Understanding Scala Streams through Fibonacci

This method gets pimped on through the implicit def consWrapper[A](stream: => Stream): ConsWrapper[A] method defined on the Stream companion object. Scala will resolve the lack of a #:: method on Stream by finding an implicit conversion to a type that does have that method, and this is the by-name parameter. This means that it’s not invoked until it’s used.

Wow, that’s a lot of stuff for one bullet point.

fibs.zip(fibs.tail)

You didn’t read it, did you? Fine… on your own head, be it.

The size of the Stream returned by tail is one-less than the size of the Stream itself. This means that the zipped result is going to be the size of the Stream returned by tail, not the size of the Stream itself. So, in the initial case (where the Stream is Stream(0, 1, [Stream]), the zipped result is actually Stream((0, 1), ([Stream])) because the tail, of one element, is paired with the head.

Stream.zip creates a Cons cell containing (this.head, that.head) as the Cons head and (this.tail zip that.tail) as the Cons tail but as a Stream of (A1, B) so we’re not evaluating it now – we’ll evaluate it when it gets called.

map { n => n._1 + n._2 }

Use it

Ok, so what happens when we evaluate it? Let’s get the first 20 numbers:

scala> fibs take 20 foreach println

0

1

1

2

3

5

8

13

21

34

55

89

144

233

377

610

987

1597

2584

4181

scala>

That looks right to me.

WTF?

Some of you may still be scratching your heads because I wasn’t terribly clear on how this actually works. How is it that each number is evaluated as needed? Well, first let’s prove that it is so. I’m going to modify the code slightly.

import scala.math.BigInt

lazy val fibs: Stream[BigInt] =

BigInt(0) #::

BigInt(1) #::

fibs.zip(fibs.tail).map(n => {

println("Evaluating: %s -> %s".format(n._1, n._2))

n._1 + n._2

})

Now let’s take the first 5:

scala> fibs take 5 foreach println

0

1

Evaluating: 0 -> 1

1

Evaluating: 1 -> 1

2

Evaluating: 1 -> 2

3

scala>

And let’s take them again…

scala> fibs take 5 foreach println

0

1

1

2

3

scala>

And let’s take the first 7…

scala> fibs take 7 foreach println

0

1

1

2

3

Evaluating: 2 -> 3

5

Evaluating: 3 -> 5

8

scala>

Ok, so it works; things are properly evaluated in a lazy manner. But how?

Why…

The culprit behind this magic appears to be the interplay between the Cons class, the StreamIterator class and the LazyCell class:

final class Cons[+A](hd: A, tl: => Stream[A]) extends Stream[A]

// Note that the head is a value of type A and the tail is a by-name Stream

final class StreamIterator[+A](self: Stream[A]) extends Iterator[A] {

class LazyCell(st: => Stream[A]) {

// Note the laziness

lazy val v = st

}

private var these = new LazyCell(self)

def next: A =

if (isEmpty) Iterator.empty.next

else {

// Evaluate the laziness

val cur = these.v

// And the concrete value of type A

val result = cur.head

// Assign the next lazy cell to be the Stream in the tail

these = new LazyCell(cur.tail)

result

}

}

Couple that together with the recursively defined zip we saw earlier, and you’ve got your lazy Stream of Fibonacci numbers.

I love this stuff…

Page 2 of 2 | Previous page