16 Jan 2009

Project Euler problem 2 using Scala

I wanted to use Haskell's zipWith funtion to solve Euler's problem 2 using Scala. This provides an elegant way to generate Fibonacci sequences lazyily, as described here. However, no function zipWith is yet available in Scala until version 2.8.0, according to this ticket. On of Scala's beauties is that, if a function on a class is not available, you can easily add it yourself using an implicit function.
Code below is largely stolen from this post by Jorge Ortiz, in which he also explains in the functions and classes in more detail. My simple addition is just another bit of library pimping, by adding an implicit withZip function:


class Euler2 {

implicit def streamWithZipWith(stream: Stream[Int]) = new {
def zipWith(that: Stream[Int])(f: (Int, Int)=>Int) = {
stream zip that map { case (x, y) => f(x, y) }
}
}

def fib: Stream[Int] = {
lazy val fibs: Stream[Int] = Stream.cons(0, Stream.cons(1, (fibs.zipWith(fibs.tail)(_ + _)) ))
fibs
}

}

object Euler2 {

implicit def iterableWithSum(it: Iterable[Int]) = new {
def sum = it.foldLeft(0)(_ + _)
}

def main(args: Array[String]): Unit = {
val fibStream = new Euler2().fib
fibStream.take(10).print
fibStream.filter(_ % 2 == 0).takeWhile(_ <= 1000000).sum
}
}




The Stream class is handy to construct a List of elements that are evaluated lazily, i.e. only when they are actually needed. This allows us to construct an infinite list definition, and later only use a subset of our infinite list for the real calculation.

The zipWith implicit function definition, is defined so that we can call it on our fibs Stream variable. Our zipWith function operates on two Streams, first zips them, which creates a Stream of tuples of elements in both streams. On that resulting tuple Stream, the map function is applied to each tuple. The function that is applied is passed on as an argument. In our case what we want is to add the two elements from the tuple to construct the fibonacci sequence. Basically the same code as in Jorge's post, but it shows how you can quickly and cleanly add your desired functions to an existing class.

No comments:

Post a Comment