A Tutorial on the Universality and Expressiveness of Fold

Hutton, Graham

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), https://doi.org/10.1017/s0956796899003500

• Journal Article Type: Article
• Publication Date: Jul 1, 1999
• Deposit Date: Oct 26, 2005
• Publicly Available Date: Oct 9, 2007
• Journal: Journal of Functional Programming
• Print ISSN: 0956-7968
• Electronic ISSN: 1469-7653
• Publisher: Cambridge University Press
• Peer Reviewed: Peer Reviewed
• Volume: 9
• Issue: 4
• DOI: https://doi.org/10.1017/s0956796899003500
• Public URL: https://nottingham-repository.worktribe.com/output/1023844