fold_right and fold_left
credits: textbook from Cornell’s cs 3110.
Some useful explanations for
fold functions in OCaml.
Let’s start with two functions:
We notice that these two functions are very similar. The only differences are the base case value (
"") and the operator (
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:
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
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
acccan be different.
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