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 . tailAnd (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
120In 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.
1 comment:
Thanks for sharing
Internship providing companies in chennai | Where to do internship | internship opportunities in Chennai | internship offer letter | What internship should i do | How internship works | how many internships should i do ? | internship and inplant training difference | internship guidelines for students | why internship is necessary
Post a Comment