# Fold

## Contents

# 4.4. Fold#

The map functional gives us a way to individually transform each element of a
list. The filter functional gives us a way to individually decide whether to
keep or throw away each element of a list. But both of those are really just
looking at a single element at a time. What if we wanted to somehow combine all
the elements of a list? That’s what the *fold* functional is for. It turns out
that there are two versions of it, which we’ll study in this section. But to
start, let’s look at a related function—not actually in the standard
library—that we call *combine*.

## 4.4.1. Combine#

Once more, let’s write two functions:

```
(** [sum lst] is the sum of all the elements of [lst]. *)
let rec sum = function
| [] -> 0
| h :: t -> h + sum t
let s = sum [1; 2; 3]
```

```
val sum : int list -> int = <fun>
```

```
val s : int = 6
```

```
(** [concat lst] is the concatenation of all the elements of [lst]. *)
let rec concat = function
| [] -> ""
| h :: t -> h ^ concat t
let c = concat ["a"; "b"; "c"]
```

```
val concat : string list -> string = <fun>
```

```
val c : string = "abc"
```

As when we went through similar exercises with map and filter, the functions share a great deal of common structure. The differences here are:

the case for the empty list returns a different initial value,

`0`

vs`""`

the case of a non-empty list uses a different operator to combine the head element with the result of the recursive call,

`+`

vs`^`

.

So can we apply the Abstraction Principle again? Sure! But this time we need to
factor out *two* arguments: one for each of those two differences.

To start, let’s factor out only the initial value:

```
let rec sum' init = function
| [] -> init
| h :: t -> h + sum' init t
let sum = sum' 0
let rec concat' init = function
| [] -> init
| h :: t -> h ^ concat' init t
let concat = concat' ""
```

```
val sum' : int -> int list -> int = <fun>
```

```
val sum : int list -> int = <fun>
```

```
val concat' : string -> string list -> string = <fun>
```

```
val concat : string list -> string = <fun>
```

Now the only real difference left between `sum'`

and `concat'`

is the operator
used to combine the head with the recursive call on the tail. That operator can
also become an argument to a unified function we call `combine`

:

```
let rec combine op init = function
| [] -> init
| h :: t -> op h (combine op init t)
let sum = combine ( + ) 0
let concat = combine ( ^ ) ""
```

```
val combine : ('a -> 'b -> 'b) -> 'b -> 'a list -> 'b = <fun>
```

```
val sum : int list -> int = <fun>
```

```
val concat : string list -> string = <fun>
```

One way to think of `combine`

would be that:

the

`[]`

value in the list gets replaced by`init`

, andeach

`::`

constructor gets replaced by`op`

.

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

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

. So
if we replace `[]`

with `0`

and `::`

with `(+)`

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

.
And that would be the sum of the list.

Once more, the Abstraction Principle has led us to an amazingly simple and succinct expression of the computation.

## 4.4.2. Fold Right#

The `combine`

function is the idea underlying an actual OCaml library function.
To get there, we need to make a couple of changes to the implementation we have
so far.

First, let’s rename some of the arguments: we’ll change `op`

to `f`

to emphasize
that really we could pass in any function, not just a built-in operator like
`+`

. And we’ll change `init`

to `acc`

, which as usual stands for “accumulator”.
That yields:

```
let rec combine f acc = function
| [] -> acc
| h :: t -> f h (combine f acc t)
```

```
val combine : ('a -> 'b -> 'b) -> 'b -> 'a list -> 'b = <fun>
```

Second, let’s make an admittedly less well-motivated change. We’ll swap the
implicit list argument to `combine`

with the `init`

argument:

```
let rec combine' f lst acc = match lst with
| [] -> acc
| h :: t -> f h (combine' f t acc)
let sum lst = combine' ( + ) lst 0
let concat lst = combine' ( ^ ) lst ""
```

```
val combine' : ('a -> 'b -> 'b) -> 'a list -> 'b -> 'b = <fun>
```

```
val sum : int list -> int = <fun>
```

```
val concat : string list -> string = <fun>
```

It’s a little less convenient to code the function this way, because we no
longer get to take advantage of the `function`

