Fold Again: Fold Left using Fold Right

In my previous post, I have shown how fold can be used to implement other collection methods, like filter, map, length, reverse, or even dropWhile and break.

We wonder now whether it is possible to implement fold left using fold right. The article (Hutton, 1999) shows indeed that it is possible. The objective of this post is then to show it in Scala and discuss a little bit about fold universality.

Before implementing fold left using fold right, let's implement something simpler. Let's implement suml, a function that is similar to sum we discussed in the previous post. Instead of summing from right to left, we want suml to sum from left to right.

The following illustrates the difference between sum and suml:

   1 sum(Stream(1, 2, 3, 4))= 1 + (2 + (3 + 4))
   2 suml(Stream(1, 2, 3, 4))= (((1 + 2) + 3) + 4)
   3 

As described in (Hutton, 1999), it turns out that we can't directly implement suml using fold. What possible is to define suml_ that returns a function Int=> Int. Here is the implementation:

   1 def suml_(xs:Stream[Int]) = {
   2     def combine(x:Int, g: =>Int=>Int) = (acc:Int)=>g(acc +x)
   3     foldr(combine, (x:Int)=>x)(xs)
   4 }
   5 def sum(xs:Stream[Int])=suml_(xs)(0)

When suml_(Stream(1, 3, 4, 5)) is called, it returns actually

((_:Int) + 5) compose ((_:Int) + 4) 

compose ((_:Int) + 3) compose ((_:Int)+ 1) 

compose ( (x:Int)=>x)

Note that, the returned function is actually an Int=>Int function, and when it receives 0 as its input, it returns (((1 + 3) + 4) + 5) = 13. Also note a special function, the identity function (x:Int)=>x.

OK, Great. What about foldl? Well, it is the generalization of suml above. Here is the foldl implementation:

   1 def foldl_[A,B](f: (A,B)=>B, xs:Stream[A]) = {
   2    def combine(x: A, g: =>B=>B) = (acc:B)=> g(f(x,acc)) 
   3    foldr(combine, (a:B)=>a)(xs)
   4 }
   5 def foldl[A,B](f:(A,B)=>B, base:B, xs:Stream[A]) = foldl_(f,xs)(base)
   6 

Let's give a shot:

   1 scala> foldl( (_:Int) + (_:Int), 0, Stream(1, 3, 4, 5))
   2 res1: Int = 13
   3 
   4 scala> foldl( (_:Int) * (_:Int), 1, Stream(1, 3, 4, 5))
   5 res2: Int = 60

Excellent. But, all this looks like a magic, right? Is there a systematic way to derive a implementation of a function using fold? Fortunately, yes. Here we come to the most interesting part of (Hutton, 1999).

Fold Universality and  Fusion Property of Fold

Two  important concepts explained in (Hutton, 1999) is fold universality and fusion property of fold.

The fold universality states that the two Scala code below are equivalent:
Code 1

   1 def g[A,B](xs: Stream[A], f:(A, B)=>B, v:B): B = 
   2   if (xs.isEmpty) v else 
   3   f(xs.head, g(xs.tail, f, v))

Code 2

   1 def g[A,B](xs:Stream[A], f:(A,B)=>B, v:B) = foldr(f,v)(xs)
   2 

Or more concise, in haskell symbols:

   1 g[]     = v
   2                       <=>   g = fold f v
   3 g(x:xs) = f x (g xs)    

And the fusion property of fold states the following:

1 h w = v
2                          => h . fold g w = fold f v
3 h(g x y) = f x (h y)

Let's have examples.

First, let's see how universal property of fold is useful to derive an implementation of a function using fold.

We will start with the recursive definition of foldl:

1 foldl     [] f v  = v
2 foldl (x:xs) f v  = foldl xs f (f v x) 

In scala:

1 def foldl[A,B](xs:Stream[A], f:(B,A)=>B, v:B): B = {
2    if (xs.isEmpty) v
3    else foldl(xs.tail, f, f(v, xs.head))
4 }

Unfortunately, foldl does not match directly with universal property definition. We need then an auxiliary method foldl_ :

1 def foldl_[A,B](xs:Stream[A]) = foldl[A,B](xs:Stream[A], (_:(B,A)=>B), (_:B))

That is, foldl function without the last two parameters.

We're ready to use universal property now:
foldl_ [] = v
foldl_ (x:xs) = f x (foldl_ xs)

Here, v is the identity function =id.

{Functions}
foldl_ (x:xs) g a = f x (foldl_ xs) g a
<=>
{Definition of foldl}
foldl_ xs g (g a x) = f x (foldl_ xs) g a
<=>
{Generalizing foldl_ xs = h}
h g (g a x) = f x h g a
<=>
f = (λx h -> (λa -> h(g a x)))

So, we got:
foldl xs f v = foldr((λx h -> (λa -> h(g a x)))) id xs v

When translated to Scala, we obtain the code explained at the beginning of the post.

***

Now, go for fusion property. Recall our map definition defined in the previous post (I modified a little bit):

   1 def map[A,B](f1:A=>B) = {
   2    def combine(x:A, xs:Stream[B]) = f1(x) #:: xs
   3    foldr(combine, Stream.empty)
   4 }

Note that the combine function can be represented as λx xs->f1 x : xs .

We would like to (a little bit informally) prove that map(f1) compose map(f2) =  map(f1 compose f2).
From the equation, we can substitute:
h = map(f1)
g = λx xs->f2(x):xs
w = v = Stream.empty = []
f = f1 compose f2

But,
map(f1) [] = []
map(f1) (g(x,xs)) = map(f1) ( f2(x):xs )
                  = (f1 compose f2)(x):map(f1)(xs)

So, the equation map(f1) compose map(f2) =  map(f1 compose f2)indeed holds.