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:
- Creating a collection — in this case, a list of integers 1,2 and 3.
- Executing a
filteroperator on the list. - Printing a message
"filter, "to standard output. - Defining the filter condition — here, any item that is greater than zero.
- Executing a
mapoperator on the list. - Printing a message
"map, "to standard output. - Executing a
forEachoperator on the list. - 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
mapoperator 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:
- Memory: New collections are returned at every step.
- 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.
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
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
}
}
Suspending...0
Suspending...1
Suspending...1
Suspending...2
Suspending...3
Suspending...5
Suspending...8
Suspending...13
override suspend fun yield(value: T)
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.
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) }
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.
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")
}
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()
// 2
sequence.forEach {
print("$it ")
}
}
// 3
fun iterableExample() = sequence {
// 4
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)
// 2
sequence.forEach {
print("$it ")
}
}
// 3
fun sequenceExample() = sequence {
// 4
yieldAll(generateSequence(2) { it * 2 })
}
2 4 8 16 32 64 128 256 512 1024
Key points
- Collection are eagerly evaluated; i.e., all items are operated upon completely before passing the result to the next operator.
- Sequence handles the collection of items in a lazy-evaluated manner; i.e., the items in it are not evaluated until you access them.
- Sequences are great at representing collection where the size isn’t known in advance, like reading lines from a file.
-
asSequence()can be used to convert a list to a sequence. - 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.
- Generators is a special kind of function that can return values and then can be resumed when they’re called again.
- Using Coroutines with Sequence it is possible to implement Generators.
- SequenceScope is defined for yielding values of a Sequence or an Iterator using suspending functions or Coroutines.
- 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.
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.
Have feedback to share about the online reading experience? If you have feedback about the UI, UX, highlighting, or other features of our online readers, you can send them to the design team with the form below:
© 2021 Razeware LLC
