10. Building Sequences & Iterators With Yield

Written by Filip Babić

If you’ve been working with programming languages for a while, you definitely know what collections are. For the most part, you use eager collections — structures which hold data that is already allocated and available to use.

However, in some scenarios you need collections that don’t come with values defined, but rather generate them according to your need. These structures are called sequences. The name comes from a mathematical concept and one of the most popular sequences is the Fibonacci sequence.

It defines the following numbers:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144...

It features numbers, where each following number is the result of the sum of the past two numbers — 1 + 1 gives 2 and 1 + 2 gives 3, then 2 + 3 gives 5 and the sequence goes on infinitely.

These are also the two main aspects of each sequence:

1. Its values are defined by a strict rule. Most of the time it’s based on mathematical assumptions.
2. All sequences can produce infinite values, based on their rule.

Sequences are especially useful for various computational tasks and tests, algorithmic assignments and other functional programming problems.

Let’s see how to build them using Kotlin Coroutines.

Getting Started With Sequences

To follow along the code in this chapter, open this chapter’s project using IntelliJ, by pressing Open project. Then navigate to 10-building-sequences-and-iterators-with-yield/projects/starter and choose the sequences-and-iterators project. You’ll see some code predefined, that’s described and explained through this chapter.

Let’s start with iterators first.

Iterating Over Values

Kotlin provides many ways to manage collections of data with a well-defined Collections API together with many functional operators at your disposal.

However, collections are not always the most efficient solution. There are many cases in which they lead to lower performance and can cause bottlenecks when executing multiple operations on multiple items. That is mostly because all the functional operators on a Collection are eagerly evaluated; i.e., all items are processed completely before passing the result to the next operator.

To provide more insight, take a look at the signature of Collection interface:

public interface Collection<out E> : Iterable<E> 

As you can see, the Collection interface inherits from Iterable interface. Iterable<E> is non-lazy by default or eager-evaluated. Thus, all collections are eager-evaluated.

To demonstrate the eager-evaluation nature of Iterable, check out the below code snippet, that’s available in IteratorExample.kt:

fun main() {
  // 1
  val list = listOf(1, 2, 3)

  // 2
  list.filter {
    print("filter, ")
    it > 0
  }.map { // 3
    print("map, ")
    it.toString()
  }.forEach { // 4
    print("forEach, ")
  }
}

There are a few things going on here:

1. You first create a collection — in this case, a List of numbers 1, 2 and 3.
2. Then you execute a filter on the list in which you print a statement which shows that you’re filtering the value. You’ll filter all values which are greater than zero.
3. Next, you execute a map on the list that transforms the number into a String, while printing a statement which shows you’re mapping the value.
4. Finally, you call forEach on the list, which prints the final statement for each of the iterations.

The output for this will be as follows:

filter, filter, filter, map, map, map, forEach, forEach, forEach,

Notice how each operator on the list iterates over the whole list to process the result for each item, finally passing the items to the next functional operator.

To understand how the process ended up to be like above, take a look at the source code of one of the functional operator filter:

/**
 * Returns a list containing only elements matching the given [predicate].
 */
public inline fun <T> Iterable<T>.filter(predicate: (T) -> Boolean): List<T> {
    return filterTo(ArrayList<T>(), predicate)
}

filter is an extension function that returns the result from filterTo. Drilling down more into the source code of filterTo:

/**
 * Appends all elements matching the given [predicate] to the given [destination].
 */
public inline fun <T, C : MutableCollection<in T>> Iterable<T>.filterTo(destination: C, predicate: (T) -> Boolean): C {
    for (element in this) if (predicate(element)) destination.add(element)
    return destination
}

As is evident from source code, filter executes a simple for loop over all elements, effectively checking against the condition in an if block to append elements to the new ArrayList. When done iterating over all the items and appending elements to the new ArrayList, the result is returned back to filter. This kind of behavior is similar in other operators, wherein their implementation returns a complete collection back by the time they finish executing.

If you were to add more operators to the pipeline, the performance will start to degrade as the number of elements in the collection increase. That is because each operator will first need to run through all the elements in the collection and then return a new collection (of the same kind) as a result to be passed on to the next functional operator, which will do the same. This is taxing in two ways:

