Lazy lists in Mathematica

Posted 2 years ago
6325 Views
|
7 Replies
|
16 Total Likes
|

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!

7 Replies
Sort By:
Posted 2 years ago
 Neat! I do not immediately foresee practical uses myself, but I can imagine there are. Do you have any?
Posted 2 years ago
 To be fair, I don't have immediate practical uses myself either, but they seem useful enough to have as a tool when the time comes. I imagine this can be useful to traverse large data sets. For example, you can represent a large file as a line-by-line lazyList, making it possible to map functions over it without having to read the whole thing into memory. You could to the same thing with databases.
Posted 2 years ago
 I would foresee lazuTuples as something that would be useful Say you want to traverse a large number of tuples but do not want to create them all at startup because of memory.
Posted 2 years ago
 Good suggestion about Tuples. I added a lazyTuples function on my development branch, though it's probably not in its final form yet. I based the methodology of off the SE answer below. It's well worth a read if you ever want to work with large numbers of tuples: https://mathematica.stackexchange.com/a/153609/43522Edit I think I did everything I for the implementation of lazyTuples right now. In the future I may try to implement a feature to generate tuples in chunks rather than 1-by-1, but the current code should already work quite well.
Posted 2 years ago
 - Congratulations! This post is now a Staff Pick as distinguished by a badge on your profile! Thank you, keep it coming!
 Lazy evaluation is quite handy in optimising interactive code like Manipulate when you don't want to compute a whole set of data anew prior to the start of Manipulate or at every "refresh".