A Tutorial on the Universality and Expressiveness of Fold
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...
| Main Author: | |
|---|---|
| Format: | Article |
| Published: |
Cambridge University Press
1999
|
| Online Access: | https://eprints.nottingham.ac.uk/224/ |
| _version_ | 1848790373751586816 |
|---|---|
| author | Hutton, Graham |
| author_facet | Hutton, Graham |
| author_sort | Hutton, Graham |
| building | Nottingham Research Data Repository |
| collection | Online Access |
| description | 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. |
| first_indexed | 2025-11-14T18:11:35Z |
| format | Article |
| id | nottingham-224 |
| institution | University of Nottingham Malaysia Campus |
| institution_category | Local University |
| last_indexed | 2025-11-14T18:11:35Z |
| publishDate | 1999 |
| publisher | Cambridge University Press |
| recordtype | eprints |
| repository_type | Digital Repository |
| spelling | nottingham-2242020-05-04T20:33:04Z https://eprints.nottingham.ac.uk/224/ A Tutorial on the Universality and Expressiveness of Fold Hutton, Graham 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. Cambridge University Press 1999-07 Article PeerReviewed Hutton, Graham (1999) A Tutorial on the Universality and Expressiveness of Fold. Journal of Functional Programming, 9 (4). pp. 355-372. |
| spellingShingle | Hutton, Graham A Tutorial on the Universality and Expressiveness of Fold |
| title | A Tutorial on the Universality and Expressiveness of Fold |
| title_full | A Tutorial on the Universality and Expressiveness of Fold |
| title_fullStr | A Tutorial on the Universality and Expressiveness of Fold |
| title_full_unstemmed | A Tutorial on the Universality and Expressiveness of Fold |
| title_short | A Tutorial on the Universality and Expressiveness of Fold |
| title_sort | tutorial on the universality and expressiveness of fold |
| url | https://eprints.nottingham.ac.uk/224/ |