Skip to main content

Research Repository

Advanced Search

A Tutorial on the Universality and Expressiveness of Fold

Hutton, Graham

A Tutorial on the Universality and Expressiveness of Fold Thumbnail


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.

Citation

Hutton, G. (1999). A Tutorial on the Universality and Expressiveness of Fold. Journal of Functional Programming, 9(4),

Journal Article Type Article
Publication Date Jul 1, 1999
Deposit Date Oct 26, 2005
Publicly Available Date Mar 29, 2024
Journal Journal of Functional Programming
Print ISSN 0956-7968
Publisher Cambridge University Press
Peer Reviewed Peer Reviewed
Volume 9
Issue 4
Public URL https://nottingham-repository.worktribe.com/output/1023844

Files





You might also like



Downloadable Citations