I like lazy evaluation, and it’s one of the reasons I like Haskell and Clojure. Although from engineering perspective lazy evaluation is probably not the most needed feature, it’s definitely very useful for solving some mathematical problems.
Most languages don’t have lazy evaluation out of the box, but you can implement it using some other language features. This is an interesting task, and I use it as a code kata which I practice every time I learn a new strict language.
So, how to implement lazy lists in a strict language? Very simple, if the language is functional. Namely, you build lazy list recursively by wrapping strict list within a function. Here is, for example, the strict empty list in Groovy:
If we wrap it with a closure, it becomes lazy empty list:
If we need a list with one element, we prepend (or speaking Lisp terminology cons) an element to lazy empty list, and make the result lazy again:
To add more elements we continue the same process until all elements are lazily consed. Here is, for example, a lazy list with three elements a, b and c:
Now, when you have an idea how to build lazy lists, let’s build them Groovy way. We start by creating a class:
list encapsulates the closure wrapper of the list. We need to expose some methods that allow constructing lists using procedure described above:
Now we can construct lists by consing elements to empty list:
To access elements of the list we implement two standard functions,
cdr, that return head and tail of the list respectively.
Here is how you use these functions to get first and second elements of the list constructed above
In Lisp there are built-in functions for various
cdr compositions. For example, the previous assertion would be equivalent to function
cadr. Instead of implementing all possible permutations, let’s use Groovy metaprogramming to achieve the same goal.
It might look complicated, but in reality it’s pretty simple if you are familiar with Groovy regex and functional programming. It’s easier to explain by example. If we pass “caddr” as a value of
name parameter, the method will create a chain on method calls
.cdr().cdr().car() which will be applied to delegate of the operation which is our LazyList object.
With this method in place we can call car/cdr functions with arbitrary depth.
If you create nested lazy lists, you can access any element of any nested list with this dynamic method.
With so many cons methods it’s hard to see the structure of the list. Let’s implement
lazy method on ArrayList class that converts strict list to lazy. Again, we will use metaprogramming and functional techniques.
Now we can rewrite the previous example as follows
What have we accomplished so far? We learned how to build lazy lists from scratch and from strict lists. We know how to add elements to lazy lists, and how to access them. The next step is to implement
fold is the fundamental operation in functional languages, so our lazy lists must provide it.
The only difference between this
fold function and the standard one is the additional parameter n. We will need it later when we implement infinite lists.
foldAll function to lazy lists is the same as standard
fold to strict lists.
First example calculates the sum of all elements of the list, second calculates the product of first three elements.
If you have
fold functions you can easily implement
take is an inverse operation to
Our next goal is
map function on lazy lists. Ideally I want the implementation look like this
For some reason it doesn’t work lazy way in Groovy — it’s still strictly evaluated. Therefore I have to implement it directly with closure syntax
map is identical to strict
The following example shows one of the benefits of laziness
map didn’t evaluate the entire list, hence there was no exception. If you evaluate the expression for all the elements, the exception will be thrown
For strict lists this is a default behaviour of
The last function I want to implement is
In the following example we find first two elements greater than 2
With the help of
filter you can implement any other function on lazy lists yourself. Here is, for example, the implementation of
Now, after we implemented all lazy functions we need, let’s define infinite lists
Infinite lists, from my point of view, is the most useful application of lazy lists
At this point you have all basic functionality implemented, and you should be able to extend this model to whatever you need in regards to lazy (infinite) lists. Happy lazy programming!