# 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.

### 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.

``````public interface Collection<out E> : Iterable<E>
``````
``````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, ")
}
}
``````
``````filter, filter, filter, map, map, map, forEach, forEach, forEach,
``````
``````/**
* 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)
}
``````
``````/**
* 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
}
``````

## 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.

``````fun main() {
val list = listOf(1, 2, 3)
// 1
list.asSequence().filter {
print("filter, ")
it > 0
}.map {
print("map, ")
}.forEach {
print("forEach, ")
}
}
``````
``````filter, map, forEach, filter, map, forEach, filter, map, forEach,
``````
``````public fun <T> Iterable<T>.asSequence(): Sequence<T> {
return Sequence { this.iterator() }
}
``````

## 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.

``````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
}
}
``````
``````Suspending...0
Suspending...1
Suspending...1
Suspending...2
Suspending...3
Suspending...5
Suspending...8
Suspending...13
``````
``````override suspend fun yield(value: T)
``````

## 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.

``````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())
}
``````
``````public fun <T> sequence(@BuilderInference block: suspend SequenceScope<T>.() -> Unit): Sequence<T> = Sequence { iterator(block) }
``````

## 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.

``````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")
}
``````
``````Printing first value
Apple
Printing second value
Orange
Printing third value
Banana
``````
``````public suspend fun yieldAll(elements: Iterable<T>)
``````
``````fun main() {
// 1
val sequence = iterableExample()

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

fun iterableExample() = sequence {
// 2
yieldAll(1..5)
}
``````
``````1 2 3 4 5
``````
``````public suspend fun yieldAll(sequence: Sequence<T>) = yieldAll(sequence.iterator())
``````
``````fun main() {
// 1
val sequence = sequenceExample().take(10)

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

fun sequenceExample() = sequence {
// 2
yieldAll(generateSequence(2) { it * 2 })
}
``````
``````2 4 8 16 32 64 128 256 512 1024
``````

## Key Points

1. `Collection`s are eagerly evaluated; i.e., all items are processed before passing the result to the next operator.
2. `Sequence`s 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 `Sequence`s, 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 `Iterable`s 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.

Have a technical question? Want to report a bug? You can ask questions and report bugs to the book authors in our official book forum here.