keyword, nor of partial
application in defining `sum`

and `concat`

. But there’s no algorithmic change.

What we now have is the actual implementation of the standard library function
`List.fold_right`

. All we have left to do is change the function name:

```
let rec fold_right f lst acc = match lst with
| [] -> acc
| h :: t -> f h (fold_right f t acc)
```

```
val fold_right : ('a -> 'b -> 'b) -> 'a list -> 'b -> 'b = <fun>
```

Why is this function called “fold right”? The intuition is that the way it works
is to “fold in” elements of the list from the right to the left, combining each
new element using the operator. For example, `fold_right ( + ) [a; b; c] 0`

results in evaluation of the expression `a + (b + (c + 0))`

. The parentheses
associate from the right-most subexpression to the left.

## 4.4.3. Tail Recursion and Combine#

Neither `fold_right`

nor `combine`

are tail recursive: after the recursive call
returns, there is still work to be done in applying the function argument `f`

or
`op`

. Let’s go back to `combine`

and rewrite it to be tail recursive. All that
requires is to change the cons branch:

```
let rec combine_tr f acc = function
| [] -> acc
| h :: t -> combine_tr f (f acc h) t (* only real change *)
```

```
val combine_tr : ('a -> 'b -> 'a) -> 'a -> 'b list -> 'a = <fun>
```

(Careful readers will notice that the type of `combine_tr`

is different than the
type of `combine`

. We will address that soon.)

Now the function `f`

is applied to the head element `h`

and the accumulator
`acc`

*before* the recursive call is made, thus ensuring there’s no work
remaining to be done after the call returns. If that seems a little mysterious,
here’s a rewriting of the two functions that might help:

```
let rec combine f acc = function
| [] -> acc
| h :: t ->
let acc' = combine f acc t in
f h acc'
let rec combine_tr f acc = function
| [] -> acc
| h :: t ->
let acc' = f acc h in
combine_tr f acc' t
```

```
val combine : ('a -> 'b -> 'b) -> 'b -> 'a list -> 'b = <fun>
```

```
val combine_tr : ('a -> 'b -> 'a) -> 'a -> 'b list -> 'a = <fun>
```

Pay close attention to the definition of `acc'`

, the new accumulator, in each
of those version:

In the original version, we procrastinate using the head element

`h`

. First, we combine all the remaining tail elements to get`acc'`

. Only then do we use`f`

to fold in the head. So the value passed as the initial value of`acc`

turns out to be the same for every recursive invocation of`combine`

: it’s passed all the way down to where it’s needed, at the right-most element of the list, then used there exactly once.But in the tail recursive version, we “pre-crastinate” by immediately folding

`h`

in with the old accumulator`acc`

. Then we fold that in with all the tail elements. So at each recursive invocation, the value passed as the argument`acc`

can be different.

The tail recursive version of combine works just fine for summation (and concatenation, which we elide):

```
let sum = combine_tr ( + ) 0
let s = sum [1; 2; 3]
```

```
val sum : int list -> int = <fun>
```

```
val s : int = 6
```

But something possibly surprising happens with subtraction:

```
let sub = combine ( - ) 0
let s = sub [3; 2; 1]
let sub_tr = combine_tr ( - ) 0
let s' = sub_tr [3; 2; 1]
```

```
val sub : int list -> int = <fun>
```

```
val s : int = 2
```

```
val sub_tr : int list -> int = <fun>
```

```
val s' : int = -6
```

The two results are different!

With

`combine`

we compute`3 - (2 - (1 - 0))`

. First we fold in`1`

, then`2`

, then`3`

. We are processing the list from right to left, putting the initial accumulator at the far right.But with

`combine_tr`

we compute`(((0 - 3) - 2) - 1)`

. We are processing the list from left to right, putting the initial accumulator at the far left.

With addition it didn’t matter which order we processed the list, because addition is associative and commutative. But subtraction is not, so the two directions result in different answers.

Actually this shouldn’t be too surprising if we think back to when we made `map`

be tail recursive. Then, we discovered that tail recursion can cause us to
process the list in reverse order from the non-tail recursive version of the
same function. That’s what happened here.

## 4.4.4. Fold Left#

