Hello Kotliners, happy Monday! Today we're diving into the mechanics of Kotlin's Iterator.

In Kotlin, we frequently use APIs like for, map, filter, and take to process collections.

These APIs are arguably among the most frequently used tools in daily development, but frankly, many developers may not truly understand the mechanisms behind them.

Have you ever wondered:

1. Why can a for loop traverse a List?
2. Why can Sequence perform lazy execution?
3. Is Sequence really more efficient than regular collection operations? Under what circumstances might it actually be slower?
4. Why can't you directly delete elements while traversing a collection?

To understand these questions, we need to start with the foundation of Kotlin collection traversal—the Iterator.

How Iterator Works

An iterator allows us to access elements one at a time without exposing the internal structure of a collection.

In Kotlin, Iterator is one of the foundations of the collection API, providing a unified way to sequentially access various collections.

Looking at its definition, Iterator is actually very simple, with only two core operator functions: hasNext() and next().

/**
 * Used for traversing collections, or other objects that can be represented as a sequence of elements.
 * Allows accessing elements in order.
 */
public actual interface Iterator<out T> {
    /**
     * Returns the next element in the iteration.
     *
     * Throws NoSuchElementException if there is no next element.
     */
    public actual operator fun next(): T

    /**
     * Returns true if there are more elements in the iteration.
     */
    public actual operator fun hasNext(): Boolean
}

This design embodies the classic Iterator Pattern.

hasNext() checks if there are more elements ahead, preventing out-of-bounds access; next() returns the next element and advances the iterator's internal traversal state.

Although the interface has only two functions, it's this simple contract that allows List, Set, and even custom data structures to be traversed sequentially in a unified way.

Core Capabilities of Iterator

The Iterator interface revolves around two cooperating functions: hasNext() and next().

1. hasNext(): Boolean

   hasNext() checks whether the current iterator has a next element.

   You can think of it as asking: "Has the traversal ended? Are there any elements left?"

   If traversal can continue, it returns true; when all elements have been visited, it returns false.

   Note that calling hasNext() does not move the caller-visible traversal position to the next element. It simply tells us whether we can still call next().

2. next(): T

   next() returns the next element in the iteration and advances the iterator's internal state, allowing subsequent calls to continue accessing later elements.

   It is the primary way we actually retrieve data from the iterator.

To avoid errors, next() should only be called when it's certain that a next element exists.

If the iterator has reached the end—meaning hasNext() would return false—but we still call next(), it will throw a NoSuchElementException.

Therefore, hasNext() and next() are almost always used together with loops, forming a safe and reliable traversal method.

Using Iterator

Here's a manual traversal of a list using Iterator:

val names = listOf("rockbyte", "kotlin", "developer")
val iterator = names.iterator()

while (iterator.hasNext()) {
    println(iterator.next())
}

In this example, iterator() creates an iterator for the list.

The while loop then repeatedly calls hasNext() to check for elements and retrieves them one by one via next().

Of course, in everyday coding, we rarely manually operate iterators to traverse collections. The more common approach is to use a for loop directly:

val names = listOf("rockbyte", "kotlin", "developer")

for (name in names) {
    println(name)
}

From Kotlin's language rules, this for loop semantically still relies on iterator(), hasNext(), and next().

It can be understood as the following expanded form:

val iterator = names.iterator()

while (iterator.hasNext()) {
    val name = iterator.next()
    println(name)
}

Thus, the for loop doesn't bypass the iterator; it hides the operational details of the iterator, making the code more concise and readable.

This refers to the semantic expansion at the Kotlin language level. For common types like arrays and ranges, the compiler may perform specific optimizations when generating actual code, meaning the final bytecode isn't necessarily identical to the while code above.

MutableIterator

A regular Iterator is only responsible for traversing and reading elements, but sometimes we also need to modify the collection during traversal.

For example, deleting elements that meet a certain condition while traversing a list.

For this, Kotlin provides the MutableIterator interface. As the name suggests, it inherits from the base Iterator, thus still possessing hasNext() and next(), while adding an important capability: safely removing elements during traversal.

Here is the MutableIterator interface definition:

/**
 * Iterator for traversing mutable collections.
 * Supports removing elements during traversal.
 *
 * @see MutableCollection.iterator
 */
