Origami Programming

One style of functional programming is based purely on recursive equations. Such equations are easy to explain, and adequate for any computational purpose, but hard to use well as programs get bigger and more complicated. In a sense, recursive equations are the `assembly language' of functional programming, and direct recursion the goto. As computer scientists discovered in the 1960s with structured programming, it is better to identify common patterns of use of such too-powerful tools, and capture these patterns as new constructions and abstractions. In functional programming, in contrast to imperative programming, we can often express the new constructions as higher-order operations within the language, whereas the move from unstructured to structured programming entailed the development of new languages. In this chapter we will look at folds and unfolds as abstractions. In a precise technical sense, folds and unfolds are the natural patterns of computation over recursive datatypes; unfolds generate data structures and folds consume them. Functional programmers are very familiar with the foldr function on lists, and its directional dual foldl; they are gradually coming to terms with the generalisation to folds on other datatypes. The computational duals, unfolds, are still rather unfamiliar; we hope to show here that they are no more complicated than, and just as useful as, folds, and to promote a style of programming based on these and similar recursion patterns