Fix from Fold

My two previous posts, Fold Right from Fold Left and Folding Stream with Scala are actually my interpretation to (Hutton, 1999) paper. Now, I would like to continue with another paper (Pope, 2010 ?) that also talks about fold. Note that, Pope's work cites of  Hutton's work.

This post ends my fold trilogy. It has been an exciting and fun to play with.  I would love to continue with scalaz Fold (Foldr, Foldl, FoldMap Foldable are interesting), but I think I have to stop having fun :-)

Yet Another dropWhile Implementation

In Folding Stream with Scala , I implemented dropWhile using fold using (Hutton, 1999) paper. Pope proposes two more implementations, both work very well with infinite stream.

First, a reminder of fold implementation:

def foldr[A, B](combine:(A, =>B) => B, base:B)(xs:Stream[A]): B = { 
    if (xs.isEmpty) base 
    else combine(xs.head, foldr(combine, base)(xs.tail)) 
  } 

And here is the solution:

  def dwHo[A](pred:A=>Boolean, xs:Stream[A]):Stream[A]=>Stream[A] = { 
    val id =(s:Stream[A])=>s 
    val tail= (s:Stream[A])=>s.tail 
 
    def combine(next:A, rec: =>Stream[A]=>Stream[A]) = { 
     if (pred(next)) (rec compose tail) 
     else id 
    } 
    foldr(combine, id)(xs) 
  }

Example:

  scala> val xs = Stream.range(20, 120) 
  xs: scala.collection.immutable.Stream[Int] = Stream(20, ?) 
  scala> dwHo( (_:Int)<100, xs)(xs).toList 
  res33: List[Int] = List(100, 101, 102, 103, 104, 105, 106, 107, 108, 109, 110, 111, 112, 113, 114, 115, 116, 117, 118, 119) 

It also works with infinite Stream:

scala> val ys = Stream.from(1) 
ys: scala.collection.immutable.Stream[Int] = Stream(1, ?) 
scala> dwHo( (_:Int)<5, ys)(ys).take(10).toList 
res38: List[Int] = List(5, 6, 7, 8, 9, 10, 11, 12, 13, 14)

Under the hood, here is what happen:

foldr combine id [1..] 
 =combine 1 (foldr combine id [2..]) = 
 =(foldr combine id [2..]) . tail 
 =(combine 2 (foldr combine id [3..]) . tail 
 =(foldr combine id [3..]) .tail . tail 
 =(combine 3 (foldr combine id [4..]) . tail . tail 
 =(foldr combine id [4..]) .tail . tail . tail 
 =(combine 4 (foldr combine id [5..]) . tail . tail . tail 
 =(foldr combine id [5..]) . tail . tail . tail . tail 
 =(combine 5 (foldr combine id [6..]) . tail . tail . tail 
 =id . tail . tail . tail . tail

And (id.tail.tail.tail.tail)[1..] = [5..].

Fix from Fold
The most interesting part of the (Pope, 2010) is not on dropWhile though, but on an implementation of a function using fold. The function is called fix, also known as Y combinator. Check this page to have an idea of what fix function is.

Basically, using fix, we can encode recursion function. The following is an example of factorial function using fix in haskell:

Prelude> :m Control.Monad.Fix 
Prelude Control.Monad.Fix> fix (\rec n -> if n == 0 then 1 else n * rec (n-1)) 5  

120
In Scala, fix function is implemented in a much trickier way. The difficulties come from the Scala strictness. Here is the implementation of fix I found after googling a little bit:

def fix[A](f: (A=>A)=>(A=>A)): A=>A = f(fix(f))(_)

Example:
scala> fix[Long](f=>x=> if (x == 0) 1 else x * f(x - 1))(5)

res5: Long = 120

One question that may arise is whether fold can be implemented using fix. Well, apparently, yes, after all, it's a recursion, but I haven't tried it yet. A more interesting question would be if fix can be implemented using fold. The answer is yes, and that's the essence of (Pope, 2010) article. Here is the implementation of fix using foldr in Scala:

def fix[A](f: (A=>A)=>(A=>A)): A=>A = { 
  def combine( a:(A=>A)=>(A=>A), b: =>A=>A):A=>A = f(b)(_) 
  foldr(combine, null)(Stream.continually(null)) 
}

Give a try:

scala> fix[Long](f=>x=> if (x == 0) 1 else x * f(x - 1))(5) 
res6: Long = 120

Youpi..., isn't it awesome? This shows how expressive fold is, since it can now be used to implement (any?) recursion functions.

References

• Hutton G (1999) A tutorial on the universality and expressiveness of fold. Available from http://www.cs.nott.ac.uk/~gmh/fold.pdf 

• Pope B (2010 ?)  Getting a Fix from the Right Fold. Available from: http://www.haskell.org/wikiupload/1/14/TMR-Issue6.pdf . There is one other dropWhile solution in this paper that I dumped here: https://gist.github.com/1195982.

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.