public actual interface MutableIterator<out T> : Iterator<T> {
    /**
     * Removes from the underlying collection the last element returned by this iterator.
     *
     * Throws IllegalStateException if next has not yet been called,
     * or if remove has already been called after the last next call.
     */
    public actual fun remove(): Unit
}

Core Capabilities of MutableIterator

MutableIterator has two main characteristics.

1. Inherits from Iterator

   Because MutableIterator inherits from Iterator<T>, it can do everything a regular iterator can do.

   We can still call hasNext() in a while loop and get elements via next().

2. Adds the remove() function

   remove() is the most important extension of MutableIterator.

   It deletes the element most recently returned by next().

There's a crucial restriction here: we cannot call remove() arbitrarily at any time.

We must first call next() to let the iterator determine which element is currently being processed, and only then can we call remove() to delete that element from the underlying collection.

If used incorrectly, remove() will throw an IllegalStateException in the following two situations:

• next() has not been called yet: Before the iterator has returned any element, there is no target for deletion.
• remove() is called twice consecutively: After deleting an element, you must call next() again to move to a new element before you can call remove() again.

Using MutableIterator

Using MutableIterator.remove() is a safe way to delete elements while traversing a collection.

If you directly call the collection's own removal functions inside a regular for loop, the collection's structure changes without the iterator's knowledge. On the JVM, many common collection implementations detect this structural modification and throw a ConcurrentModificationException.

Suppose we want to remove all even numbers from a mutable list of integers. We can write it like this:

val numbers = mutableListOf(1, 2, 3, 4, 5, 6, 7, 8)
val iterator = numbers.iterator()
// Calling iterator() on a MutableList returns a MutableIterator

while (iterator.hasNext()) {
    val number = iterator.next()

    if (number % 2 == 0) {
        // Remove the element just returned by next()
        iterator.remove()
    }
}

println(numbers) // Output: [1, 3, 5, 7]

In this example, the element removal is performed by the MutableIterator currently executing the traversal.

Therefore, the iterator can synchronously maintain its internal state, continuing to access the correct position after removing an element, avoiding disruption of the traversal process due to structural changes in the collection.

Of course, if the requirement is simply "remove all elements that meet a condition," you can use the more concise removeAll in actual business code:

numbers.removeAll { it % 2 == 0 }

However, understanding MutableIterator is still important. It not only explains the mechanism for safely removing elements during traversal but also helps us understand why directly modifying a collection being traversed can cause problems.

Summary

Iterator provides a simple and unified way to sequentially traverse different types of collections.

A regular Iterator is responsible for reading elements; MutableIterator adds modification capabilities on top of this, allowing us to safely delete the current element during traversal.

Whether explicitly calling iterator() or using the more idiomatic Kotlin for loop, they all rely on this simple access protocol behind the scenes.

What is Sequence

In the Kotlin standard library, both Iterable and Sequence can be used to process a series of elements.

Collections like List and Set implement Iterable. On the surface, many operations provided by Iterable and Sequence look very similar, such as map, filter, and flatMap, with almost identical calling conventions.

However, their underlying execution models differ significantly.

For Iterable, common multi-step collection transformations adopt an eager execution approach: first, the current operation is completed for the entire collection, producing an intermediate result, and then the next operation is performed on that intermediate result.

Sequence, on the other hand, uses lazy execution. It processes elements one by one as needed, and computation only happens when the downstream actually requests results.

The entire Sequence mechanism is built upon a very simple contract: the iterator() operator function.

public interface Sequence<out T> {
    /**
     * Returns an Iterator that yields elements of this sequence one by one.
     *
     * If this Sequence is constrained to be traversed only once,
     * calling iterator() a second time will throw an exception.
     */
    public operator fun iterator(): Iterator<T>
}

Unlike collections like List and Set that already hold elements in memory, Sequence is more like a description of "how to produce a series of elements" and "what processing these elements need to undergo."

Its single core promise is: when requested externally, it can provide an Iterator.

What truly drives the entire sequence is this Iterator. It knows how to produce or read the next element, but typically only actually fetches and processes that element when next() is called externally.

This method, where the downstream continuously requests data from the upstream, can also be called a pull-based model.

