Fibonacci stream
February 4th, 2008The Fibonacci sequence: teacher of recursion for so many Computer Science students. But can it also teach us about streams? Yes! The function to build a stream (in Javascript):
var fib_stream_maker = function() { return (function() { var a = 0; var b = 0; var c = 1; return function() { a = b; b = c; c = a + b; return c; } })(); }
Let’s break this down so Ben can follow along. First, the inner most function:
return function() { a = b; b = c; c = a + b; return c; }
This anonymous function returns the next number in the sequence. Looking one level of scope higher, we see the variables a, b, and c declared:
function() { var a = 0; var b = 0; var c = 1; return function() { a = b; b = c; c = a + b; return c; } }
So we initialize the variables and then return a function that increments those variables, local to the inner function’s scope, so we can have multiple instances of the function running without collision of variables. To build the stream factory, we wrap the initialization function in parentheses, creating a continuation, and then execute the wrapped function, creating an initialized fib stream function. This is then set to return when the fib_stream_maker is called as a function.
var fib_stream = fib_stream_maker(); fib_stream(); // returns 1 fib_stream(); // returns 2 fib_stream(); // returns 3 fib_stream(); // returns 5 fib_stream(); // returns 8, etc...
This is only touching the surface of streams but I thought it was pretty cool that the Fibonacci sequence can be utilized to teach such important concepts as continuations and streams. Code on!
*Update*
While explaining the inner workings of the above code to CD, she asked a very astute question, one that Ben probably would not have, “What about going backwards in the stream?” A just question. Let’s look at a table of how the values of a, b, and c act as the stream goes forward first (this will help us design our algorithm later).
| a | b | c | Returns | |
| Creating fib_stream | 0 | 0 | 1 | |
| fib_stream(); | 0 | 1 | 1 | 1 |
| fib_stream(); | 1 | 1 | 2 | 2 |
| fib_stream(); | 1 | 2 | 3 | 3 |
| fib_stream(); | 2 | 3 | 5 | 5 |
So to go backwards, what do we need to do to values of a, b, and c? We need to assign b’s value to c, a’s value to b, and the difference of c and b to a, and still return c. In code, this would look like:
c = b; b = a; a = c - b; return c;
To integrate this into the above example, we need to pass a boolean parameter to the inner-most lamda function and test to see whether to forward or reverse the stream. Let’s see the inner-lamda now:
return function(go_forward) { if ( go_forward ) { a = b; b = c; c = a + b; } else { c = b; b = a; a = c - b; } return c; }
We may want to put an additional test to see if we are at the beginning of the stream again:
return function(go_forward) { if ( go_forward ) { a = b; b = c; c = a + b; } else if ( a == 0 && b == 0 ) { ; // do nothing } else { c = b; b = a; a = c - b; } return c; }
Let’s see it all as one big fun function:
var fib_stream_maker = function() { return (function() { var a = 0; var b = 0; var c = 1; return function(go_forward) { if ( go_forward ) { a = b; b = c; c = a + b; } else if ( a == 0 && b == 0 ) { ; // do nothing } else { c = b; b = a; a = c - b; } return c; } })(); }
And there you have it. Thanks CD for bringing up this interesting idea! What a nerd!