# Beyond Lists

## Contents

# 4.5. Beyond Lists#

Functionals like map and fold are not restricted to lists. They make sense for nearly any kind of data collection. For example, recall this tree representation:

```
type 'a tree =
| Leaf
| Node of 'a * 'a tree * 'a tree
```

```
type 'a tree = Leaf | Node of 'a * 'a tree * 'a tree
```

## 4.5.1. Map on Trees#

This one is easy. All we have to do is apply the function `f`

to the
value `v`

at each node:

```
let rec map_tree f = function
| Leaf -> Leaf
| Node (v, l, r) -> Node (f v, map_tree f l, map_tree f r)
```

```
val map_tree : ('a -> 'b) -> 'a tree -> 'b tree = <fun>
```

## 4.5.2. Fold on Trees#

This one is only a little harder. Let’s develop a fold functional for `'a tree`

similar to our `fold_right`

over `'a list`

. One way to think of
`List.fold_right`

would be that the `[]`

value in the list gets replaced by the
`acc`

argument, and each `::`

constructor gets replaced by an application of the
`f`

argument. For example, `[a; b; c]`

is syntactic sugar for
`a :: (b :: (c :: []))`

. So if we replace `[]`

with `0`

and `::`

with `( + )`

,
we get `a + (b + (c + 0))`

. Along those lines, here’s a way we could rewrite
`fold_right`

that will help us think a little more clearly:

```
type 'a mylist =
| Nil
| Cons of 'a * 'a mylist
let rec fold_mylist f acc = function
| Nil -> acc
| Cons (h, t) -> f h (fold_mylist f acc t)
```

```
type 'a mylist = Nil | Cons of 'a * 'a mylist
```

```
val fold_mylist : ('a -> 'b -> 'b) -> 'b -> 'a mylist -> 'b = <fun>
```

The algorithm is the same. All we’ve done is to change the definition of lists to use constructors written with alphabetic characters instead of punctuation, and to change the argument order of the fold function.

For trees, we’ll want the initial value of `acc`

to replace each `Leaf`

constructor, just like it replaced `[]`

in lists. And we’ll want each `Node`

constructor to be replaced by the operator. But now the operator will need to be
*ternary* instead of *binary*—that is, it will need to take three
arguments instead of two—because a tree node has a value, a left child,
and a right child, whereas a list cons had only a head and a tail.

Inspired by those observations, here is the fold function on trees:

```
let rec fold_tree f acc = function
| Leaf -> acc
| Node (v, l, r) -> f v (fold_tree f acc l) (fold_tree f acc r)
```

```
val fold_tree : ('a -> 'b -> 'b -> 'b) -> 'b -> 'a tree -> 'b = <fun>
```

If you compare that function to `fold_mylist`

, you’ll note it very nearly
identical. There’s just one more recursive call in the second pattern-matching
branch, corresponding to the one more occurrence of `'a tree`

in the definition
of that type.

We can then use `fold_tree`

to implement some of the tree functions we’ve
previously seen:

```
let size t = fold_tree (fun _ l r -> 1 + l + r) 0 t
let depth t = fold_tree (fun _ l r -> 1 + max l r) 0 t
let preorder t = fold_tree (fun x l r -> [x] @ l @ r) [] t
```

```
val size : 'a tree -> int = <fun>
```

```
val depth : 'a tree -> int = <fun>
```

```
val preorder : 'a tree -> 'a list = <fun>
```

Why did we pick `fold_right`

and not `fold_left`

for this development? Because
`fold_left`

is tail recursive, which is something we’re never going to achieve
on binary trees. Suppose we process the left branch first; then we still have to
process the right branch before we can return. So there will always be work left
to do after a recursive call on one branch. Thus on trees an equivalent to
`fold_right`

is the best which we can hope for.

The technique we used to derive `fold_tree`

works for any OCaml variant type
`t`

:

Write a recursive

`fold`

function that takes in one argument for each constructor of`t`

.That

`fold`

function matches against the constructors, calling itself recursively on any value of type`t`

that it encounters.Use the appropriate argument of

`fold`

to combine the results of all recursive calls as well as all data not of type`t`

at each constructor.

This technique constructs something called a *catamorphism*, aka a *generalized
fold operation*. To learn more about catamorphisms, take a course on category
theory.

## 4.5.3. Filter on Trees#

This one is perhaps the hardest to design. The problem is: if we decide to filter a node, what should we do with its children?

We could recurse on the children. If after filtering them only one child remains, we could promote it in place of its parent. But what if both children remain, or neither? Then we’d somehow have to reshape the tree. Without knowing more about how the tree is intended to be used—that is, what kind of data it represents—we are stuck.

Instead, we could just eliminate the children entirely. So the decision to filter a node means pruning the entire subtree rooted at that node.

The latter is easy to implement:

```
let rec filter_tree p = function
| Leaf -> Leaf
| Node (v, l, r) ->
if p v then Node (v, filter_tree p l, filter_tree p r) else Leaf
```

```
val filter_tree : ('a -> bool) -> 'a tree -> 'a tree = <fun>
```