Understanding Scala Streams through Fibonacci

I took a look at Scala Streams tonight (or was that last night? When am I posting this?) and thought I’d share what I learned from Literate Programs and the Scala source code.

Streams

For the uninitiated, a Stream in Scala helps realize one of the fundamental concepts of Functional Programming, that of laziness. In essence, a Stream as infinite – think of a asinine to construct the entire collection before ever using it as that would only ensure that you never used it. A Stream is evaluated on an as-needed basis and only up to the point that you need it.

The Delicious, Delicious Code…

Let’s illustrate using good ol’ the Literate Programs website but I’m hoping to explain it in a bit more depth, and not get it too wrong in the process)

import scala.math.BigInt

lazy val fibs: Stream[BigInt] = BigInt(0) #::

BigInt(1) #::

fibs.zip(fibs.tail).map { n => n._1 + n._2 }

(Note: The above must all be on one line or the compiler is going to have a tough time pimping it out)

Sweet and delicious, no?

Dissection

Let’s break it down:

lazy

val fibs: Stream[BigInt]

BigInt(0) #:: BigInt(1) #::

If you look at the Stream api you won’t find the #:: member function anywhere, and indeed you shouldn’t as we’re not working with a Stream right now, but a BigInt.

So with that realization in place, we must also recognize that methods ending in : are right associative. What this means is that the object we’re calling the #:: method on is actually the Stream object that is returned from the map command at the end of the call (we’ll get back to that, just hang on). Remember how we had to declare that fibs was a Stream instead of letting Scala infer it? Well, that’s (one of the reasons) why we need to do that.

Now we know that the method is being called on the Stream but when we look at the api for Stream, again we don’t see that method call. So where is it?

Page 1 of 2 | Next page