Sequences

The previous lesson showed that every transformation takes a collection and gives a new collection. map builds a four-element list from a four-element list, filter builds a third from that list; each step in the chain leaves its own intermediate list. Most of the time this is no problem. But if the source is very large, or infinite, or only the first matching element is wanted, every step processing all the elements is needless work.

Kotlin offers the sequence (Sequence) for this situation. A sequence is not a container that stores elements but a recipe for producing them in order. The intermediate operations added on top of it, such as map and filter, compute nothing; they only add a step to the recipe and return a new sequence. The operations that start the computation and produce the result are called terminal operations: toList, first, count and the like. When a terminal operation arrives, the elements pass through the chain one by one: the first element goes through all the intermediate operations and reaches the result, and only then does the second element start. Laziness is not a measuring axis here, only a property that explains behavior: a category asking when the value is computed is not used in this course. The measuring question stays as in the earlier lessons: what makes these two values equal?

There is a name clash to watch for. In Kotlin an array (Array, IntArray) is a fixed-size structure that holds its elements in contiguous memory. A sequence is the Sequence interface and does not carry the same name; in this lesson “sequence” always means Sequence, and where the distinction is needed we write it in full. The four criteria, Criterion and summarize are as in the earlier lessons.

// Criterion.kt — classifies the criterion that makes two values equal
class Criterion(val label: String, first: Any?, twin: Any?, other: Any?) {
    val sameObject = first === twin
    val equalTwin = first == twin
    val equalOther = first == other

    val name: String = when {
        sameObject -> "singleton"
        !equalTwin -> "identity"
        !equalOther -> "content"
        else -> "partial-content"
    }

    fun report() {
        println("$label: same-object=$sameObject, twin=$equalTwin, other=$equalOther -> $name")
    }
}

fun summarize(checks: List<Criterion>) {
    for (name in listOf("singleton", "identity", "content", "partial-content")) {
        println("$name: ${checks.count { it.name == name }}")
    }
}

A List Works at Once, a Sequence Piece by Piece

The difference shows most clearly through a side effect. The block below applies the same two operations to the same four elements, first with a sequence and then with a list. Each lambda adds a record to log, so which step ran when can be read afterwards. For the sequence three things are asked in turn: how many records there are right after the chain is built, what first() returns, and in what order the records stand. For the list only the record count and the first element are asked.

// Main.kt — a list works at once, a sequence piece by piece
fun main() {
    val log = mutableListOf<String>()
    val lazy = sequenceOf(1, 2, 3, 4)
        .map { log.add("map$it"); it * 2 }
        .filter { log.add("filter$it"); it > 2 }
    println(log.size)
    println(lazy.first())
    println(log)

    val eagerLog = mutableListOf<String>()
    val eager = listOf(1, 2, 3, 4)
        .map { eagerLog.add("map$it"); it * 2 }
        .filter { eagerLog.add("filter$it"); it > 2 }
    println(eagerLog.size)
    println(eager.first())
}

0
4
[map1, filter2, map2, filter4]
8
4

The first line shows that when the chain was built no lambda ran in the sequence: the intermediate operations were added to the recipe, and the computation did not start. In the second line first() ran as the terminal operation and returned 4. The third line says what ran. The first element 1 became 2 through map1, and filter2 dropped it (2 > 2 is not true). The second element 2 became 4 through map2, filter4 let it pass, and first() stopped when it found the first match. The elements 3 and 4 were never processed. Four records were kept in all.

In the list the same chain left eight records: four map, four filter. The 4 in the fifth line gives the same result, but first all four elements were mapped, then all four were filtered, and only after that was first() called. The difference between them is not a difference of result but of work. The result comes out the same; the sequence does not process needless elements and builds no intermediate list. This also changes the order of records for lambdas with side effects: in the list all the maps run first, then all the filters; in the sequence each element completes its own chain.

CC13. These measurements are for a four-element Int source and lambdas with side effects. How many elements the chain processes with pure lambdas without side effects, and how the amount of work changes with the size of the source, were not measured.

An Infinite Source and Kinds of Source

Because a sequence does not store its elements up front, its source can be infinite. generateSequence(1) { it * 2 } gives 1 as the first element, produces the next from the previous one and never ends. To get a finite result, a bounding operation such as take or takeWhile is added to the chain. The sequence { ... } builder takes a block that calls yield: each yield produces an element and the block pauses until the next element is requested. To move from a list to a sequence, asSequence() is used. The last two measurements show that the same sequence can be collected twice with toList().

// Main.kt — an infinite source and kinds of source
fun main() {
    println(generateSequence(1) { it * 2 }.take(6).toList())
    println(generateSequence(1) { it + 1 }.map { it * it }.takeWhile { it < 50 }.toList())
    println(listOf(3, 8, 11).asSequence().filter { it > 5 }.count())
    val squares = sequence {
        var n = 1
        while (true) {
            yield(n * n)
            n++
        }
    }
    println(squares.drop(2).take(3).toList())
    val twice = sequenceOf(1, 2, 3).map { it + 1 }
    println(twice.toList())
    println(twice.toList())
}

