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 theinit
argument is the same for every recursive invocation offold_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 infold_left
, you will notice that at each recursive invocation, the value passed as the argumentacc
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