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
Best Answer
Let's have a look at
(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 fromB
toB
. The fold step takes a value of typea: A
and a functiong: B => B
and produces a new function(b => g(f(b,a))): B => B
. This function can be expressed as a composition ofg
withf(_, a)
:We can view the process as follows: For each element
a
ofl
we take the partial applicationb => f(b,a)
, which is a functionB => 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 onz
. 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
Now let's compute what happens when we pass it
List(1,2)
:Applying this function to
z
yieldsas required.