Sixian Li

credits: textbook from Cornell’s cs 3110.

Some useful explanations for fold functions in OCaml.

fold_right

Let’s start with two functions: sum and concat

We notice that these two functions are very similar. The only differences are the base case value (0 and "") and the operator (+ and ^).

We love excerptions. So we rewrite these two functions as

Why is it called fold_right?

Because the associativity is from right to left like this:

(a+(b+(c+0)))

fold_left

Similarly, the associativity, as its name suggests, is ((a+0)+b)+c). It is actually a handy function for tail recursion.

It is implemented like this:

fold_left op acc(base case) list

In fold_right, you will notice that the value passed as the initargument is the same for every recursive invocation of fold_right: 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 fold_left, you will notice that at each recursive invocation, the value passed as the argument acc can be different.

NOTE: In fold_left, its type is:

('a -> 'b -> 'a) -> 'a -> 'b list -> 'a = <fun> In the example rev below, the function is fun l a instead of fun a l

Examples