## Functional Pearls #1: foldr and cprod

# Pearls: a programmers best friend?

So, I’m back after a really long hiatus. This post is part 1 of a series about well known and perhaps not-so-well-known functional pearls. A *Functional Pearl* is an elegant, purely functional solution to a problem. In this post, we’ll look at the earliest known functional pearl, Christopher Strachey’s Cartesian product function. I found this pearl in a paper called “Strachey’s functional pearl, forty years on” by Mike Spivey, and this post is largely based on that paper.

# Folds

If you’ve written any amount of code in a functional programming language, you’ve come across foldr (or perhaps foldl). It’s ubiquitous in the fp world and as natural as say, a for loop in an imperative language.

` foldl y [x1,x2,x3,..., xn] = f(f(...f(f(x1, y), x2), ...), x_n)`

And foldr is the same, but “from the right”:

`foldr f y [x1,x2,x3, ..., xn] = f(x1, f(x2, f(..., f(xn, y)...)))`

Incidentally, a nice way of looking at foldr is: it is the unique solution (for fixed f and o) to the equations:

foldr f o [] = o foldr f o (x:xs) = f x (foldr f o xs)

One of the things that are so great about languages like Haskell, is that this IS how you define functions. The above is executable Haskell code that defines foldr!

# And God said: let there be foldr…

A bit of history about foldr. It came as something of a shock to me that foldr was *invented* (discovered?), and there was actually a time without a foldr! Somehow I had always assumed that foldr had been created in the Big Bang along with everything else. But it appears that there was actually a time when higher order functions like “map” were known (in LISP, for example) but foldr wasn’t. And although a lot of programmers had probably written their own foldr’s without realizing it, the discovery of its coolness and universal usefulness can probably be attributed to Christopher Strachey (I should clarify that the history is actually pretty hazy, so please tell me if you can find an earlier reference)

He’s probably better known as one of the developers of the CPL programming language (the great-grandfather of C). But he’s done a bunch of other things in his career, and among them lies the first functional pearl.

He was investigating foldl and foldr (although not by that name) in 1961 (according to some handwritten notes that were found later) and began to realize how useful these functions could be. Then, in 1966 he published a paper giving examples of CPL code written in a functional style. This paper contained (among many other things) a function called cprod, which used foldr. This is the function that is now widely regarded as the very first “functional pearl”.

# A X B = ?

The cprod function finds the Cartesian Product of a bunch of sets (expressed as a list of lists). For example,

`cprod [[1,2],[2,3],[1]] = [[1,2,1], [1,3,1], [2,2,1],[2,3,1]]`

These days, several languages let you do this sort of thing with list comprehensions. For example,

`cprod (xs:xss) = [x:ys | x <- xs, ys <- cprod xss]`

But we will use neither list comprehension nor recursion – just foldr. To see how, remember what I said about `p = foldr f o`

being the unique solution to:

p [] = a p (x:xs) = f x (p xs)

Then for `f xs yss = [x:ys | x <- xs, ys <- xss]`

, cprod can be seen as the unique solution to:

cprod [] = [[]] cprod (xs:xss) = f xs (cprod xss)

In fact, `cprod = foldr f [[]]`

. Now all we have to do is rewrite the list comprehension f in terms of list primitives alone. We can do this by expanding each generator in the comprehension as a foldr, giving:

cprod = foldr f [[]] where f xs yss = foldr (g yss) [] xs g yss xs xss = foldr (h x) xss yss h x ys uss = (x:ys):uss

Beautifying this a little, we get our very first functional pearl!

cprod = foldr f [[]] where f xs yss = foldr g [] xs where g x xss = foldr h xss yss where h ys uss = (x:ys):uss

Next week – zippers!

From our modern perspective, we can also make use of the fact that lists form a monad:

cprod = sequence

and in turn we have that:

sequence = foldr (liftM2 (:)) (return [])

This liftM2 (:), for the list monad, is exactly the function f in the article. (Of course, return [] = [[]].) :)

Cale Gibbard said this on August 21, 2008 at 10:23 am |

wow!!!

hellfeuer said this on August 21, 2008 at 1:11 pm |

Hi, thanks for the nice post! I’m looking forward to the next one.

Three things regarding the last definition:

1. s/foldr f [] xs/foldr g [] xs/

2. s/foldr h zss yss/foldr h xss yss/

3. The second and third ‘where’ should be further indented, no?

Paulo said this on August 23, 2008 at 9:57 am |

woops!! fixed.

The indentation was for aesthetic reason, but maybe its better to be parsable than beautiful :)

hellfeuer said this on August 23, 2008 at 1:14 pm |