FoldLeft using FoldRight in scala

Question

While going through Functional Programming in Scala, I came across this question:

Can you right foldLeft in terms of foldRight? How about the other way around?

In solution provided by the authors they have provided an implementation as follows:

def foldRightViaFoldLeft_1[A,B](l: List[A], z: B)(f: (A,B) => B): B = 
    foldLeft(l, (b:B) => b)((g,a) => b => g(f(a,b)))(z)

  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)

Can somebody help me trace through this solution and make me understand how this actually gets the foldl implemented in terms of foldr and vice-versa?

Thanks

Answer 1

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.