## Catamorphisms, part two

Posted by Brian on April 6, 2008

Last time we talked about folds on lists. Today we’ll generalize to folds on trees, and suggest how to generalize folds to arbitrary data types.

### Binary trees

Binary trees are a common data structure. Sometimes (such as in the wikipedia page for "catamorphism") you’ll see tree data types defined where they store data in the leaves (on the fringe), but more commonly I think people author tree structures that store data in the interior nodes of the tree. So that’s the kind of data structure I’ll define for the next example:

| Node of (*data*)‘a * (*left*)Tree<’a> * (*right*)Tree<’a>

| Leaf

// 4

// 2 6

// 1 3 5 7

let tree7 = Node(4, Node(2, Node(1, Leaf, Leaf), Node(3, Leaf, Leaf)),

Node(6, Node(5, Leaf, Leaf), Node(7, Leaf, Leaf)))

A tree "Node" has a bit of data, a left child, and a right child. "Leaf" represents null – the edge of the tree. I’ve also defined a small sample tree called "tree7", which is the full and balanced binary search tree containing the numbers 1-7 (the canonical ‘example tree’ we always used in my CS classes). (Aside: Currently F# doesn’t let you name the bits of data in each alternative of a discriminated union, so I put the names I would give those fields ("data", "left", and "right") in comments.)

There are a number of common functions you might write for trees. Here are a few, along with naive implementations:

let rec SumTree t =

match t with

| Node(x,left,right) -> x + (SumTree left) + (SumTree right)

| Leaf -> 0

// InOrder : Tree<’a> -> list<’a>

let rec InOrder t =

match t with

| Node(x,left,right) -> (InOrder left) @ [x] @ (InOrder right)

| Leaf -> []

// Height : Tree<’a> -> int

let rec Height t =

match t with

| Node(x,left,right) -> 1 + (max (Height left) (Height right))

| Leaf -> 0

printfn "%A" (InOrder tree7) // [1; 2; 3; 4; 5; 6; 7]

printfn "%d" (Height tree7) // 3

SumTree adds up the data values in all the Nodes in the tree. InOrder yields a list of data values in the order of an inorder traversal of the tree. Height computes the height (sometimes called the "depth") of the tree, the longest chain of Nodes starting from the root.

Note that I called the implementations "naive" because they are not tail-recursive. Additionally, InOrder uses the append operator (@) to concatenate lists, which is needlessly inefficient. These are both pitfalls that I discussed in a prior blog entry.

### Folds over trees

You may notice lot of commonality in those three tree functions, and again we can factor out that commonality into a general fold function for trees. Here it is, along with a redefinition of our three tree functions:

let FoldTree nodeF leafV t =

let rec Loop t cont =

match t with

| Node(x,left,right) -> Loop left (fun lacc ->

Loop right (fun racc ->

cont (nodeF x lacc racc)))

| Leaf -> cont leafV

Loop t (fun x -> x)

let InOrder = FoldTree (fun x l r -> l @ [x] @ r) []

let Height = FoldTree (fun _ l r -> 1 + max l r) 0

FoldTree takes three parameters. The first parameter ("nodeF") is a function that processes Nodes, combining the data value in the node with the result of recursive calls on the left and right subtrees. The second parameter ("leafV") is the result value of a fold on just a Leaf (an empty tree). The third parameter ("t") is the tree that we want to process. Our three tree functions are now defined simply as partial applications of this very general FoldTree function.

The code for FoldTree leverages the "continuation" strategy we used last time in order to make the implementation tail-recursive. For a Node, we recurse on the left subtree, along with a continuation function that takes that result (which I’ve called "lacc" for "left accumulator") and recurses on the right subtree with a new continuation function that takes *that *result ("racc" – right accumulator) and then uses the "nodeF" function to combine the data in the current node, the left-recursion result, and the right-recursion result into a final result which it passes to the continuation for the current call. For a Leaf, we just continue with the "leafV" value. (That sounds complicated, but if you followed the description of using a continuation to implement FoldRight in the previous blog entry, this is the same thing, only we applied it twice since we have two recursive calls to make.)

Since the implementation of FoldTree is tail-recursive, we’ve addressed one of the two pitfalls. SumTree and Height now have terrific definitions.

InOrder, however, still suffers from the second pitfall, in that it inefficiently builds a list through a number of appends (order N^2) rather than consing up the list in reverse order (order N). It’s not immediately obvious how to fix this. We ideally want to build the list in a "reverse inorder" traversal, consing each new data value on to the front of an accumulator list. How can we achieve this? Where would the accumulator go, and how can we thread it through the fold computation in the right order?

The answer is surprising:

What’s going on here? Something seems fishy – for example, the function passed as the first parameter to FoldTree is taking four parameters instead of three. However, as I alluded to in a prior blog entry, an implication of currying and partial application is that "fun x y -> body" means the same thing as "fun x -> fun y -> body" (you can tease apart multiple arguments). And so in our example, "fun x l r acc ->" can be interpreted as "fun x l r -> fun acc ->", which now makes it more apparent how this fits the signature of FoldTree:

Here the final result type ‘r is not just any ordinary value type – it’s a function type! Since we need to thread an accumulator through the computation, we’ll have FoldTree compute a new function that takes the accumulator. And so this explains the extra "acc" parameters. As a result, now "l" and "r" (the results of the recursive calls on left and right subtrees) are also also one-argument functions that expect an accumulator parameter. And thus our "nodeF" node function can create our in-order list in reverse order, by first calling the right-subtree function with the accumulator "(r acc)", and then consing the data of the current node onto the front of that "(x :: …)", and then passing that result as the final accumulator to the left-subtree function "(l …)". Traversing a Leaf does not have an impact on the traversal, and so the "leafV" leaf value is just the identity function (it returns the same accumulator without any changes). The result of the call to FoldTree is thus a function that will compute the inorder traversal list once it’s passed the "seed" accumulator, which explains the empty list "[]" at the end of InOrder’s definition.

Whew! I find it hard to write prose that does justice to the explanation of what’s going on here, so I encourage you to study this until you understand what’s going on. Here are three different tree traversal definitions, along with sample calls:

let PreOrder t = (FoldTree (fun x l r acc -> x :: l (r acc)) (fun acc -> acc) t) []

let PostOrder t = (FoldTree (fun x l r acc -> l (r (x :: acc))) (fun acc -> acc) t) []

// 4

// 2 6 <– tree7

// 1 3 5 7

printfn "%A" (InOrder tree7) // [1; 2; 3; 4; 5; 6; 7]

printfn "%A" (PreOrder tree7) // [4; 2; 1; 3; 6; 5; 7]

printfn "%A" (PostOrder tree7) // [1; 3; 2; 5; 7; 6; 4]

Awesome.

### Aside: currying and partial application

We just saw the "particularly interesting" application of currying that I mentioned at the end of the blog entry from a few days ago. When we needed to thread an extra accumulator parameter through the FoldTree function to efficiently perform our traversal, we were free to just tack on that extra parameter, and the types and the computation all just worked out. A "function that takes four arguments and returns a value" is the same thing as a "function that takes three arguments and returns another function that takes one argument and returns a value". These niceties of the F# type system and syntax made it easy to express tree traversals as one-liner applications of a general fold function on trees. The resulting traversal functions are tail-recursive (no fear of blowing the stack) and have the optimal complexity (order N for a tree of N nodes). How cool is that? F# rocks.

### Catamorphisms

Now that we’ve authored folds over both lists and trees, we can start thinking about what they have in common and start understanding what a catamorphism is. To sum up what we’ve seen so far, here are the two data types and the signatures of the corresponding fold functions. (I’ve used my own type definition for List; the F# list<’a> type is very similar, but would sidetrack us with a couple needless syntax details.)

| Cons of ‘a * List<’a>

| Nil

// FoldList : (‘r -> ‘a -> ‘r) -> ‘r -> List<’a> -> ‘r

type Tree<’a> =

| Node of ‘a * Tree<’a> * Tree<’a>

| Leaf

// FoldTree : (‘a -> ‘r -> ‘r -> ‘r) -> ‘r -> Tree<’a> -> ‘r

See some similarity? As we’ll see in a future entry, we can generalize folds to arbitrary discriminated-union types, where the first N parameters to the fold correspond to the N alternatives in the discriminated union, and the final (N+1) parameter is the data structure itself. Both List and Tree are discriminated unions with two alternatives, and so each has a corresponding fold function of 3 (2+1) parameters. FoldList’s first parameter is a function that says what to do with a Cons (given the result of a recursive call on the rest of the list, and the current node value, compute a result), and its second parameter says what to do return for a Nil. Similarly, FoldTree’s first parameter says what to do with a Node (given the current node value, the result of recursing the left subtree, and the result of recursing the right subtree, compute a result), and its second parameter says what to return for a Leaf.

This is the essence of a catamorphism – we let the structure of the data guide the computation. The shape of the data structure implies a particular signature for a fold function that can be used as a general mechanism for doing arbitrary computations over data of that shape. In a future installment I hope to demonstrate this in more detail with a cool, more-real-world example.

## Dustin said

Hey Brian,Neither of these are actually compilable because of the value restriction:let SumTree = FoldTree (fun x l r -> x + l + r) 0let InOrder = FoldTree (fun x l r -> l @ [x] @ r) []let Height = FoldTree (fun _ l r -> 1 + max l r) 0They need to be rewritten like so to compile:let SumTree t = FoldTree (fun x l r -> x + l + r) 0 tlet InOrder t = FoldTree (fun x l r -> l @ [x] @ r) [] tlet Height t = FoldTree (fun _ l r -> 1 + max l r) 0 t

## Brian said

Dustin,

These do compile on the latest release (1.9.4.15, available at http://research.microsoft.com/fsharp/release.aspx). But they may not have compiled on previous releases (and I posted this code before 1.9.4.15 was released – oops!), so perhaps that\’s what you\’re seeing. From now on I\’ll try to be more careful about only posting code that compiles against the latest _released_ version of the compiler (I\’ve been guilty of this before).

Thanks for keeping me honest! :)

## Dov said

BrianWith the latest F# v1.9.6.16 (Compiled for .NET 4) I\’m still getting the value restriction error for the Height & the InOrder functions:let InOrder = FoldTree (fun x l r -> l @ [x] @ r) []let Height = FoldTree (fun _ l r -> 1 + max l r) 0error FS0030: Value restriction. The value \’Height\’ has been inferred to have generic type val Height : (Tree<\’_a> -> int)Either make the arguments to \’Height\’ explicit or, if you do not intend for it to be generic, add a type annotation.error FS0030: Value restriction. The value \’InOrder\’ has been inferred to have generic type val InOrder : (Tree<\’_a> -> \’_a list)Either make the arguments to \’InOrder\’ explicit or, if you do not intend for it to be generic, add a type annotation.

## Brian said

Ah, yes, you can do eta-conversion and add a \’t\’ to both sides, likelet Height t = FoldTree (fun _ l r -> 1 + max l r) 0 tSee also http://stackoverflow.com/questions/1131456/understanding-f-value-restriction-errors