This is where Sequence's laziness comes from.

Unlike regular collections that execute transformations immediately, intermediate operations like map, filter, and flatMap in Sequence do not process all elements right away.

They defer computation until terminal operations like toList(), count(), or first() start consuming the sequence.

Creating a Sequence

We can create a Sequence using sequenceOf() or generateSequence(), or convert a collection to a sequence by calling asSequence().

val numbers = sequenceOf(1, 2, 3, 4, 5)
println(numbers.toList()) // Output: [1, 2, 3, 4, 5]

val generated = generateSequence(1) { it + 1 }
println(generated.take(5).toList()) // Output: [1, 2, 3, 4, 5]

In the second example, generateSequence(1) { it + 1 } produces an infinite sequence with no natural endpoint.

Because Sequence generates elements on demand, we can first use take(5) to limit the quantity, then use toList() to retrieve the first five results.

If toList() or count() were called directly on this infinite sequence, the computation would never naturally terminate.

Transforming a Sequence

Transformation functions like map, filter, and take can also be used on Sequence.

These operations are lazy. That is, calling them merely describes processing steps; elements are only processed when a terminal operation actually starts consuming the results.

val sequence = sequenceOf(1, 2, 3, 4, 5)

val transformed = sequence
    .map { it * 2 }
    .filter { it > 5 }

println(transformed.toList()) // Output: [6, 8, 10]

If we look at the implementation of intermediate operations like map and filter in Sequence, the design is quite clever.

When these operations are called, they don't immediately traverse the original sequence; instead, they create and return a new Sequence object.

The new Sequence holds a reference to the original upstream sequence and the transformation operation to be executed. After multiple operations are chained, a layered structure forms, with each layer preserving one step of the entire computation.

This structure somewhat resembles the Decorator pattern: each subsequent Sequence wraps the previous one, ultimately forming a complete processing chain.

Let's look at a conceptual implementation of Sequence.map():

// This is a simplified version conceptually consistent with the standard library implementation.
// The actual implementation in the standard library uses TransformingSequence.
public fun <T, R> Sequence<T>.map(
    transform: (T) -> R
): Sequence<R> {
    // 1. This does not traverse the original Sequence.
    // 2. It simply returns a new Sequence,
    //    holding the original Sequence and the transform function.
    return object : Sequence<R> {

        override fun iterator(): Iterator<R> {
            // 3. When an external request asks for the new Sequence's iterator,
            //    an Iterator responsible for transformation is created.
            return object : Iterator<R> {

                // 4. Get the Iterator of the upstream original Sequence.
                val originalIterator = [email protected]()

                override fun hasNext(): Boolean {
                    // 5. hasNext() can be directly delegated to the upstream Iterator.
                    return originalIterator.hasNext()
                }

                override fun next(): R {
                    // 6. Only when next() is called externally,
                    //    is one element fetched from upstream and only that one element transformed.
                    val originalElement = originalIterator.next()
                    return transform(originalElement)
                }
            }
        }
    }
}

From this code, we can see that almost no actual data processing occurs when map() is called.

It merely creates a new Sequence, holding the upstream sequence and the transform function—essentially recording a set of instructions for "how data should be transformed later."

filter, take, and other intermediate operations follow a similar approach. Each time an intermediate operation is called, a new layer of wrapping is added to the processing chain.

However, the iterator implementations for different operations are not entirely identical.

For example, map's hasNext() can generally be delegated directly to the upstream; but for filter to determine if there is a "next element that meets the condition," its hasNext() might need to read several elements from upstream and temporarily cache the found result.

Although the specific implementations differ, they follow the same core principle: instead of completing the computation for the entire collection upfront, they perform the work needed for the current element on demand when the downstream requests an element.

Terminal Operations

Before a terminal operation is called, the entire Sequence processing chain remains in a state where no actual execution has occurred.

A terminal operation consumes the elements of the sequence and produces a final result, for example:

• toList()
• forEach()
• count()
• first()

The terminal operation calls the iterator() of the last Sequence in the processing chain.

This last Sequence then requests the iterator of the upstream Sequence it wraps, and so on, layer by layer, back to the original data source.

Once the iterator chain is established, the terminal operation starts calling hasNext() and next(), pulling elements one by one from upstream and passing them through the entire processing chain.

Consider the following example:

val result = (1..10).asSequence()
    .filter {
        println("Filtering $it")
        it % 2 == 0
    }
    .map {
        println("Mapping $it")
        it * 2
    }
    .take(2) // Another intermediate operation
    .toList() // Terminal operation, truly starts the entire processing chain

println("Result: $result")

The actual execution starting point for this code is toList().

Its execution process roughly unfolds as follows:

1. toList() requests the iterator corresponding to take(2) and prepares a list to collect the final results.
2. The take(2) iterator requests the first element from the map iterator.
3. The map iterator continues to request an element from the filter iterator.
4. The filter iterator starts pulling data from the original data source (1..10).
   • Fetches 1, outputs Filtering 1. It doesn't meet the even condition, so it continues searching.
   • Fetches 2, outputs Filtering 2. It meets the condition, so filter returns 2.
5. map receives 2, outputs Mapping 2, performs the transformation 2 * 2 = 4, and returns 4.
6. take(2) passes 4 downstream to toList(). toList() adds it to the result list. At this point, take still allows one more element to be returned.
7. toList() requests the next element again, and take(2) continues to request the second result from map.
8. The above process happens again:
   • filter fetches 3, outputs Filtering 3, condition not met.
   • filter fetches 4, outputs Filtering 4, condition met, so it returns 4.
9. map receives 4, outputs Mapping 4, transforms it to 8 and returns it.
10. take(2) passes 8 to toList(). toList() adds it to the result list. At this point, take(2) has returned two elements.
11. When the downstream checks again for more elements, take(2) returns false. toList() then terminates. Only 1 through 4 from the original data source were actually processed.

The final output is:

Filtering 1
Filtering 2
Mapping 2
Filtering 3
Filtering 4
Mapping 4
Result: [4, 8]

This example demonstrates several core characteristics of Sequence.

• Lazy Execution

  Before a terminal operation is called, intermediate operations do not actually start processing elements.

• Element-by-Element Processing

  An element first goes through filter, then map, and finally reaches take. Only after the current element is fully processed does the next element get pulled.

  For the filter, map, and take used here, the processing does not require creating complete intermediate collections for each step, as is the case with multi-step transformations on regular collections, thus generally reducing extra memory overhead.

• Short-Circuiting Capability

  Operations like take() and first() can cause the entire processing chain to terminate early once they have obtained the required results, without needing to process the remaining elements in the data source.

One more thing to note: lazy execution does not mean that all Sequence operations require no extra state.

Operations like map and filter can process elements one by one; but distinct needs to record elements that have already appeared, and sorting operations typically need to collect data first. Therefore, Sequence avoids many unnecessary intermediate collections, but not all scenarios use only constant-level memory.

Summary

The internal mechanism of Sequence is a classic implementation of lazy evaluation in the Kotlin standard library, and its foundation remains that very simple Iterator interface.

Intermediate operations like map and filter do not execute immediately. They create a new Sequence, wrapping the previous one and saving the operation to be performed, thus gradually building up the complete computation pipeline.

Only when terminal operations like toList(), count(), or first() are called does the final Iterator chain start working. Elements are pulled one by one from the data source and pass sequentially through the entire processing pipeline.

This design avoids many intermediate collections and can cooperate with operations like take() and first() to terminate computation early, making it particularly suitable for the following scenarios:

• Relatively large data volumes;
• Long multi-step transformation chains;
• Only needing the first few results that meet a condition;
• Needing to process on-demand generated data, or even infinite sequences.

However, Sequence does not unconditionally mean "higher performance."

Lazy processing requires extra Sequence and Iterator wrappers, which also adds indirect function calls. For collections with very small data volumes and very simple operations, using regular collection operations directly might be more straightforward, and even faster.

Therefore, a more accurate understanding is not "call asSequence() whenever you see a collection operation," but rather first judging whether the current task can genuinely benefit from lazy computation, avoiding intermediate results, or terminating processing early.

References

• Kotlin Iterator API
• Kotlin Sequences Official Documentation
• Kotlin Language Specification: for loops
• Kotlin Standard Library Sequences.kt