article banner (priority)

Sequence builders in Kotlin Coroutines

This is a chapter from the book Kotlin Coroutines. You can find it on LeanPub or Amazon.
In some other languages, like Python or JavaScript, you can find structures that use limited forms of coroutines:
  • async functions (also called async/await);
  • generator functions (functions in which subsequent values are yielded).
We've already seen how async can be used in Kotlin, but this will be explained in detail in the Starting coroutines chapter. Instead of generators, Kotlin provides a sequence builder - a function used to create a sequence[^102_1].
A Kotlin sequence is a similar concept to a collection (like List or Set), but it is evaluated lazily, meaning the next element is always calculated on demand, when it is needed. As a result, sequences:
  • do the minimal number of required operations;
  • can be infinite;
  • are more memory-efficient[^102_2].
Due to these characteristics, it makes a lot of sense to define a builder where subsequent elements are calculated and "yielded" on demand. We define it using the sequence function. Inside its lambda expression, we can call the yield function to produce the next elements of this sequence.
val seq = sequence {
    yield(1)
    yield(2)
    yield(3)
}

fun main() {
    for (num in seq) {
        print(num)
    } // 123
}
The sequence function here is a small DSL. Its argument is a lambda expression with a receiver (suspend SequenceScope<T>.() -> Unit). Inside it, the receiver this refers to an object of type SequenceScope<T>. SequenceScope<T> has functions like yield. When we call yield(1), it is equivalent to calling this.yield(1) because this can be used implicitly. If this is your first contact with lambda expressions with receivers, I recommend starting from learning about them and about DSL creation, as they are used intensively in Kotlin Coroutines. I explained DSL creation in detail in the book Functional Kotlin.
What is essential here is that each number is generated on demand, not in advance. You can observe this process clearly if we print something in both the builder and in the place where we handle our sequence.
import kotlin.*

//sampleStart
val seq = sequence {
    println("Generating first")
    yield(1)
    println("Generating second")
    yield(2)
    println("Generating third")
    yield(3)
    println("Done")
}

fun main() {
    for (num in seq) {
        println("The next number is $num")
    }
}
// Generating first
// The next number is 1
// Generating second
// The next number is 2
// Generating third
// The next number is 3
// Done
//sampleEnd
Let's analyze how it works. We ask for the first number, so we enter the builder. We print "Generating first", and we yield number 1. Then we get back to the loop with the yielded value, and so "Next number is 1" is printed. Then something crucial happens: execution jumps to the place where we previously stopped to find another number. This would be impossible without a suspension mechanism, as it wouldn't be possible to stop a function in the middle and resume it from the same point in the future. Thanks to suspension, we can do this as execution can jump between main and the sequence generator.

When we ask for the next value in the sequence, we resume in the builder straight after the previous yield.
To see it more clearly, let's manually ask for a few values from the sequence.
import kotlin.*

//sampleStart
val seq = sequence {
    println("Generating first")
    yield(1)
    println("Generating second")
    yield(2)
    println("Generating third")
    yield(3)
    println("Done")
}

fun main() {
    val iterator = seq.iterator()
    println("Starting")
    val first = iterator.next()
    println("First: $first")
    val second = iterator.next()
    println("Second: $second")
    // ...
}

// Prints:
// Starting
// Generating first
// First: 1
// Generating second
// Second: 2
//sampleEnd
Here, we used an iterator to get the next values. At any point, we can call it again to jump into the middle of the builder function and generate the next value. Would this be possible without coroutines? Maybe, if we dedicated a thread for that. Such a thread would need to be maintained, and that would be a huge cost. With coroutines, it is fast and simple. Moreover, we can keep this iterator for as long as we wish as it costs nearly nothing. Soon we will learn how this mechanism works under the hood (in the Coroutines under the hood chapter).

Real-life usages

There are a few use cases where sequence builders are used. The most typical one is generating a mathematical sequence, like a Fibonacci sequence.
import java.math.BigInteger

//sampleStart
val fibonacci: Sequence<BigInteger> = sequence {
    var first = 0.toBigInteger()
    var second = 1.toBigInteger()
    while (true) {
        yield(first)
        val temp = first
        first += second
        second = temp
    }
}

fun main() {
    print(fibonacci.take(10).toList())
}
// [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]
//sampleEnd
This builder can also be used to generate random numbers or texts.
fun randomNumbers(
    seed: Long = System.currentTimeMillis()
): Sequence<Int> = sequence {
    val random = Random(seed)
    while (true) {
        yield(random.nextInt())
    }
}

fun randomUniqueStrings(
    length: Int,
    seed: Long = System.currentTimeMillis()
): Sequence<String> = sequence {
    val random = Random(seed)
    val charPool = ('a'..'z') + ('A'..'Z') + ('0'..'9')
    while (true) {
        val randomString = (1..length)
            .map { i -> random.nextInt(charPool.size) }
            .map(charPool::get)
            .joinToString("")
        yield(randomString)
    }
}.distinct()
The sequence builder should not use suspending operations other than yielding operations[^102_3]. If you need, for instance, to fetch data, it's better to use Flow, as will be explained later in the book. The way its builder works is similar to the sequence builder, but Flow has support for other coroutine features.
fun allUsersFlow(
  api: UserApi
): Flow<User> = flow {
  var page = 0
  do {
      val users = api.takePage(page++) // suspending
      emitAll(users)
  } while (!users.isNullOrEmpty())
}
We've learned about the sequence builder and why it needs suspension to work correctly. Now that we've seen suspension in action, it is time to dive even deeper to understand how suspension works when we use it directly.
[^102_1]: Even better, it offers flow builders. Flow is a similar but much more powerful concept which we will explain later in the book.
[^102_2]: See item Prefer Sequence for big collections with more than one processing step in the Effective Kotlin.
[^102_3]: And it cannot be, since SequenceScope is annotated with RestrictsSuspension, which prevents the suspend function being called unless its receiver is SequenceScope.