Let's have a look at
def foldLeftViaFoldRight[A,B](l: List[A], z: B)(f: (B,A) => B): B =
foldRight(l, (b:B) => b)((a,g) => b => g(f(b,a)))(z)
(the other fold is similar). The trick is that during the right fold operation, we don't build the final value of type B
. Instead, we build a function from B
to B
. The fold step takes a value of type a: A
and a function g: B => B
and produces a new function (b => g(f(b,a))): B => B
. This function can be expressed as a composition of g
with f(_, a)
:
l.foldRight(identity _)((a,g) => g compose (b => f(b,a)))(z);
We can view the process as follows: For each element a
of l
we take the partial application b => f(b,a)
, which is a function B => B
. Then, we compose all these functions in such a way that the function corresponding to the rightmost element (with which we start the traversal) is at far left in the composition chain. Finally, we apply the big composed function on z
. This results in a sequence of operations that starts with the leftmost element (which is at far right in the composition chain) and finishes with the right most one.
Update: As an example, let's examine how this definition works on a two-element list. First, we'll rewrite the function as
def foldLeftViaFoldRight[A,B](l: List[A], z: B)
(f: (B,A) => B): B =
{
def h(a: A, g: B => B): (B => B) =
g compose ((x: B) => f(x,a));
l.foldRight(identity[B] _)(h _)(z);
}
Now let's compute what happens when we pass it List(1,2)
:
List(1,2).foldRight(identity[B] _)(h _)
= // by the definition of the right fold
h(1, h(2, identity([B])))
= // expand the inner `h`
h(1, identity[B] compose ((x: B) => f(x, 2)))
=
h(1, ((x: B) => f(x, 2)))
= // expand the other `h`
((x: B) => f(x, 2)) compose ((x: B) => f(x, 1))
= // by the definition of function composition
(y: B) => f(f(y, 1), 2)
Applying this function to z
yields
f(f(z, 1), 2)
as required.