## fold_right and fold_left

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`init`

argument 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`