--- title: Sequences source: 'https://academia.sh/en/courses/kotlin/sequences' course: 'The Kotlin Language' language: en updated: '2026-10-21T05:02:39+00:00' license: 'CC BY-SA 4.0' objectives: - 'Measures that intermediate operations do not run before a terminal operation and that elements pass through the chain one at a time' - 'Shows with generateSequence and sequence that a finite result can be taken from an infinite source' - 'Reads from the output that two separately built sequences are not counted as equal' - 'Measures that once a sequence is collected, equality comes from the type of the collected collection, not the sequence' --- # Sequences Measures that a sequence holds its intermediate operations until a terminal operation arrives and processes elements piece by piece, that it can be finished from an infinite source, and that two sequences are not counted as equal. 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. ```kotlin // 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) { 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. ```kotlin // Main.kt — a list works at once, a sequence piece by piece fun main() { val log = mutableListOf() 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() 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 `map`s run first, then all the `filter`s; 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()`. ```kotlin // 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. ```kotlin // 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. ```kotlin // 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. ```kotlin // Main.kt — filter and take order fun main() { val firstLog = mutableListOf() 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() 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()`. ```kotlin // Main.kt — sorted wants all the elements fun main() { val sortedLog = mutableListOf() val smallest = sequenceOf(3, 1, 2, 5, 4) .onEach { sortedLog.add(it) } .sorted() .first() println(smallest) println(sortedLog) val plainLog = mutableListOf() 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. ```kotlin // 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?