10. Building Sequences & Iterators with Yield

Written by Nishant Srivastava

Functional programming is one of the coolest concepts you can use in Kotlin. In this chapter, you’ll see how you can use coroutines with sequences and iterators in order to manage theoretically infinite collections of data.

Getting started with sequences

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 themselves are not the most efficient. 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 operated upon 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. Now 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:

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

  // 2
  list.filter {
    // 3
    print("filter, ")
    // 4
    it > 0
  // 5
  }.map {
    // 6
    print("map, ")
  // 7
  }.forEach {
    // 8
    print("forEach, ")
  }
}

Here’s what’s going on:

1. Creating a collection — in this case, a list of integers 1,2 and 3.
2. Executing a filter operator on the list.
3. Printing a message "filter, " to standard output.
4. Defining the filter condition — here, any item that is greater than zero.
5. Executing a map operator on the list.
6. Printing a message "map, " to standard output.
7. Executing a forEach operator on the list.
8. Printing a message "forEach, " to standard output.

The output for this is will be as follows:

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

Note: You can find the executable version of the above snippet of code in the starter project in the file called IteratorExample.kt.

Here, notice how each functional operator on the list:

• Iterates over the whole list.
• Processes the result.
• Then passes it to the next functional operator.

For example, filter:

• Runs on the whole list of three items three times.
• Evaluates all the items that are greater than zero.
• Returns a list back that is then passed on to the next functional operator map.

Then, map:

• Runs through the whole resulting list (here it is the same list since all the integers in the list are greater than zero) three times.
• Passes it on to the next functional operator forEach.
• Since nothing was done inside the map operator block except printing a log statement, the resulting list again has three items.

Next, forEach runs three times on the three items in the resulting list.

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 a filterTo function. Drilling down more into the source code of filterTo function:

/**
 * 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, the filter operator eventually 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 resulting ArrayList is returned back to the filter operator. 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 came up with 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 wherein the size isn’t known in advance, like reading lines from a file.

Sequence is based on a 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 (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:

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:

1. Here, asSequence() is used to convert the list to a sequence.

The output for this is as follows:

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

Note: You can find the executable version of the above snippet of code in the starter project in the file called SequenceExample.kt.

Here, first, 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).

The method asSequence() is actually an extension function on the Iterable defined as:

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

Next, notice how 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 code block, 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, thereby 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 recommended to use simple Iterables in most of the cases. The benefit of using a Sequence is only when there is a huge/infinite collection of elements with multiple operations.

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 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 Sequence, it is possible to implement Generators. Generators are a special kind of function that can return values and then can be resumed when they’re called again. Think about lazy, infinite streams of values, like the Fibonacci sequence.

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 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:

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

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

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

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

Here, you are:

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

Output of the above code snippet on execution will be:

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

Note: You can find the executable version of the above snippet of code in the starter project in the file called GeneratorFunctionExample.kt.

Here, notice the use of sequence function inside the generatorFib() function body, which is used to builds 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 the yield() function. 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 execution point will reach yield() function it will suspend. This can be validated from the output of the code snippet, too. Right before the call to yield() function, "Suspending..." is printed to the standard output. Next, when yield() function is encountered, the function suspends and returns the value passed to the yield() function. This value is thus generated in the sequence and, while running through, the forEach is printed on the standard output. The function is then resumed back until the next Fibonacci number is generated and the yield() function is called.

Typically, the code is jumping into the middle of the generatorFib() function and executing a part of it. It works because not only the result is returned in this case but the remaining part of the code also and moving it as it is 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 from where did this yield() function come from? Move onto the next section to find out.

SequenceScope is here to stay

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{} DSL 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.

Thus, when using the sequence{} DSL, body of the DSL is ready to handle suspension function, enabling the usage of yield() and yieldAll() suspension functions.

Yield and YieldAll at your service

Using the yield() function, 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 the yield() function suffices the use case. 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:

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

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

// 3
fun singleValueExample() = sequence {
  // 4
  println("Printing first value")
  // 5
  yield("Apple")

  // 6
  println("Printing second value")
  // 7
  yield("Orange")

  // 8
  println("Printing third value")
  // 9
  yield("Banana")
}

Here, in the code snippet, you are:

1. Creating a sequence using the method singleValueExample().
2. Iterating over the sequence and printing each item.
3. Defining a singleValueExample() function using the sequence DSL.
4. Printing a message “Printing first value” to standard output.
5. Generating the item "Apple" and suspending via the yield() function.
6. Printing a message "Printing second value" to standard output.
7. Generating the item "Orange" and suspending via the yield() function.
8. Printing a message "Printing third value" to standard output.
9. Generating the item "Banana" and suspending via the yield() function.

When you execute this code snippet, the output is:

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

Note: You can find the executable version of the above snippet of code in the starter project in the file called SequenceYieldExample.kt.

The code snippet here is printing one value at a time, suspending, and then resuming back until encountering the next yield() function. 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() function.

However, this leads to the question like how would this work when a sequence is generated over a range? 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 into use. 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:

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

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

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

Here, you are:

1. Creating a sequence using the method iterableExample().
2. Iterating over the sequence and printing each item.
3. Defining the iterableExample() function using the sequence DSL.
4. Generating the integers over a range of 1 to 5 via the yieldAll() function and suspending every time an integer is generated.

On executing this code snippet, the output is:

1 2 3 4 5 

Note: You can find the executable version of the above snippet of code in the starter project in the file called IteratorYieldAllExample.kt.

Here, the sequence generation executes over a range of 1 to 5, using the yieldAll() function the code block suspends and resumes every time a new value is yielded.

In case the sequence becomes infinite, the Kotlin Standard Library provides another helper method, which is basically 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:

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

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

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

Here, you are:

1. Creating a sequence using the method sequenceExample(), but limiting it to 10 items only using the take() method.
2. Iterating over the sequence and printing each item.
3. Defining the sequenceExample() function using the sequence DSL.
4. Generating infinite integers using the generateSequence() function and passing each generated integer to the yieldAll() function.

On executing the code snippet, the output is:

2 4 8 16 32 64 128 256 512 1024 

Note: You can find the executable version of the above snippet of code in the starter project in the file called SequenceYieldAllExample.kt.

Here, the function sequenceExample() generates an infinite sequence, but to keep the program usable the sequence was limited to first 10 items in the sequence by passing the limit via the method call take(10) on the sequenceExample() function, which generates the infinite sequence.

The code block under sequenceExample() function suspends every time an integer is generated, prints the item using the forEach in the main() function, and resumes back when a new item is generated by the generateSequence() function.

Key points

1. Collection are eagerly evaluated; i.e., all items are operated upon completely before passing the result to the next operator.
2. Sequence handles the collection of items in a lazy-evaluated manner; i.e., the items in it are not evaluated until you access them.
3. Sequences are great at representing collection where the size isn’t known in advance, like reading lines from a file.
4. asSequence() can be used to convert a list to a sequence.
5. It is recommended to use simple Iterables in most of the cases, the benefit of using a sequence is only when there is a huge/infinite collection of elements with multiple operations.
6. Generators is a special kind of function that can return values and then can be resumed when they’re called again.
7. Using Coroutines with Sequence it is possible to implement Generators.
8. SequenceScope is defined for yielding values of a Sequence or an Iterator using suspending functions or Coroutines.
9. 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 what is even more interesting is understanding how Coroutines work with Context and Dispatcher. You will be learning about those in the next chapter.