The Lazy Fibonacci List
In a project I am working on, I want to implement a large list using lazy evaluation in Scheme. The list is large enough to be too unwieldy to store entirely in memory, but I still want to represent it in my program as if it was. The solution is lazy evaluation.
One use of lazy evaluation is allowing a program to have infinitely sized data structures without going into the impossible task of actually creating them. Instead, the structure is created on the fly as needed. As a prototype for getting it right, I made an infinitely long list in Scheme that contains the entire Fibonacci series.
This function, given two numbers from the series, returns the lazy
list. It uses
delay to delay evaluation of the list.
Notice the recursion here as no base case, so without lazy evaluation it would continue along forever without halting. Now run it,
The rest of the list is stored as a promise, which will later
be teased out using
force. This forces evaluation of the
promise. Here is a function to traverse the list to the
nth element and return it. Notice, this does have a base
Here it is in action. It is retrieving the 30th element.
If you examine
f, it contains the first 30 numbers until
running into an unevaluated promise. This behavior is very similar to
memoization, as calculated values
are stored instead of being recalculated later.
These two functions are also behaving as coroutines. When
nth-fib reaches a promise, it yields to
which continues its non-halting definition. After producing a new
f, it yields back to
The way I called these functions above, however, can lead to
problems. We are storing all the calculated values in
which can take up a lot of memory. For example, this probably won't
We will run out of memory before it halts. Instead, we can do this,
nth-fib uses tail recursion as it traverses the
list, unneeded calculated values are tossed (which the garbage
collector will handle) and no additional function stack is used. All
Scheme implementations optimize tail recursion in this way. This will
continue along until it hits the millionth Fibonacci number, all while
using a constant amount of memory.
It turns out that Scheme calls this type of data structure a stream, and some implementations have functions and macros defined so that they are ready to use.
So there you go: memoization, lazy evaluation, and coroutines all packed into one example.