1. Memory: New collections are returned at every step.
2. Performance: Complete collections are processed at every step.

This situation effectively makes it impossible to use the Collections API for an infinite collection of elements. The Kotlin language creators noticed this bottleneck issue and came up with a solution.

Enter: Sequence

To overcome such performance bottleneck issues, Kotlin exposes another data structure called Sequence, which handles the collection of items in a lazy evaluated manner. The items processed in a sequence are not evaluated until you access them. They are great at representing collection where the size isn’t known in advance, like reading lines from a file.

In addition to the basic concepts you learned about at the start of the chapter, the Sequence is based on a single basic rule: It allows you to do multiple intermediate operations on a collection of elements but enforces the requirement of having a terminal operation to actually get the result from the sequence. As a result, it is possible for a Sequence to process collections of infinite size elements.

Notice that Sequence is similar to Iterable from Java, which you covered earlier, except it performs lazily whenever possible. The key difference lies in the semantics and the implementation of the Standard Library extension functions for Iterable and Sequence, which both have a method called iterator.

To demonstrate the lazy-evaluation of a Sequence, check out the below code snippet, that’s available in SequenceExample.kt:

fun main() {
  val list = listOf(1, 2, 3)
  // 1
  list.asSequence().filter {
    print("filter, ")
    it > 0
  }.map {
    print("map, ")
  }.forEach {
    print("forEach, ")
  }
}

Here, the code snippet is exactly as it was for Iterable earlier, except you use asSequence to convert the List to a sequence.

The output for this is as follows:

filter, map, forEach, filter, map, forEach, filter, map, forEach,

Notice the call to asSequence function on the list. Sequences can be created in various ways. The most common use case is to create a sequence from a collection of elements by calling the method asSequence on an Iterable type, such as a list, set or map.

asSequence is an extension function on the Iterable defined as:

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

Notice how, in the example above, each functional operator on the sequence iterates over the whole pipeline on every pass, processes the result at each step and then passes it to the next functional operator.

For example, filter:

• Runs on the first item in the sequence.
• Prints "filter, ".
• Evaluates if the item is greater than zero and returns the result back.

This resulting item is then passed on to the next functional operator map. Here, under the map operator code block, a print statement is executed which prints "map, " to standard output. Since nothing is processed the item is passed to the next operator in the pipeline, forEach.

Now, under forEach, a print statement is executed which prints "forEach, " to standard output and the iteration completes. The next iteration of the sequence is processed next over the whole pipeline and so on, until all iterations are executed, resulting in the right output.

It is quite evident that using Sequence helps to avoid unnecessary temporary allocations overhead and may significantly improve the performance of complex processing pipelines because the whole collection of items is not required to be evaluated when processing. At the same time, the Sequence structure enables you to easily operate upon collections of elements by chaining pure function calls with a rich and fluent API.

However, laziness also introduces some overhead, which is undesirable for common simple transformations of smaller collections and makes them less performant. It is still recommended to use simple Iterables in most of the cases. The benefit of using a Sequence is only when there is a large or infinite collection of elements with multiple operations, especially if you are filtering items.

Note: Java 8 and Scala both have the concept of streams, which is the same as a Sequence. Kotlin chose to use Sequence as a new class to avoid naming conflicts when running on a Java 8 JVM and also be able to backport it to older JVM targets.

Knowing about how to process an infinite collection of items in Kotlin opens up the door to many more possibilities of working with infinite items. One of those possibilities is of building generator functions.

Generators & Sequences

Using Coroutines with sequences, it is possible to implement generators. Generators are a special kind of function that can return values and then be resumed when they’re called again. Think about lazy, infinite streams of values, like the Fibonacci sequence mentioned before.

Note: You can also find generator functions in other languages such as Python and Javascript where they exist with the yield keyword.

Owing to the lazy-evaluated behavior of Sequence and the suspend-resume concept from using Coroutines, creating a generator function is quite easy.

To understand how that can be achieved, take a look at the below code snippet about generating an infinite sequence of Fibonacci numbers, that’s available in GeneratorExample.kt:

fun main() {
  // 1
  val sequence = generatorFib().take(8)

  // 2
  sequence.forEach {
    println("$it")
  }
}

// 3
fun generatorFib() = sequence {
  // 4
  print("Suspending...")

  // 5
  yield(0L)
  var cur = 0L
  var next = 1L
  while (true) {
    // 6
    print("Suspending...")
    // 7
    yield(next)
    val tmp = cur + next
    cur = next
    next = tmp
  }
}

There is a lot going on here. You are:

1. Creating a sequence using generatorFib but limiting it to eight items only using take(8).
2. Iterating over the sequence and printing each item.
3. Returning a Sequence within generatorFib.
4. Printing a message "Suspending..." to standard output.
5. Generating the item 0 and suspending via yield.
6. Printing a message "Suspending..." to standard output.
7. Generating infinitely the next item in the Fibonacci numbers sequence and suspending via yield.

Running the above code snippet will output the following:

Suspending...0
Suspending...1
Suspending...1
Suspending...2
Suspending...3
Suspending...5
Suspending...8
Suspending...13

Here, notice the use of sequence inside the generatorFib body, which is used to build a Sequence lazily generating values one by one.

This will suspend when values are not needed and it will end appropriately when the sequence is no longer being used or is exhausted.

Take note of yield. This function is a suspending function as is visible from its signature from the source code:

override suspend fun yield(value: T)

This means that whenever the execution point reaches yield, it will suspend. This can be validated from the output of the code snippet, too. Right before the call to yield, "Suspending..." is printed to the standard output. Next, when yield function is encountered, the function suspends and returns the value passed to yield. The sequence generates the value and while running through forEach, you print it out. The function is then resumed back until the next Fibonacci number is generated and you call yield.

Typically, the code jumps into the middle of the generatorFib and executes a part of it. It works because not only the result is returned in this case but the remaining part of the code as well.

Then the execution point moves with the instance of a Continuation; i.e., result of the function along with the context of where the code returned.

However, the more important question here is where did this yield come from? Move onto the next section to find out!

Yielding From SequenceScope

When working with Coroutines, you need to define a scope within which the coroutines or suspension functions will work. SequenceScope is defined for the same reason, for yielding values of a Sequence or an Iterator using suspending functions or coroutines.

Taking a peek at the source code provides more insight:

public abstract class SequenceScope<in T> internal constructor() {

    public abstract suspend fun yield(value: T)

    public abstract suspend fun yieldAll(iterator: Iterator<T>)

    public suspend fun yieldAll(elements: Iterable<T>) {
        if (elements is Collection && elements.isEmpty()) return
        return yieldAll(elements.iterator())
    }

    public suspend fun yieldAll(sequence: Sequence<T>) = yieldAll(sequence.iterator())
}

Thus SequenceScope provides yield and yieldAll suspension functions.

The next question is how does this all tie up in the sequence?

Well, turns out that the sequence {} syntax that was used earlier passes SequenceScope as the only argument to it.

public fun <T> sequence(@BuilderInference block: suspend SequenceScope<T>.() -> Unit): Sequence<T> = Sequence { iterator(block) }

Since Kotlin allows to convert functions with a single argument to be replaced by a lambda expression in place of the single argument, what you have is a sequence {} DSL that provides a SequenceScope.

In turn, when using sequence {}, the body is ready to handle suspension functions, enabling the use of yield and yieldAll suspension functions.

Providing Values With Yield & YieldAll

Using yield, there are various ways by which a generator function can be written to handle infinite collections of data.

When considering a Sequence that generates a single value, simply using yield is enough. It suspends the sequence when encountered and resumes back for the next iteration and so on.

Here is a working example to demonstrate the functionality, available in SequenceYieldExample.kt:

fun main() {
  // 1
  val sequence = singleValueExample()
  sequence.forEach {
    println(it)
  }
}

fun singleValueExample() = sequence {
  // 2
  println("Printing first value")
  yield("Apple")

  // 3
  println("Printing second value")
  yield("Orange")

  // 4
  println("Printing third value")
  yield("Banana")
}

Again, several things going on in the snippet above::

1. You create a sequence using singleValueExample and iterate over it to print each item.
2. Within singleValueExample you first print a statement and then yield("Apple").
3. Then you do the same for the second value — “Orange”.
4. And finally the third value — “Banana”.

When you execute this code snippet, the output is:

Printing first value
Apple
Printing second value
Orange
Printing third value
Banana

The code snippet here is printing one value at a time, suspending and then resuming back until encountering the next yield. It is quite a simple process in which the items are being generated one by one and yield is making sure that the items are processed one at a time. Effectively, one can keep on yielding more values via the yield.

However, this leads to the question of how this would work when a sequence is generated over a range of values? You probably wouldn’t want to call the yield function every time a new value is generated in a sequence within a range of items. This is where the function yieldAll(elements: Iterable<T>) comes in handy. The signature of this function is as follows:

public suspend fun yieldAll(elements: Iterable<T>)

To demonstrate the behavior, here is a functional example code snippet, available in IteratorYieldAllExample.kt:

fun main() {
  // 1
  val sequence = iterableExample()

  sequence.forEach {
    print("$it ")
  }
}

fun iterableExample() = sequence {
  // 2
  yieldAll(1..5)
}

Here, you:

1. Create a sequence using iterableExample and iterate over it, printing each item.
2. Generate the integers in the range of [1..5] via yieldAll and suspend every time you generate an integer.

On executing this code snippet, the output is:

1 2 3 4 5 

In case the sequence becomes infinite, the Kotlin Standard Library provides another helper method, which is an overloaded function named yieldAll(sequence: Sequence<T>); i.e., it takes in a sequence as an argument instead of an iterator.

Here is the declaration of the function from the source code:

public suspend fun yieldAll(sequence: Sequence<T>) = yieldAll(sequence.iterator())

To demonstrate the usage, checkout the below example, which is available in SequenceYieldAllExample.kt:

fun main() {
  // 1
  val sequence = sequenceExample().take(10)

  sequence.forEach {
    print("$it ")
  }
}

fun sequenceExample() = sequence {
  // 2
  yieldAll(generateSequence(2) { it * 2 })
}

Once again, you do the following:

1. Create a sequence using sequenceExample and iterate over it, printing each item.
2. Generate an infinite number of integers using generateSequence and passing each generated integer to the yieldAll function. The way the values are generated, is by starting off with the number two and then doubling it.

On executing the code snippet, the output is:

2 4 8 16 32 64 128 256 512 1024

sequenceExample generates an infinite sequence, but to keep the program usable the sequence was limited to first 10 items in the sequence by calling take(10) on sequenceExample, which generates the infinite sequence.

The code block under sequenceExample suspends every time an integer is generated. This is why you can print the item using forEach in main and go back to generating a new value, which you then print.

And so on infinitely, or at least until you either run out of memory or you reach the last item you requested using take.

Key Points

1. Collections are eagerly evaluated; i.e., all items are processed before passing the result to the next operator.
2. Sequences handle the collection of items in a lazy-evaluated manner; i.e., the items in it are not evaluated or allocated until you access them.
3. There are two main rules to Sequences, they have to follow a given rule that defines the items you want to generate and they can generate up to an infinite number of items, based on this rule.
4. Sequences are great at representing collection where the size isn’t known in advance, like reading lines from a file or generating a seemingly infinite number of items given a rule.
5. asSequence can be used to convert a List to a sequence.
6. It is recommended to use simple Iterables in most cases. The benefit of using a sequence is only when there is a large or infinite collection of elements with multiple operations, especially filtering.
7. Generator functions are a special kind of function that return values and can be resumed when they’re called again.
8. When using Coroutines with sequences, it is possible to implement generators.
9. SequenceScope is defined for yielding values of a Sequence or an Iterator using suspending functions or Coroutines.
10. SequenceScope provides yield and yieldAll suspending functions to enable generator function behavior.

Where to Go From Here?

Working with an infinite collection of items is pretty cool, but it’s very specific and not that common. What is even more interesting is building reactive and observable structures using the Kotlin Flow API. You’ll learn about those in the next chapter.