Getting stack overflow error when trying Haskell-style lazy evaluation in Scala

Question

To practice, I'm writing some useless methods/functions in Scala. I'm trying to implement a fibonacci sequence function. I wrote one in Haskell to use as a reference (so I don't just end up writing it Java-style). What I've come up with in Haskell is:

fib a b = c : (fib b c)
   where c = a+b

Then I can do this:

take 20 (fib 0 1)
[1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765,10946]

So I tried translating this to Scala:

def fib(a:Int, b:Int):List[Int] = {
  val c = a+b
  c :: fib(b,c)
}

But I get a stack overflow error when I try to use it. Is there something I have to do to get lazy evaluation to work in Scala?

drexin drexin · Accepted Answer · 2013-06-08T17:17:46

Lists in scala are not lazily evaluated. You have to use a stream instead:

def fib(a:Int, b:Int): Stream[Int] = {
  val c = a+b
  c #:: fib(b,c)
}

scala> fib(0,1) take 20 toList
res5: List[Int] = List(1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946)

Getting stack overflow error when trying Haskell-style lazy evaluation in Scala

2 Answers