A tutorial on the universality and expressiveness of fold

J. Functional Programming 9 (4): 355–372, July 1999. Printed in the United Kingdom 355c! 1999 Cambridge University PressA tutorial on the universality andexpressiveness of foldGRAHAM HUTTONUniversity of Nottingham, Nottingham, UKhttp://www.cs.nott.ac.uk/-gmhAbstractIn functional programming, fold is a standard operator that encapsulates a simple pattern ofrecursion for processing lists. This article is a tutorial on two key aspects of the fold operatorfor lists. First of all, we emphasize the use of the universal property of fold both as a proofprinciple that avoids the need for inductive proofs, and as a definition principle that guidesthe transformation of recursive functions into definitions using fold. Secondly, we show thateven though the pattern of recursion encapsulated by fold is simple, in a language with tuplesand functions as first-class values the fold operator has greater expressive power than mightfirst be expected.Capsule ReviewWithin the last ten to fifteen years, the algebra of datatypes has become a stable and wellunderstood element of the mathematics of program construction. Graham Hutton’s paper isa highly readable, elementary introduction to the algebra centred on the well-known functionon lists. The paper distinguishes itself by focusing on how the properties are used for thecrucial task of ‘constructing’ programs, rather than on the post hoc verification of existingprograms. Several well-chosen examples are given, beginning at an ...