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!

About these ads

~ by hellfeuer on August 20, 2008.

4 Responses to “Functional Pearls #1: foldr and cprod”

  1. 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 [] = [[]].) :)

  2. wow!!!

  3. 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?

  4. woops!! fixed.
    The indentation was for aesthetic reason, but maybe its better to be parsable than beautiful :)

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

 
Follow

Get every new post delivered to your Inbox.

%d bloggers like this: