LazyList

A lazy list that remembers what it computed. Nothing is computed before it is read, not even its first element or whether it is empty: each element is computed when it is first reached, and then kept. It can be infinite.

Unlike a java.util.stream.Stream, which is a one-shot pipeline, a LazyList is a collection: it can be read many times, and each read after the first reuses what was computed.

When to choose it

For a sequence computed on demand: an infinite series, a sequence whose elements are expensive and only partly read, or a sequence defined in terms of itself.

var naturals = LazyList.from(1); // LazyList<Integer>
var squares  = naturals.map(n -> n * n).filter(n -> n % 2 == 1).take(4).toVector();
// Vector(1, 9, 25, 49)

var fibonacci = LazyList.of(0L, 1L).appendSelf(self -> self.zipWith(self.tail(), Long::sum));
var firstTen  = fibonacci.take(10).toVector(); // Vector<Long>
// Vector(0, 1, 1, 2, 3, 5, 8, 13, 21, 34)

LazyList.iterate(seed, f), LazyList.continually(supplier) and LazyList.ofAll are other ways to create one.

Nothing is computed before it is read

Building a LazyList and calling map, filter or appendAll on it compute nothing. Reading an element computes the elements it needs, once, even when several threads read it.

var seen    = new java.util.ArrayList<Integer>();
var squares = LazyList.from(1).tap(seen::add).map(n -> n * n); // LazyList<Integer>
// seen is empty: nothing is computed yet
var third = squares.get(2); // 9, and seen is [1, 2, 3]

LazyList.cons(head, () -> tail) takes its first element as a value. LazyList.defer(() -> ...) computes the whole list, first element included, when it is first read.

Costs

lazy means the call computes nothing: each element of the result is computed when it is first read. The note says what reading the first element computes: filter and the calls like it the elements up to the first one they keep, drop, slice and dropRight the elements they skip or hold back, rotateLeft or takeRight the whole list. reverse, sorted and scanRight compute the whole list when they are called.

Operation	Cost	Note
head	O(1)	O(1) once this LazyList is computed; otherwise the call computes it first, which is where a lazy operation does its work (such as the search of filter), and keeps the result.
tail	O(1)	O(1) once this LazyList is computed: the tail is returned without being computed. If this LazyList is not computed yet, the call computes it first, as head does. On a LazyList built by append or appendAll, computing the first appended element may put the p appended parts in order, O(p) once for the whole walk.
last	O(n)	O(n); the whole LazyList is computed.
init	lazy	lazy; the first element is computed now, to know that this LazyList is not empty, and the result reads one element ahead of what it returns.
get	O(i)	O(i); the first i + 1 elements are computed.
update	lazy	lazy; nothing is computed now. The result copies the elements before index i as it reaches them and shares those after it; an index past the end throws when the result reaches it.
prepend	O(1)	O(1); nothing is computed.
append	O(1)	O(1); nothing is computed now, and the element comes after the last one of this LazyList. Appending in a loop stays O(1) per call, and reading the result back costs O(1) per element, however many calls built it.
prependAll	O(1)	O(1); nothing is computed now: the given elements are read when the result reaches them, and this LazyList is shared, not read. Calling prependAll in a loop stays O(1) per call, and reading the result back costs O(1) per element, however many calls built it.
appendAll	O(1)	O(1); nothing is computed now, neither of this LazyList nor of the given elements, which are read when the result reaches them, so an infinite argument is fine. They are read once, into a LazyList that every result built from this one shares. Calling appendAll or append in a loop stays O(1) per call, and reading the result back costs O(1) per element, however many calls built it.
insert	lazy	lazy; nothing is computed now. The result copies the elements before index i as it reaches them, and shares the rest.
removeAt	lazy	lazy; nothing is computed now. The result copies the elements before index i as it reaches them, and shares the rest.
take	lazy	lazy; nothing is computed now, each element when the result reaches it.
drop	lazy	lazy; nothing is computed now. Reading the first element computes the k dropped elements and the first one kept, O(k); the rest are computed when the result reaches them. A drop of a drop not read yet is one drop of the sum, so a chain of drops is read at the stack depth of one.
slice	lazy	lazy; nothing is computed now. Reading the first element computes the first i + 1 elements, O(i), and the rest up to index j are computed when the result reaches them, so it works on an infinite LazyList.
splitAt(Predicate<? super T>)	lazy	lazy; nothing is computed now, and each side computes its elements when it is read: the suffix starts at the first match.
splitAt(int)	lazy	lazy; nothing is computed now, and each side computes its elements when it is read.
reverse	O(n)	O(n); the whole LazyList is computed now.
sorted	O(n log n)	O(n log n) comparisons; the whole LazyList is computed now.
size	O(n)	O(n): the whole LazyList is computed and walked at each call, so it never returns on an infinite LazyList.
contains	O(n)	O(n): the elements are compared one by one until an equal one is found. The sets and the maps override it with a lookup.
indexOf	O(n)	O(n); the elements are computed until the element is found.
zip	lazy	lazy; nothing is computed now, and reading every pair costs O(min(n, m)).
sliding(int)	lazy	lazy; nothing is computed now, and reading every window costs O(n * size). Moving to the next window computes the elements of the current one and one more, so an infinite LazyList can be windowed.
sliding(int, int)	lazy	lazy; nothing is computed now, and reading every window costs O(n + (n / step) * size). Moving to the next window computes the elements up to max(size, step) positions after the start of the current one, so an infinite LazyList can be windowed.
grouped	lazy	lazy; nothing is computed now, and reading every block costs O(n). Moving to the next block computes the elements of the current one and one more, so an infinite LazyList can be grouped.
distinct	lazy	lazy; nothing is computed now. Moving to the next element skips and hashes the repeated ones before it, which never ends on an infinite LazyList with no further new element.

Every method: complexity page.

Sharp edges

• Operations that need the whole sequence compute it and never return on an infinite LazyList: size, last, reverse, sorted, max, min, foldRight, groupBy, lastIndexOfSlice(that) and hashCode, and anything else that reads every element, such as foldLeft, mkString or toVector.
• equals stops at the first difference or at the end of the shorter side, so an infinite LazyList compared with a finite List, Vector, Queue or LazyList returns. Two infinite LazyLists with the same elements never do.
• filter and the calls like it (reject, retainAll, removeAll, collect, flatMap, distinct) compute elements until they find one to keep, each time the result is read further. On an infinite LazyList with nothing more to keep, reading the next element never returns. isEmpty() reads: it runs that search too.
• partition and partitionMap return at once, but reading a side that stays empty on an infinite LazyList never returns.
• An out-of-range index given to insert, insertAll, removeAt or update throws when the result is read that far, not when the method is called (unless the LazyList is already known to be empty). A negative index throws at once.
• LazyList.cons(head, supplier) calls the supplier when the tail is read, not when tail() returns it: a supplier that returns null fails there.
• When computing an element throws, the LazyList keeps the exception in its place: reading that element again throws the same exception, and never skips to the next one. Only a VirtualMachineError, such as a stack overflow, lets a later read try again.
• A chain of thousands of lazy operations (map, filter, take, defer inside defer) built without reading anything is evaluated recursively on the first read, as in Scala, and can overflow the stack then. Reading as you go, or reading on a thread with a bigger stack, avoids it. A chain of drops, or a loop of append or appendAll, has no such limit.
• A LazyList keeps every element it computed. Holding on to the start of a long LazyList while walking it keeps all of it in memory.