8

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?

Michael
  • 10,185
  • 12
  • 59
  • 110

2 Answers2

19

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.

Community
  • 1
  • 1
oxbow_lakes
  • 133,303
  • 56
  • 317
  • 449
  • Thanks. It is interesting though, how to write a _function_ to return a Fibonacci stream anyway? – Michael Dec 28 '11 at 20:14
  • You already wrote one; but you are returning a different instance of the stream each time. Because scala has side-effects, the runtime cannot replace an expression with a single, lazily-computed value – oxbow_lakes Dec 29 '11 at 11:45
  • Ok. What if I need a function with arguments: e.g. `fib(f1:Int, f2:Int):Stream[Int]`, where `f1` and `f2` are the 1st and 2nd numbers of the sequence ? – Michael Dec 29 '11 at 11:52
  • Scala is not a referentially-transparent language. The runtime will not "cache" calls to your method. If you do not want to construct a new stream each time, either memoize the results, or extract into a val locally. – oxbow_lakes Dec 31 '11 at 19:37
  • What do you think about `def fib(f1:Int, f2:Int):Stream[Int] = Stream.cons(f1, fib(f1, f1 + f2))` as in the response below? It looks efficient. – Michael Jan 01 '12 at 12:22
14

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)
}
S. Kucherenko
  • 585
  • 3
  • 8
  • the outer one should just be a def. Then you can have precise control over the stream that is returned and be able to drop that reference when you want to. For example, if you just wanted a stream that started with the 100,000th fib number, then you could do `val bigs = fibs drop 100000 take n`, and bigs wouldn't hold the first 100000 in memory. – Zak Patterson Feb 20 '14 at 19:16