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?

Improve this question

2 Answers 2

Reset to default
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)
Improve this answer
Sign up to request clarification or add additional context in comments.

1 Comment

The Stream documentation - scala-lang.org/api/current/… - 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 }
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.

Improve this answer

1 Comment

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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.