[1, 2, 4, 8, 16, 32]
[1, 4, 9, 16, 25, 36, 49]
2
[9, 16, 25]
[2, 3, 4]
[2, 3, 4]

The first line takes six elements from the powers of two. The second line produces the squares of the natural numbers and stops at the first square that is fifty or larger; the last element is 49. In the third line a list is turned into a sequence, filtered and counted: 8 and 11 are greater than five, so the result is 2. The fourth line drops the first two elements of an infinite square producer written with sequence { } (1 and 4) and takes the next three. The last two lines show that the same sequence was collected twice and gave the same result twice. A sequence built with sequenceOf can be traversed more than once; each terminal operation runs the recipe from the start. This cannot be generalized to every sequence, but it holds for the sources of this lesson.

There is a limit here too: if the bounding operation is forgotten on an infinite source, the program does not finish. Calling toList() without an operation such as take or takeWhile tries to fit an infinite collection into memory. A sequence makes infinity possible, but leaves the responsibility of building a finite result to the caller.

CC14. These measurements are for the sources generateSequence, sequence, sequenceOf and asSequence. What sources that can be traversed only once, such as the seedless form of generateSequence, do on a second traversal, and the result of an infinite source without a bounding operation, were not measured separately.

The Criterion: Identity

Sequences do not store their own content; they carry a recipe. So the question of the equality of two sequences gets a different answer than for two lists. The block below builds two separate sequenceOf(1, 2), compares the two with == and names the result with Criterion. other is a sequence that differs only in its second element. In the second measurement the sequences are built twice from the same list with asSequence(): even if the source is the same list, each call returns a new sequence.

// Main.kt — two sequences
fun main() {
    val list = listOf(1, 2)
    val checks = listOf(
        Criterion("sequenceOf", sequenceOf(1, 2), sequenceOf(1, 2), sequenceOf(1, 3)),
        Criterion("asSequence", list.asSequence(), list.asSequence(), sequenceOf(1, 3)),
    )
    for (check in checks) check.report()
    summarize(checks)
}

sequenceOf: same-object=false, twin=false, other=false -> identity
asSequence: same-object=false, twin=false, other=false -> identity
singleton: 0
identity: 2
content: 0
partial-content: 0

Both measurements came out as identity. The twins are separate objects and are not equal; that is, although two sequenceOf(1, 2) would produce the same elements, comparing them with == gives false. The reason is that Sequence does not define equals: equality falls to the default behavior, that is, identity. This is the criterion of the lesson: identity. The other measurement tells nothing here: since the twin does not come out equal anyway, the criterion becomes identity without looking at the other value. The second measurement is more instructive: even sequences built twice from the same list variable do not come out equal, because equality does not ask for the source to be the same.

CC15. These measurements are for sequences built with sequenceOf and asSequence. The equality among sequences derived with intermediate operations (the results of map and filter) and the equality of a generateSequence result were not measured separately.

The Bounding Measurement

Is there a way to compare two sequences, then? There is, but the comparison is made not on the sequence but on the collected form. toList() consumes the sequence and builds a list; because the list type defines equals by content, the result changes. The block below measures the same two sequences in three forms: as they are, with toList() and with toSet(). In the set measurement other is a sequence that gives the same elements in reverse order.

// Main.kt — content once collected
fun main() {
    val checks = listOf(
        Criterion("sequence", sequenceOf(1, 2), sequenceOf(1, 2), sequenceOf(1, 3)),
        Criterion("collected", sequenceOf(1, 2).toList(), sequenceOf(1, 2).toList(), sequenceOf(1, 3).toList()),
        Criterion("set", sequenceOf(1, 2).toSet(), sequenceOf(1, 2).toSet(), sequenceOf(2, 1).toSet()),
    )
    for (check in checks) check.report()
    summarize(checks)
}

sequence: same-object=false, twin=false, other=false -> identity
collected: same-object=false, twin=true, other=false -> content
set: same-object=false, twin=true, other=true -> partial-content
singleton: 0
identity: 1
content: 1
partial-content: 1

The bounding measurement is this: equality is given not by the value but by the type that holds the value. The same elements give the criterion identity in a sequence, content in a list and partial-content in a set. With the elements 1 and 2 in all three, the only thing that changes the criterion is the type of the container. The first line repeats the previous measurement. The second line shows that after toList() the twin is equal and the different one is not. The third line shows that order makes no difference in a set: even with other in reverse order, it comes out equal. So the criteria of the first two lessons appear side by side in this lesson.

The practical consequence: if two sequences have to be compared, they are collected into a suitable collection before the comparison. Which collection to collect into depends on which equality is wanted: toList() if order matters, toSet() if it does not. Also, collecting consumes the sequence; an infinite sequence has to be bounded before it is collected.

CC16. These measurements are for two-element sequences with Int elements. The equality of the collected forms of sequences whose elements are classes that do not define their own equality was not measured separately.

Operation Order Changes the Result

In a sequence the order of the intermediate operations changes not only the work but sometimes the result. The filter and take pair is the clearest example. filter { it % 2 == 0 }.take(2) first filters the even elements, then takes the first two. take(2).filter { it % 2 == 0 } first takes the first two elements, then filters only those. The block below applies both orders to a six-element source and records each filter call. The records show the elements that entered filter, in order.

// Main.kt — filter and take order
fun main() {
    val firstLog = mutableListOf<Int>()
    val filterFirst = sequenceOf(1, 2, 3, 4, 5, 6)
        .filter { firstLog.add(it); it % 2 == 0 }
        .take(2)
        .toList()
    println(filterFirst)
    println(firstLog)

    val secondLog = mutableListOf<Int>()
    val takeFirst = sequenceOf(1, 2, 3, 4, 5, 6)
        .take(2)
        .filter { secondLog.add(it); it % 2 == 0 }
        .toList()
    println(takeFirst)
    println(secondLog)
}

[2, 4]
[1, 2, 3, 4]
[2]
[1, 2]

The chain that filters first and takes after traversed until it found two even numbers: filter saw four elements and gave [2, 4]. In the chain that takes first and filters after, filter saw only the first two elements and a single element, [2], remained. The two chains were built from the same operations; their results differ. This says that intermediate operations should not be treated as interchangeable.

CC17. These measurements are for the filter and take pair. The record order of map with take, and of other bounding operations such as drop and takeWhile, was not measured separately.

Sorting Breaks Laziness

Not every intermediate operation lets elements pass one by one. To sort a sequence, sorted() has to see all the elements: the first result element is known only after the smallest is found. So when sorted() enters the chain, the source is traversed from start to end even if the remaining operations are lazy. The measurement makes this visible with onEach; onEach leaves a record as it passes each element. The first chain has sorted(), the second does not, and both end with first().

// Main.kt — sorted wants all the elements
fun main() {
    val sortedLog = mutableListOf<Int>()
    val smallest = sequenceOf(3, 1, 2, 5, 4)
        .onEach { sortedLog.add(it) }
        .sorted()
        .first()
    println(smallest)
    println(sortedLog)

    val plainLog = mutableListOf<Int>()
    val head = sequenceOf(3, 1, 2, 5, 4)
        .onEach { plainLog.add(it) }
        .first()
    println(head)
    println(plainLog)
}

1
[3, 1, 2, 5, 4]
3
[3]

The chain with sorted() found the smallest number, 1, but to do so it saw all five elements. The record is the full order of the source. The chain without sorted() took the first element, 3, and stopped; only that one is in the record. The rule is this: the gain of a sequence depends on no step in the chain waiting for all the elements. Operations such as sorted, sortedBy and sortedDescending cut this chain. If there is a bounding operation, putting it before the sorting reduces the elements to be sorted.

CC18. These measurements are for sorted() and first(). How many elements other operations such as sortedBy, sortedDescending and distinct wait for was not measured separately.

A Sequence Traversable Once

The previous section saw that a sequence built with sequenceOf can be collected twice. This does not hold for every sequence. A sequence built from an Iterator with asSequence() can give the iterator’s elements only once; on the second traversal the same iterator is already exhausted. Kotlin counts these sequences as traversable once and throws IllegalStateException on the second terminal operation. The error appears when the sequence is used in two places; it is not visible in the code that builds the chain.

// Main.kt — a sequence traversable once
fun main() {
    val once = listOf(1, 2, 3).iterator().asSequence()
    println(once.toList())
    try {
        println(once.toList())
    } catch (e: IllegalStateException) {
        println(e::class.simpleName)
    }
    val again = listOf(1, 2, 3).asSequence()
    println(again.toList())
    println(again.toList())
}

[1, 2, 3]
IllegalStateException
[1, 2, 3]
[1, 2, 3]

The first collection gave [1, 2, 3]. The second collection threw IllegalStateException, which was caught. When the same elements were this time built with listOf(1, 2, 3).asSequence(), both collections gave the same result: the sequence traverses the source list from the start each time. The difference is whether the source can be traversed again. Code that will use a sequence more than once must know which source the sequence was built from; if it is not sure, it should take the intermediate result into a collection with toList() and use that.

CC19. These measurements are for Iterator.asSequence() and List.asSequence(). Making a sequence traversable once on purpose with constrainOnce() and the text of the error message were not measured.

Summary

• In a sequence the intermediate operations do not run until a terminal operation arrives; when it does, each element passes through the whole chain. A list processes all the elements at every step, while a sequence never processes needless elements.
• generateSequence and sequence { } build an infinite source; a finite result is taken with take or takeWhile. If the bounding operation is forgotten, the program does not finish.
• Two separately built sequences are not equal; Sequence does not define equals. The criterion of this lesson: identity.
• The bounding measurement: the same elements give content when collected with toList() and partial-content when collected with toSet(); the type that holds the value decides equality.

Next Step

This lesson showed that a sequence is a recipe, and that a recipe alone is not a value. When elements have to arrive over time, while some other work is awaited, the recipe itself has to wait too. The next lesson builds this waiting computation with coroutines and asks the equality question again: are two waiting jobs that will give the same result equal to each other?