Recursion patterns

The central idea in this book is the importance of recursion patterns in functional programming. One of the simplest examples is the map operator on lists, defined in Haskell as follows:

$\begin{array}{lcl} \mathit{map}\;f\;[\,] &=& [\,] \\ \mathit{map}\;f\;(x:xs) &=& f\;x : \mathit{map}\;f\;xs \end{array}$

(Intuitively, $\mathit{map}$ applies a function $f$ to every element of a list, returning a new list. When $\mathit{map}\;f$ is applied to the empty list $[\,]$ , it returns the empty list; applied to a non-empty list $x:xs$ with head $x$ and tail $xs$ , it returns the list whose head is $f$ applied to $x$ , and whose tail is $\mathit{map}\;f$ applied recursively to $xs$ . Because the function $\mathit{map}$ accepts another function $f$ as an argument, it is called a higher-order function.)

Another example familiar to Haskell programmers is the fold operator on lists:

$\begin{array}{lcl} \mathit{foldr}\;f\;e\;[\,] &=& e \\ \mathit{foldr}\;f\;e\;(x:xs) &=& f\;x\;(\mathit{foldr}\;f\;e\;xs) \end{array}$

(Intuitively, this “folds” a list up into a value; the empty list is folded into the initial value $e$ , and a non-empty list is folded by recursively folding the tail then combining the result of this with the head using the binary function $f$ .)

One can think of the operators $\mathit{map}$ and $\mathit{foldr}$ as abstracted patterns of computation: many useful functions can be expressed in terms of them, and identifying them as useful and reusable concepts saves a lot of repetition in code. Put another way, functional programming (especially lazy functional programming) languages provide the programmer with good tools for building their own control structures; if you don’t have the right kind of loop built-in, just define it as a higher-order function.

But there’s another benefit to be derived from certain recursion patterns (in particular, for the map and fold above, but not for any old custom control structure that you might just have defined). Take the definition of $\mathit{foldr}$ , but abstract from the $\mathit{foldr}\;f\;e$ part:

$\begin{array}{lcl} h\;[\,] &=& e \\ h\;(x:xs) &=& f\;x\;(h\;xs) \end{array}$

and read this as an equation in the unknown $h$ , for fixed $f$ and $e$ . It turns out that this equation has a unique solution (modulo some subtleties, as we’ll cover later) — which is, as you might have guessed, $h = \mathit{foldr}\;f\;e$ . This is called the universal property of $\mathit{foldr}$ , and it is very convenient for reasoning about programs with. For example, to show that some complicated expression equals a given fold, it suffices to show that the expression satisfies the universal property for that fold. Such universal properties will come up again and again throughout the book.