How does the lazy 'take' function compute the Scala stream further?

Question

In Martin Odersky’s book “Programming in Scala” there is an example of computing the Fibonacci sequence starting with 2 numbers passed as arguments to the function fibFrom.

def fibFrom(a: Int, b: Int): Stream[Int] =
       a #:: fibFrom(b, a + b)

If you apply the method take() to this recursive function like:

fibFrom(1, 1).take(15).print

The output will be:

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, empty

Maybe this output is obvious for more experienced people, but I don’t understand how exactly this method take() makes the stream to be calculated further. Is 15 somehow nonobviously passed into fibFrom()?

score 3 · Answer 1 · answered Mar 27 '20 at 12:19

I think the thing that should be pointed is that Stream is lazily evaluated:

The class Stream implements lazy lists where elements are only evaluated when they are needed.

Quoted from scala-lang.org

fibFrom function is returning a Stream, so we understand that the function won't do nothing, even when called; it will start calculating the numbers only when you try to access the Stream.
take function also returns a Stream and acts lazily.
The print function is the one that actually calls the recursion and stops when filling the output with 15 numbers (like your example).

You can easily check this by performing the functions one by one and see the output.
Lets run only fibFrom:

We can see that the returned value is a Stream and the numbers are not calculated yet.

Now, lets see what take(15) does:

Same as our first test.

Eventually, performing print is giving us the desired result thus actually running fibFrom recursively until reaching 15 numbers:

Bonus: Converting the Stream to any non lazy data structure will trigger the computations:

score 2 · Accepted Answer · answered Mar 27 '20 at 11:52

With

a #:: fibFrom(b, a + b)

you created Stream object, and that object has head which is Int and tail which is function. Take is function of Stream that will calculate 15 elements using tail and head. You can check source code of take() function:

  override def take(n: Int): Stream[A] = (
    // Note that the n == 1 condition appears redundant but is not.
    // It prevents "tail" from being referenced (and its head being evaluated)
    // when obtaining the last element of the result. Such are the challenges
    // of working with a lazy-but-not-really sequence.
    if (n <= 0 || isEmpty) Stream.empty
    else if (n == 1) cons(head, Stream.empty)
    else cons(head, tail take n-1)
  )

How does the lazy 'take' function compute the Scala stream further?

2 Answers2