Catamorphisms, part one
Posted by Brian on April 5, 2008
(Read this blog entry at a pace which is appropriate for you. Some readers will find this mostly old-hat, whereas others will find it rough going at parts. I encourage you to take a break and try out the code examples, if that helps you out.)
I would like to discuss catamorphisms. A catamorphism is a generalization of a fold on lists to an arbitrary data type. So for today’s blog entry, let’s review lists and folds. We’ll also end up discussing continuations as a cool technique for preserving tail-recursion in certain kinds of folds.
Lists and folds
If you’ve taken a CS class that was some sort of “introduction to functional programming”, you almost surely started out writing recursive functions that operated on lists. For example:
// SumList : list<int> -> int let rec SumList l = match l with | h :: t -> h + SumList t |  -> 0printfn "%d" (SumList [1; 2; 3; 4]) // prints 10
But then the instructor has you sum the list of numbers from 1 to 100000 and *kaboom* you blow the stack. The instructor doesn’t allow you to use iterative constructs like “for” or “while” in this class, and thus you learn about tail recursion, and rewrite the function like this:
// SumList : list<int> -> int let SumList l = let rec Loop l acc = match l with | h :: t -> Loop t (h + acc) |  -> acc Loop l 0
The essence of rewriting this tail recursively is to take the computation that would normally happen after the recursive call finishes (the “h+” in the original example), and doing the computation before the recursive call, passing the result as an extra “accumulator” argument (often conventionally named “acc”). Then when you reach the end of the list, the accumulated value is the final result. Since you don’t want the implementation detail of the accumulator to leak into the public API, the tail-recursive accumulating function is just a nested helper function (often conventionally called “Loop”, since tail recursion and loops are equivalent) and the real function calls this helper with an appropriate “seed value” for the accumulator. In the case of summing a list, the sum of an empty list is 0, so we use the value 0 to seed the accumulator.
So you get accustomed to writing your list functions tail-recursively, writing more functions like
// LengthList : list<'a> -> int let LengthList l = let rec Loop l acc = match l with | h :: t -> Loop t (1 + acc) |  -> acc Loop l 0printfn "%d" (LengthList [1; 2; 3; 4]) // 4// ReverseList : list<'a> -> list<'a> let ReverseList l = let rec Loop l acc = match l with | h :: t -> Loop t (h :: acc) |  -> acc Loop l printfn "%A" (ReverseList [1; 2; 3; 4]) // [4; 3; 2; 1]
and one day you notice a pattern emerging – the code for each function looks eerily similar. But you’re just learning functional programming and so it isn’t immediately obvious how to factor out the common pattern until one day someone shows you
// Fold : ('a -> 'b -> 'a) -> 'a -> list<'b> -> 'a let rec Fold combine acc l = match l with | h :: t -> Fold combine (combine acc h) t |  -> accprintfn "%d" (Fold (fun acc e -> e+acc) 0 [1; 2; 3; 4]) // sum: 10 printfn "%d" (Fold (fun acc _ -> 1+acc) 0 [1; 2; 3; 4]) // length: 4 printfn "%A" (Fold (fun acc e -> e::acc)  [1; 2; 3; 4]) // reverse: [4; 3; 2; 1]
You puzzle over this a bit, but upon inspecting the call sites you see that Fold has indeed factored out the essential differences from the three functions we wrote. The only differences were (1) the “computations on the accumulators” (either adding the current value to the accumulator to sum, adding one to the accumulator to get the length, or consing onto the front of the accumulator to reverse the list) and (2) the “seed values” (zero, zero, and nil, respectively). Fold neatly factors these differences out, and thus provides a general function for doing all sorts of computations on lists.
For some people the real understanding and appreciation of Fold comes in one of those “aha!” moments where it finally clicks and a ray of sunshine shines down on you from the heavens and a choir of angels sings the praises of higher-order functions. For others, it’s a gradual process, where repeated exposure over time allow you to accumulate the necessary experience to understand exactly where, when, and how “Fold” is applicable. Regardless of which of these types of person describes you, once you “get it” you keep “Fold” handy as a very useful tool in your toolbox, and you almost never write recursive functions to process lists again, because the moment you start writing them you realize you could just do it in one line of code with a fold. So now you’d write the functions just by giving names to partial applications of folds:
let SumList = Fold (fun acc e -> e+acc) 0 let LengthList = Fold (fun acc _ -> 1+acc) 0 let ReverseList = Fold (fun acc e -> e::acc)  printfn "%d" (SumList [1; 2; 3; 4]) // 10 printfn "%d" (LengthList [1; 2; 3; 4]) // 4 printfn "%A" (ReverseList [1; 2; 3; 4]) // [4; 3; 2; 1]
Of course, in practice you wouldn’t be writing any of these functions yourself since they’re all already in the F# library (most notably, the “Fold” function we wrote is fold in the List module). But this is what you do in the first few weeks of any introductory CS class – you reimplement a bunch of functionality that’s already in the standard library because those functions are simple little functions that help you learn all the main concepts.
fold, foldBack, and continuations
Why are there two functions in the List module called “fold” and “foldBack”? The difference is the order in which the elements of the list are processed and combined. The “fold” version goes left-to-right, whereas the “foldBack” version goes right-to-left. (These functions also take arguments in a slightly different order; inspect their signatures for the details.) Here are a couple examples that demonstrate the difference in behavior:
// print "1 2 3 4 " List.fold (fun _ e -> printf "%d " e) () [1; 2; 3; 4] printfn "" // print "4 3 2 1 " List.foldBack (fun e _ -> printf "%d " e) [1; 2; 3; 4] () printfn ""// reverse: [4; 3; 2; 1] printfn "%A" (List.fold (fun acc e -> e::acc)  [1; 2; 3; 4]) // clone: [1; 2; 3; 4] printfn "%A" (List.foldBack (fun e acc -> e::acc) [1; 2; 3; 4] )
In the first example, I’ve passed a function that prints each element as it is encountered as the “combining function” argument to the fold. The output demonstrates the evaluation order. In the second example, I’ve passed a function that conses the current element onto the front of the accumulated list. If we walk the list left-to-right, creating a new list by consing elements onto the front of an accumulator, we end up with a reversed copy of the list. Whereas if we do the same thing traversing from right-to-left, we get a copy of the list with the elements in the original order (we just cloned the list).
The “Fold” we already wrote today corresponds to the “fold” version. The question is, how would you write the “foldBack” version? The initial naive approach is
let rec FoldBack combine l acc = match l with | h :: t -> combine h (FoldBack combine t acc) |  -> acc
but this isn’t tail-recursive, and so calling it on a large list yields a StackOverflowException. How do we get around this? We’re already using an accumulator. We need to traverse to the end before we start calling the “combine” function, since the last value of the list is the first value it processes. But we also need to remember all the elements in the list so that we can process them in reverse order… only not on the call stack on the way back, because our whole goal is to be tail-recursive and not use the call stack. We’re going to need to allocate an auxiliary data structure. There are a number of choices here. One straightforward way is to reverse the list and call fold_left (reordering the arguments as necessary):
let FoldBack combine l acc =
List.fold (fun x y -> combine y x) acc (List.rev l)
List.fold (fun x y -> combine y x) acc (List.rev l)
The auxiliary data structure here was another list – the reversed copy of the original list. However there’s another possible implementation strategy. A particularly elegant and generally useful strategy is to employ a continuation. A continuation is just a function that describes “the remaining portion of the computation”. Here is what it looks like to rewrite FoldBack to use a continuation:
// FoldBack : ('a -> 'b -> 'b) -> list<'a> -> 'b -> 'b let FoldBack combine l acc = // Loop : list<'a> -> ('b -> 'c) -> 'c let rec Loop l cont = match l with | h :: t -> Loop t (fun racc -> cont (combine h racc)) |  -> cont acc Loop l (fun x -> x)
Just as accumulator parameters are often conventionally named “acc”, continuation parameters are often conventionally named “cont”. Here the continuation describes the remaining work at a given point in the list as a function of the result of the work that is yet to be done. In the expression
(fun racc -> cont (combine h racc))
“racc” is the right-accumulated result of the tail-recursive call that will happen in the future. This functions basically says: “Once I eventually have that result, the next thing to do is combine that result with the current element of the list. Then I’ll know my answer, and so I can pass that answer to the continuation that the previous recursive call handed to me.” So we walk forward down the list, building up a delayed computation that represents all the work we have to do. And when we reach the end of the list, we finally invoke this computation.
Just as we needed to “seed” accumulator parameters, we need to “seed” the continuation parameter, and in this case, the correct seed value is the identity function “(fun x -> x)”.
Where is the auxiliary data structure in this solution? It’s the continuation. Specifically, the lambda creates a closure, a data structure representing values captured by the lambda. Each recursive call differs only in the values of “h” and “cont”, so we can imagine the closure being represented in memory as a pair of those two values. This is (not coincidentally) quite similar to how we might ‘draw’ the process of reversing a list:
//  // // /---+--\ // | 1 | -+-->  // \---+--/ // // /---+--\ /---+--\ // | 2 | -+-->| 1 | -+-->  // \---+--/ \---+--/ // // /---+--\ /---+--\ /---+--\ // | 3 | -+-->| 2 | -+-->| 1 | -+-->  // \---+--/ \---+--/ \---+--/
To reverse a list, we start with the seed value “nil”, and then walk the list from left to right, consing each value onto the font of the list. You’ve probably seen pictures like the above before, where  represents nil, and each ‘box’ represents a cons call, with two fields: “data” and “next”. “data” is an int, and “next” is a reference to another list<int>.
The exact same picture applies to how FoldBack builds continuations as it recurses. We are building the same kind of structure, only now each diagram represents a one-argument function of type “int -> int” rather than a “list<int>”. This time,  represents the identity function (fun x -> x). Each box represents a closure over the lambda “fun racc -> cont (combine h racc)”, where the two fields are “h” and “cont”. “h” is an int, and “cont” is a reference to another int->int function.
To be continued…
Today we’ve built a foundation. With an understanding of folds on lists, we are prepared to consider folds over other data structures. So we’ll continue along those lines in a future blog entry.