Our `combine_tr`

function is also in the standard library under the name
`List.fold_left`

:

```
let rec fold_left f acc = function
| [] -> acc
| h :: t -> fold_left f (f acc h) t
let sum = fold_left ( + ) 0
let concat = fold_left ( ^ ) ""
```

```
val fold_left : ('a -> 'b -> 'a) -> 'a -> 'b list -> 'a = <fun>
```

```
val sum : int list -> int = <fun>
```

```
val concat : string list -> string = <fun>
```

We have once more succeeded in applying the Abstraction Principle.

## 4.4.5. Fold Left vs. Fold Right#

Let’s review the differences between `fold_right`

and `fold_left`

:

They combine list elements in opposite orders, as indicated by their names. Function

`fold_right`

combines from the right to the left, whereas`fold_left`

proceeds from the left to the right.Function

`fold_left`

is tail recursive whereas`fold_right`

is not.The types of the functions are different.

Regarding that final point, it can be hard to remember what those types are! Luckily we can always ask the toplevel:

```
List.fold_left;;
List.fold_right;;
```

```
- : ('a -> 'b -> 'a) -> 'a -> 'b list -> 'a = <fun>
```

```
- : ('a -> 'b -> 'b) -> 'a list -> 'b -> 'b = <fun>
```

To understand those types, look for the list argument in each one of them. That tells you the type of the values in the list. Then look for the type of the return value; that tells you the type of the accumulator. From there you can work out everything else.

In

`fold_left`

, the list argument is of type`'b list`

, so the list contains values of type`'b`

. The return type is`'a`

, so the accumulator has type`'a`

. Knowing that, we can figure out that the second argument is the initial value of the accumulator (because it has type`'a`

). And we can figure out that the first argument, the combining operator, takes as its own first argument an accumulator value (because it has type`'a`

), as its own second argument a list element (because it has type`'b`

), and returns a new accumulator value.In

`fold_right`

, the list argument is of type`'a list`

, so the list contains values of type`'a`

. The return type is`'b`

, so the accumulator has type`'b`

. Knowing that, we can figure out that the third argument is the initial value of the accumulator (because it has type`'b`

). And we can figure out that the first argument, the combining operator, takes as its own second argument an accumulator value (because it has type`'b`

), as its own first argument a list element (because it has type`'a`

), and returns a new accumulator value.

Tip

You might wonder why the argument orders are different between the two `fold`

functions. Good question. Other libraries do in fact use different argument
orders. One way to remember it for OCaml is that in `fold_X`

the accumulator
argument goes to the `X`

of the list argument.

If you find it hard to keep track of all these argument orders, the
`ListLabels`

module in the standard library can help. It uses
labeled arguments to give names to the combining operator (which it calls `f`

)
and the initial accumulator value (which it calls `init`

). Internally, the
implementation is actually identical to the `List`

module.

```
ListLabels.fold_left;;
ListLabels.fold_left ~f:(fun x y -> x - y) ~init:0 [1;2;3];;
```

```
- : f:('a -> 'b -> 'a) -> init:'a -> 'b list -> 'a = <fun>
```

```
- : int = -6
```

```
ListLabels.fold_right;;
ListLabels.fold_right ~f:(fun y x -> x - y) ~init:0 [1;2;3];;
```

```
- : f:('a -> 'b -> 'b) -> 'a list -> init:'b -> 'b = <fun>
```

```
- : int = -6
```

Notice how in the two applications of fold above, we are able to write the arguments in a uniform order thanks to their labels. However, we still have to be careful about which argument to the combining operator is the list element vs. the accumulator value.

## 4.4.6. A Digression on Labeled Arguments and Fold#

It’s possible to write our own version of the fold functions that would label the arguments to the combining operator, so we don’t even have to remember their order:

```
let rec fold_left ~op:(f: acc:'a -> elt:'b -> 'a) ~init:acc lst =
match lst with
| [] -> acc
| h :: t -> fold_left ~op:f ~init:(f ~acc:acc ~elt:h) t
let rec fold_right ~op:(f: elt:'a -> acc:'b -> 'b) lst ~init:acc =
match lst with
| [] -> acc
| h :: t -> f ~elt:h ~acc:(fold_right ~op:f t ~init:acc)
```

