Friday, October 23, 2015

FoldRight in terms of foldLeft

Here is how to implement foldRight in terms of foldLeft in Scala:

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)

Instead of computing the values, it builds up a function, and then feed the initial value z to that function. This can be better explained in a diagram:

b f ( a 0 , b ) id a 0 a 1 b f ( a 0, f ( a 1 , b ) )

0 comments: