Sequences: Theory

Let’s figure out how sequences work and how they differ from collections

Transformation of collections

• Each transformation is performed in a separate loop.
• For each transformation, a copy of the original collection is created.

Therefore, each transformation we make involves allocating new memory and copying the array, which in theory may not be very optimal.

Transformation of sequences

• All transformations are performed in a single loop iteration.
• There is no allocation of additional memory for storing intermediate results.

Therefore, in theory, it seems that when using transformations through sequences, we avoid all the negative aspects that regular collection transformations have. It appears that sequences should provide a significant performance boost. However, are these assumptions correct, or are there any hidden pitfalls and nuances? Let’s find out.

What are sequences?

Sequences are often described as lazy collections, but that’s not entirely accurate.

When we work with a collection, we are working with a set of data. A set of data has a beginning and an end. We can navigate through the set of data forwards and backwards. We know the number of elements in the set of data.

When we work with sequences, we are not working with a set, but with a sequence of elements. We do not have information about the number of elements, and we cannot navigate through the sequence. We do not know when it started or when it will end. Essentially, we only have the current element at hand.

Sequence

Sequences are simply a wrapper interface over an iterator and nothing more.

public interface Sequence<out T> {
    public operator fun iterator(): Iterator<T>
}

When we use the asSequence() function, we are simply creating an anonymous class that implements the sequence interface, which hides the underlying iterator of our collection or data source.

public fun <T> Iterable<T>.asSequence(): Sequence<T> {
    return Sequence { this.iterator() }
}

And then we work with the sequence using only its iterator. All we have is the value of the current element and the ability to move to the next element.

Iterator

You may call me “Captain Obvious” but let’s remember how an iterator works. Everything in the world of sequences is built on iterators, so it is important to understand the principles of its work.

public interface Iterator<out T> {
    public operator fun next(): T
    public operator fun hasNext(): Boolean
}

Iterator has just only two methods:

• hasNext() — returns true if it has the next element
• next() — Moves to the next element and returns its value

Thus, we always work with the iterator in a loop, and on each iteration of the loop, we always call the combination of methods hasNext() and next().

while (iterator.hasNext()) {
        val value = iterator.next()
    }

How lazy sequence magic works

When we use collection transformation through sequences, for each transformation function, a decorator is created underneath, wrapping the iterator of the original collection.

Let’s say we have the following collection transformation:

sourceCollection.asSequence()
        .map { it + 1 }
        .map { it + 2 }
        .map { it + 3 }
        .toList()

In this case, under the hood, it would expand to the following construction:

val resultIterator = 
        MapIterator( { it + 3 }, 
            MapIterator( { it + 2 }, 
                MapIterator( { it + 1}, 
                    sourceCollection.iterator()
                )
            )
        )
    
    val result = mutableListOf<Int>()
    resultIterator.forEach { result.add(it) }

All of our transformation functions have become decorators and are nested inside each other like matryoshka dolls, giving us a single resulting iterator. As a result, we only need to iterate once over the resulting iterator, and we will obtain the transformed collection as output.

On each iteration of the loop, for each element of the resulting iterator, all our transformation functions are applied sequentially. In essence, the principle of invoking our transformations through decorators can be well demonstrated by the following pseudocode.

This example demonstrates the transformation of a single element from the original collection with a value of 10 => 10 + 1 + 2 + 3 => 16.

resultIterator.next() => 16
               | 16
    mapIterator(it + 3).next() + 3 => 13 + 3 = 16
                        | 13
        mapIterator(it + 2).next() + 2 => 11 + 2 = 13
                            | 11
            mapIterator(it + 1).next() + 1   => 10 + 1 = 11
                                | 10
                sourceIterator().next()  => 10

Well, now that we have covered the theory, let’s move on to measurements and take a look under the hood.

You can learn more from my sequences performance study “Measuring sequences”