Month: May 2016

That Fibonacci function in detail…

Posted by – May 3, 2016

Some time ago I gave an answer on StackOverflow is to a question about producing a Fibonacci sequence, which asked if there is an “elegant way to do this in Scala”.

My solution was this:


val fibs: Stream[Int] = 0 #:: fibs.scanLeft(1)(_ + _)

Funnily enough, none of the comments on this confusing-looking snippet of code asked exactly how it worked. Maybe people are too embarrassed to ask. But I don’t think it’s really very obvious, so here’s an explanation. I’ll type slowly…

The short answer:

The result of scanLeft is by definition a sequence consisting of the accumulator at each step of the calculation, starting with its initial value.

For each step, the accumulator and an element of the collection are combined using the supplied function, producing a new accumulator value that is used in the following step.

In our function, calculating element ei will take element ei-2 (since we already have the first two values from the 0 provided, and 1, the initial accumulator), and combine with the current accumulator. The current accumulator has been output by scanLeft as ei-1, hence in effect we are adding the previous two elements together to provide the following one.

In detail…

The Fibonacci sequence

In case you don’t know, the Fibonacci sequence is a sequence of numbers that crops up in nature and mathematics. The important thing about it for our purposes is that it’s easy to define: start with the numbers 0 and 1, then each subsequent term is the sum of the previous two. So the next one would be 0 + 1 = 1, then 1 + 1 = 2, then 1 + 2 = 3, then 2 + 3 = 5, then 3 + 5 = 8, and so on, creating the following:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55…

The solution

Let’s break the code up and describe what each word does. Simple bits first. Skip ahead if you know it already.

val means we’re defining a value (a variable as it’s known in other languages, except here it’s immutable, so “variable” wouldn’t be such a great bit of terminology), which we’re calling fibs.

: precedes a type annotation, where we describe the type of fibs. Type annotations are for showing anyone reading the code the type without having to look at the definition, and also as a sanity check on your definition. Normally this is optional, but because this value is recursive (fibs also appears on the right hand side of the = sign), the compiler requires the extra help.

Stream[Int] is the actual type of fibs. A Stream is like an everyday linked List, except it’s lazy, i.e. we only know what the first element (the head) is, and the rest (the tail) will only be calculated as far as needed if and when we access it. This allows us to describe infinite sequences (though Streams can also be of finite length). The [Int] part is the Stream’s type parameter, required because there is a type parameter in the class definition. It lets us and the compiler know the type of the elements in the Stream.

0 is just a plain old Int literal: the first element of our Stream.

#:: is the Stream cons operator. It’s the equivalent to :: in List, i.e. it’s a prepend method to insert an element at the start of the Stream. Because it ends in the character ’:’, it’s right-associative, so it’s called on the object to the right (here, a Stream, since that’s what Stream’s scanLeft method returns), with the argument being the 0 to the left.

Actually… it’s a bit more complicated than this, since if you check the Stream documents, there’s no mention of a method called #::. The method is supplied via an implicit conversion to a class called ConsWrapper. Why? Because if it wasn’t, the Stream would itself need to be evaluated before we can call the prepend method, which would mean our resulting Stream (our 0 plus the result of scanLeft) now has at least the first two elements calculated, which is not what we want. This implicit conversion method is found on the Stream companion object:

implicit def consWrapper[A](stream: ⇒ Stream[A]): ConsWrapper[A]

It’s in scope because companion objects are one of the places that the compiler looks for implicit conversions.

So our snippet above is converted by the compiler to:

val fibs: Stream[Int] = 0 #:: Stream.consWrapper(fibs.scanLeft(1)(_ + _))

Importantly, the parameter “stream” in the implicit conversion is by-name, indicated by the “=>” before its type. This means that the argument is not actually evaluated, but only its name is passed – which is effectively a function that evaluates and returns the value each time it is used. Hence in the following:

def foo(x: ⇒Int) = {
  Thread.sleep(100)
  println("Start")
  Thread.sleep(100)
  println(x)
  Thread.sleep(100)
  println(x)
}
foo({println("Evaluating"); 42})

The output is:

Start
Evaluating
42
Evaluating
42

Notice:

1) Evaluation of the {code block} does not occur before it passed to foo, as method arguments normally would be. It’s first evaluated at the first place in the receiving method foo where the value x is used

2) Each time it is used, it is re-evaluated

So the consWrapper method can be called without actually evaluating its “stream” parameter, which is the behaviour we need.

fibs.scanLeft(1)(_ + _):

Let’s get the (_ + _) out of the way first. That’s your everyday anonymous function placeholder syntax, and is exactly equivalent to ((b,a) => b + a), which hopefully you’ll recognize as a function literal that takes two values that we declare as b and a on the left hand side of the =>,  and adds them together. Such repetition of the value names is avoided by using the underscore _ for each instead. The types of b and a are known from the context, i.e. the type of function scanLeft is expecting, given the types of the elements in the Stream, and the type of the first argument (1 in this case).

