The Beta Things: Lazy Fibonacci stream in Scala

2008/10/04

I tried to create a lazy infinite Fibonacci stream using Scala, here are my two solutions.

The first one is a naive one using inner function:


def fib:Stream[Long]={
  def fibInner(f0:Long, f1:Long):Stream[Long]={
    Stream.cons(f0, fibInner(f1, f0+f1))
  }
  fibInner(1,2)
}

The second one is ported from Haskell:


def fib2:Stream[Long]={
  Stream.cons(1, Stream.cons(2, fib2.zip(fib2.tail).map(x=>x._1+x._2)))
}

Although both of them works but the second one is way slower than the first one.

Anonymous 25/2/11 22:38: I'd also come up with the Haskell ported version, and was very disappointed with the performance. There's clearly something not being done lazily there, but I'm not sure what.

I like your other solution. You can change all your Longs to BigInts and then you can easily calculate the 10000th fibonnacci number.
Anonymous 7/6/11 02:07: Second solution should be:
lazy val fib2:Stream[Long]=
Stream.cons(1, Stream.cons(2, fib2.zip(fib2.tail).map(x=>x._1+x._2)))
Current second solution recomputes every value every time. This solution is properly lazy