```
val fold_left : op:(acc:'a -> elt:'b -> 'a) -> init:'a -> 'b list -> 'a =
<fun>
```

```
val fold_right : op:(elt:'a -> acc:'b -> 'b) -> 'a list -> init:'b -> 'b =
<fun>
```

But those functions aren’t as useful as they might seem:

```
let s = fold_left ~op:( + ) ~init:0 [1;2;3]
```

```
File "[17]", line 1, characters 22-27:
1 | let s = fold_left ~op:( + ) ~init:0 [1;2;3]
^^^^^
Error: This expression has type int -> int -> int
but an expression was expected of type acc:'a -> elt:'b -> 'a
```

The problem is that the built-in `+`

operator doesn’t have labeled arguments,
so we can’t pass it in as the combining operator to our labeled functions.
We’d have to define our own labeled version of it:

```
let add ~acc ~elt = acc + elt
let s = fold_left ~op:add ~init:0 [1; 2; 3]
```

But now we have to remember that the `~acc`

parameter to `add`

will become
the left-hand argument to `( + )`

. That’s not really much of an improvement
over what we had to remember to begin with.

## 4.4.7. Using Fold to Implement Other Functions#

Folding is so powerful that we can write many other list functions in terms of
`fold_left`

or `fold_right`

. For example,

```
let length lst =
List.fold_left (fun acc _ -> acc + 1) 0 lst
let rev lst =
List.fold_left (fun acc x -> x :: acc) [] lst
let map f lst =
List.fold_right (fun x acc -> f x :: acc) lst []
let filter f lst =
List.fold_right (fun x acc -> if f x then x :: acc else acc) lst []
```

```
val length : 'a list -> int = <fun>
```

```
val rev : 'a list -> 'a list = <fun>
```

```
val map : ('a -> 'b) -> 'a list -> 'b list = <fun>
```

```
val filter : ('a -> bool) -> 'a list -> 'a list = <fun>
```

At this point it begins to become debatable whether it’s better to express the
computations above using folding or using the ways we have already seen. Even
for an experienced functional programmer, understanding what a fold does can
take longer than reading the naive recursive implementation. If you peruse the
source code of the standard library, you’ll see that none of the
`List`

module internally is implemented in terms of folding, which is perhaps
one comment on the readability of fold. On the other hand, using fold ensures
that the programmer doesn’t accidentally program the recursive traversal
incorrectly. And for a data structure that’s more complicated than lists, that
robustness might be a win.

## 4.4.8. Fold vs. Recursive vs. Library#

We’ve now seen three different ways for writing functions that manipulate lists:

directly as a recursive function that pattern matches against the empty list and against cons,

using

`fold`

functions, andusing other library functions.

Let’s try using each of those ways to solve a problem, so that we can appreciate them better.

Consider writing a function `lst_and: bool list -> bool`

, such that
`lst_and [a1; ...; an]`

returns whether all elements of the list are `true`

.
That is, it evaluates the same as `a1 && a2 && ... && an`

. When applied to an
empty list, it evaluates to `true`

.

Here are three possible ways of writing such a function. We give each way a slightly different function name for clarity.

```
let rec lst_and_rec = function
| [] -> true
| h :: t -> h && lst_and_rec t
let lst_and_fold =
List.fold_left (fun acc elt -> acc && elt) true
let lst_and_lib =
List.for_all (fun x -> x)
```

```
val lst_and_rec : bool list -> bool = <fun>
```

```
val lst_and_fold : bool list -> bool = <fun>
```

```
val lst_and_lib : bool list -> bool = <fun>
```

The worst-case running time of all three functions is linear in the length of the list. But:

The first function,

`lst_and_rec`

has the advantage that it need not process the entire list. It will immediately return`false`

the first time they discover a`false`

element in the list.The second function,

`lst_and_fold`

, will always process every element of the list.As for the third function

`lst_and_lib`

, according to the documentation of`List.for_all`

, it returns`(p a1) && (p a2) && ... && (p an)`

. So like`lst_and_rec`

it need not process every element.