Skip to main content

Research Repository

See what's under the surface

A Tutorial on the Universality and Expressiveness of Fold

Hutton, Graham

Authors



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.

Journal Article Type Article
Publication Date Jul 1, 1999
Journal Journal of Functional Programming
Print ISSN 0956-7968
Publisher Cambridge University Press (CUP)
Peer Reviewed Peer Reviewed
Volume 9
Issue 4
APA6 Citation Hutton, G. (1999). A Tutorial on the Universality and Expressiveness of Fold. Journal of Functional Programming, 9(4),
Copyright Statement Copyright information regarding this work can be found at the following address: http://eprints.nottingh.../end_user_agreement.pdf

Files

fold.pdf (192 Kb)
PDF

Copyright Statement
Copyright information regarding this work can be found at the following address: http://eprints.nottingham.ac.uk/end_user_agreement.pdf





You might also like



Downloadable Citations