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 citeulike:2104856
%A Hutton, Graham
%C New York, NY, USA
%D 1999
%I Cambridge University Press
%J J. Funct. Program.
%K fold haskell tutorial
%N 4
%P 355--372
%R 10.1017/s0956796899003500
%T A tutorial on the universality and expressiveness of fold
%U http://dx.doi.org/10.1017/s0956796899003500
%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{citeulike:2104856,
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 = {2019-06-18T20:47:03.000+0200},
address = {New York, NY, USA},
author = {Hutton, Graham},
biburl = {https://www.bibsonomy.org/bibtex/2d47a62aa9549e40827df672fc99c61a4/alexv},
citeulike-article-id = {2104856},
citeulike-linkout-0 = {http://portal.acm.org/citation.cfm?id=968579},
citeulike-linkout-1 = {http://dx.doi.org/10.1017/s0956796899003500},
doi = {10.1017/s0956796899003500},
interhash = {88bfd7e27815fd99535abaa0028ca459},
intrahash = {d47a62aa9549e40827df672fc99c61a4},
issn = {0956-7968},
journal = {J. Funct. Program.},
keywords = {fold haskell tutorial},
month = jul,
number = 4,
pages = {355--372},
posted-at = {2015-11-24 04:23:50},
priority = {0},
publisher = {Cambridge University Press},
timestamp = {2019-08-24T00:13:50.000+0200},
title = {{A tutorial on the universality and expressiveness of fold}},
url = {http://dx.doi.org/10.1017/s0956796899003500},
volume = 9,
year = 1999
}