Hi all. In this post I want to demonstrate a package I wrote (and still tweak here and there), which implements Haskell-style lazy lists in Mathematica. Anyone who wants to play around with it can find here on Github:

https://github.com/ssmit1986/lazyLists

What are lazy lists?

Before diving into implementation details, let's give some motivation for the use of lazy lists. A lazy list is a method to implicitly represent a long (possibly infinite) list. Of course, you cannot truly have an infinite list in your computer, so the central idea is to format the list as a linked list consisting of 2 parts. This means that a lazyList will always look like this:

lazyList[first, tail]

Here, first is the first element of the list and tail is a held expression that, when evaluated, will give you the rest of the list, which is again a lazyList with a first element and a tail. So in other words: elements of a lazyList are only generated when they are needed and not before. This makes it possible to represent infinite lists and perform list operations on them. To get the elements of the list, one can simply evaluate the tail as often as needed to progress through the list.

For example, let's define lazyRange[] as the lazy list of all positive integers. Then

Map[#^2&, lazyRange[]]

becomes the infinite list of all squares, again represented as a lazy list. You can go even further, though. For example, you can generate the triangular numbers by doing a FoldList over the integers and then select the odd ones with a Select:

Select[FoldList[Plus, 0, lazyRange[]], OddQ]

which is yet another lazy list. So if we want the first 100 odd triangular numbers, we simply evaluate the tail of this lazy list 99 times to get them. In contrast, if you'd try to do this with a normal list, you could do something like this:

    Select[FoldList[Plus, 0, Range[n]], OddQ]

However, what value should you pick for n? If you pick it too low, you won't get your 100 numbers. If it's too high, you're doing too much work. Of course you could write some sort of While loop, but the code for that would be less concise and doesn't really play into the strengths of Wolfram Language.

Implementation

To illustrate how my code works, I will reproduce some of the code in this blog post, though the package code is different in some respects for efficiency reasons.

The easiest way to prevent the tail from evaluating is to give lazyList the HoldRest attribute, which is how I implemented them:

Attributes[lazyList] = {HoldRest}

Next, we need some way to construct basic infinite lists like the positive integers. This is generally done recursively. My lazyRange[] function takes up to 2 arguments: a starting value (1 by default) and an increment value (also 1 by default):

lazyRange[start : _ : 1, step : _ : 1] := lazyList[start, lazyRange[start + step, step]]

We can extract the first element with First and advance through the list with Last:

First@lazyRange[]
First@Last@lazyRange[]
First@Last@Last@lazyRange[]

Out[100]= 1    
Out[101]= 2    
Out[102]= 3

We can also check that the tail of lazyRange[] is equal to the list of integers starting from 2:

In[103]:= Last@lazyRange[] === lazyRange[2]    
Out[103]= True

Of course, iterating Last can be done with NestList, so if we want to get the first n elements of the lazy list, we can define the following special functionality for Take by setting an UpValue for lazyList:

lazyList /: Take[l_lazyList, n_Integer] :=  NestList[Last, l, n - 1][[All, 1]]
Take[lazyRange[], 10]

Out[105]= {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}

As it turns out, nesting Last isn't actually the most efficient way to do this, so I ended up implementing Take with ReplaceRepeated and Sow/Reap to make the best use of the pattern matching capabilities of WL.

Next, we want to be able to do transformations on lazyLists. The simplest one is Map: you simply create a lazyList with the function applied to the first element and then Map the function over the tail:

lazyList /: Map[f_, lazyList[first_, tail_]] := lazyList[
   f[first],
   Map[f, tail]
];
Map[#^2 &, lazyRange[]]
Take[%, 10]

Out[117]= lazyList[1, (#1^2 &) /@ lazyRange[1 + 1, 1]]
Out[118]= {1, 4, 9, 16, 25, 36, 49, 64, 81, 100}

Similarly, Select is easily implemented by repeatedly evaluating the tail until we find an element that satisfied the selector function f. At that point we found our element and return a lazyList:

lazyList /: Select[lazyList[first_, tail_], f_] /; f[first] := lazyList[first, Select[tail, f]];
lazyList /: Select[lazyList[first_, tail_], f_] := Select[tail, f];

As an example, we can now find the first 10 numbers that are co prime to 12 and the first 10 squares that are 1 more than a multiple of 3:

Take[Select[lazyRange[], CoprimeQ[#, 12] &], 10]
Take[Select[Map[#^2 &, lazyRange[]], Mod[#, 3] === 1 &], 10]

Out[128]= {1, 5, 7, 11, 13, 17, 19, 23, 25, 29}
Out[129]= {1, 4, 16, 25, 49, 64, 100, 121, 169, 196}

I hope this gives a good enough overview of the benefits of lazyLists as well as giving you an idea of how to use them. In the package I tried to implement other list computational functionality (such as MapIndexed, MapThread, FoldList, Transpose, Cases, and Pick) for lazy lists as efficiently as possible.

Please let me know if you have further suggestions!