How to fix my Fibonacci stream in Scala

8
votes

I defined a function to return Fibonacci stream as follows: 

def fib:Stream[Int] = {
  Stream.cons(1,
    Stream.cons(2,
      (fib zip fib.tail) map {case (x, y) => println("%s + %s".format(x, y)); x + y}))
}

The functions work ok but it looks inefficient (see the output below)

scala> fib take 5 foreach println
1
2
1 + 2
3
1 + 2
2 + 3
5
1 + 2
1 + 2
2 + 3
3 + 5
8

So, it looks like the function calculates the n-th fibonacci number from the very beginning. Is it correct? How would you fix it?

2
scalastreamfibonacci

2 Answers

19
votes

That is because you have used a def. Try using a val:

lazy val fib: Stream[Int] 
  = 1 #:: 2 #:: (fib zip fib.tail map { case (x, y) => x + y })

Basically a def is a method; in your example you are calling the method each time and each time the method call constructs a new stream. The distinction between def and val has been covered on SO before, so I won't go into detail here. If you are from a Java background, it should be pretty clear.

This is another nice thing about scala; in Java, methods may be recursive but types and values may not be. In scala both values and types can be recursive.

14
votes

You can do it the other way: 


lazy val fibs = {
  def f(a: Int, b: Int): Stream[Int] = a #:: f(b, a + b)
  f(0, 1)
}