Recursion patterns

Posted on Friday, September 3rd, 2010 by jeremygibbons

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.

About jeremygibbons

Jeremy Gibbons is Professor of Computing in Oxford University Department of Computer Science, and a fan of functional programming and patterns of computation.
This entry was posted in Uncategorized. Bookmark the permalink.

5 Responses to Recursion patterns

  2. Roger says:
    Sunday, July 8th, 2018 at 3:58 am

    Might it be helpful to the reader if the type signatures are included in the code fragments?
    It might be clearer to specify in the ‘map’ example that f : a -> a, and in the ‘foldr’ example that f : a -> b -> b.

    Reply
  3. zhang says:
    Thursday, May 12th, 2022 at 3:25 am

    Which book do you refer to ‘this book’?

    Reply

Leave a comment