scanLeft is a method that is available on all Traversables, i.e. anything in the Scala collections library, which includes Streams such as our fibs here. First, what does it do? To quote the documents, this method is to

create a new stream which contains all intermediate results of applying the operator to subsequent elements left to right. scanLeft is analogous to foldLeft.

For a Stream[A], the method signature is:

final def scanLeft[B, That](z: B)(op: (B, A) ⇒ B)(implicit bf: CanBuildFrom[Stream[A], B, That]): That

Ouch! Let’s ignore the clever generic bits (that allow us to spit out a collection of some other type, if we so desired), and state it more simply as

def scanLeft[B](z: B)(op: (B, A) ⇒ B): Stream[B]

So we see that scanLeft takes two parameter lists, with one parameter in each.

  • The first, z, is some value of type B, which gives the initial value of the “accumulator”, i.e. a value that is used for storing the accumulated value of a fold function, the “current total”, if you like.
  • The second, op, is a function value which takes a B and an element A, and combines them into a new B (meaning, how to add an element to the current total). At the end we’re left with a Stream of Bs.

Let’s remind ourselves what foldLeft does, and see how this compares to scanLeft, using a List for simplicity:

val xs = List(2,3,4)
xs.foldLeft(10)(_ * _)

res5: Int = 240

We start with an accumulator, with value 10, then this is multiplied by 2, to give 20, which is our new accumulator value. So this is then multiplied by 3, to give 60. Finally, 60 is multiplied by 4, and the result 240 is returned. The list folds left to right into the accumulator like a concertina.

Now let’s change foldLeft to scanLeft:

xs.scanLeft(10)(_ * _)

res6: List[Int] = List(10, 20, 60, 240)

As you can see, scanLeft is very similar, except all the intermediate values of the accumulator are output. Note that the initial value is included. So it’s pretty simple: scanLeft is just a foldLeft that shows its working.

So now we understand the elements of this snippet, WHY does this yield a Stream of Fibonaccis?

To start with, we can see that the first element must be 0, because that has been tacked onto the start. fibs is

Stream.consWrapper(…).#::(0)

where the “…” is a Stream, but it’s not evaluated yet, because it’s passed by-name. This returns

Stream(0, ?)

Scala uses the ‘?’ in its toString representation to show the parts that haven’t yet been evaluated.

Now, let’s force it to evaluate some more of fibs. (We might do this using the “take” method to give us the first n elements.) To get the second value, we need to evaluate the “…”, which is the scanLeft part, fibs.scanLeft(1)(_ + _)

Remember that scanLeft returns a Stream, and (from the definition of scanLeft) the first element of that Stream is just the initial accumulator, which is 1. At this point,

fibs = 0 #:: Stream(1, ?)

For the third element of fibs, and second element of the scanLeft result, we use the (_ + _) function to combine the accumulator, 1, with the first element of fibs. This is 0, and readily available without evaluating scanLeft, as we saw above. 1 + 0 = 1.

fibs = 0 #:: Stream(1, 1, ?)

For the next element, remember how scanLeft works, from our demo with List above. Each element of the result is the value of the accumulator at each step in the calculation. We take the second element of fibs, 1, and combine it with the accumulator that we just calculated – which was the third element of fibs, also 1. 1 + 1 = 2.

fibs = 0 #:: Stream(1, 1, 2, ?)

Carrying on, because scanLeft by definition appends each accumulator value to the resulting Stream, we can see that each new value also is added to the fibs Stream, which means it’s available two steps later when we need to reference the next value of fibs. So in our next step, the third element of fibs, 1, is combined with the accumulator, which is what we just worked out.

fibs = 0 #:: Stream(1, 1, 2, 3, ?)

When the scanLeft method references the next value of fibs, it does not need to re-calculate each time, since Streams cache their results.

So as we can see above, the current accumulator value in scanLeft is the final element of fibs calculated so far, and the value of fibs being folded into the accumulator is always the value one element behind, which was the previous accumulator value. These are summed using (_+_), giving the new accumulator value, which is added on the end. Effectively, we’re continuously adding the last two values in the Stream to yield the following one. And that’s the definition of the Fibonacci sequence!

Food for thought

  1. Is it possible to use a List instead of a Stream in this solution, to give a Fibonacci sequence of a finite length?
  2. Is it possible to use foldLeft, rather than scanLeft, to return a single value at position n in the sequence?
  3. Why doesn’t Stream’s scanLeft method enter an infinite loop, given that the input Stream is infinite? How must the implementation on this method differ from the implementation on List?

Give your answers in the comments!