Lazy Lists in Groovy

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:

The variable 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, car and 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 car and 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 function. 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 functions

take is an inverse operation to lazy

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

Unlike fold, lazy map is identical to strict map

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 map function.

The last function I want to implement is filter

In the following example we find first two elements greater than 2

With the help of car/cdr, fold, map and filter you can implement any other function on lazy lists yourself. Here is, for example, the implementation of zipWith function

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!