5

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?

2 Answers2

12

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)
drexin
  • 24,225
  • 4
  • 67
  • 81
  • 5
    The Stream documentation - http://www.scala-lang.org/api/current/index.html#scala.collection.immutable.Stream - gives several examples of how to write fib, my favorite of which is: val fibs: Stream[BigInt] = BigInt(0) #:: BigInt(1) #:: fibs.zip(fibs.tail).map { n => n._1 + n._2 } – Chris Martin Jun 08 '13 at 17:53
1

While @drexin's answer is generally correct, you might want to use a lazy val instead of just a val in some cases; see here for some more information on lazy vals.

Community
  • 1
  • 1
Ptharien's Flame
  • 3,246
  • 20
  • 24
  • 4
    I don't think that is a good idea when dealing with infinite streams. In general, once you get your result out of the stream, you want the JVM to garbage collect the stream. Using a lazy val will prevent that. – huynhjl Jun 09 '13 at 13:18