A tutorial on the universality and expressiveness of fold
G. Hutton. Journal of Functional Programming, 9 (4):
355-372(июля 1999)
Аннотация
In functional programming, fold is a standard operator that encapsulates a simple pattern of
recursion for processing lists. This article is a tutorial on two key aspects of the fold operator
for lists. First of all, we emphasize the use of the universal property of fold both as a proof
principle that avoids the need for inductive proofs, and as a definition principle that guides
the transformation of recursive functions into definitions using fold. Secondly, we show that
even though the pattern of recursion encapsulated by fold is simple, in a language with tuples
and functions as first-class values the fold operator has greater expressive power than might
first be expected.
%0 Journal Article
%1 Hutton1999fold
%A Hutton, Graham
%D 1999
%J Journal of Functional Programming
%K computer-science functional-programming programming
%N 4
%P 355-372
%T A tutorial on the universality and expressiveness of fold
%U http://dblp.uni-trier.de/db/journals/jfp/jfp9.html#Hutton99
%V 9
%X In functional programming, fold is a standard operator that encapsulates a simple pattern of
recursion for processing lists. This article is a tutorial on two key aspects of the fold operator
for lists. First of all, we emphasize the use of the universal property of fold both as a proof
principle that avoids the need for inductive proofs, and as a definition principle that guides
the transformation of recursive functions into definitions using fold. Secondly, we show that
even though the pattern of recursion encapsulated by fold is simple, in a language with tuples
and functions as first-class values the fold operator has greater expressive power than might
first be expected.
@article{Hutton1999fold,
abstract = {In functional programming, fold is a standard operator that encapsulates a simple pattern of
recursion for processing lists. This article is a tutorial on two key aspects of the fold operator
for lists. First of all, we emphasize the use of the universal property of fold both as a proof
principle that avoids the need for inductive proofs, and as a definition principle that guides
the transformation of recursive functions into definitions using fold. Secondly, we show that
even though the pattern of recursion encapsulated by fold is simple, in a language with tuples
and functions as first-class values the fold operator has greater expressive power than might
first be expected.},
added-at = {2017-05-10T05:39:37.000+0200},
author = {Hutton, Graham},
biburl = {https://www.bibsonomy.org/bibtex/22cef4086b03e5a2620c3d10bba814d7a/salotz},
interhash = {88bfd7e27815fd99535abaa0028ca459},
intrahash = {2cef4086b03e5a2620c3d10bba814d7a},
journal = {Journal of Functional Programming},
keywords = {computer-science functional-programming programming},
month = {July},
number = 4,
pages = {355-372},
timestamp = {2017-05-10T05:39:37.000+0200},
title = {A tutorial on the universality and expressiveness of fold},
url = {http://dblp.uni-trier.de/db/journals/jfp/jfp9.html#Hutton99},
volume = 9,
year = 1999
}