Arrays, Collections,… And Sequences

map(), fold(), and similar higher-order functions in Kotlin can be used with arrays and many types of collections, such as List.

They can also be used with Sequence. Unlike List — which has its origins in the Java java.util.List type — Sequence is a Kotlin-specific type. On the surface it can be used a lot like a List, particularly in functional programming. In reality, Sequence is a substantially different construct.

What’s a Sequence?

Technically, Sequence is more comparable with Java’s Iterable. Both interfaces have an iterator() method that returns some Iterator to iterate over stuff. In Java, all of the one-dimensional collection classes that you are used to, like ArrayList and HashSet, have implementations of Iterable.

The difference lies in the implied contract. The assumption is that an Iterable represents an actual collection of stuff, where that stuff exists in memory and can be iterated over. As a result, Iterable also has methods like forEach() that take advantage of this concrete collection. Sequence, by contrast, is lazy, meaning that there should be no assumption that the data over which you are iterating actually exists prior to being handed to the iterator.

Ummmm… Why Bother?

Kotlin’s developers designed its higher-order functions that work on Sequence to be item-at-a-time, whereas they needed to make their higher-order functions that work on Iterable to be collection-at-a-time.

Let’s turn back to an example from earlier in the chapter:

data class Event(val id: Int)

fun main() {
  val events = listOf(Event(1), Event(5), Event(1337), Event(24601), Event(42), Event(-6))

  val evenNegativeEvent = events.filter { it.id % 2 == 0 }.firstOrNull { it.id < 0 }

  println(evenNegativeEvent)
}

Here, we chain two higher-order functions: filter() and firstOrNull(). These are being applied to a List, which implements Iterable. As a result, what happens is:

• We create a List of six Event objects
• filter() creates a List of two Event objects (those with an ID that is even)
• firstOrNull() returns a single Event

Let’s change this a bit, by adding a map() operation and changing the order of the events so that the -6 one is second:

val events = listOf(Event(1), Event(-6), Event(5), Event(1337), Event(24601), Event(42))

val evenNegativeEvent = events
  .map { it.id }
  .filter { it % 2 == 0 }
  .firstOrNull { it < 0 }

println(evenNegativeEvent)

Now, the flow is:

• We create a List of six Event objects
• map() creates a List of six Integer objects
• filter() creates a List of two Integer objects (those that are even)
• firstOrNull() returns a single Integer

For a starter list of six objects, that is not too bad. But imagine that the list had 6,000 objects. Now, we are allocating memory for the 6,000-item initial list, the 6,000-item list from map(), plus some smaller list from filter().

With a Sequence, each item is processed through the entire chain on an item-by-item basis. With that, our flow would be:

• We create a Sequence of six Event objects
• map() emits the first Integer (1)
• filter() skips that item, as it is not even
• map() emits the second Integer (-6)
• filter() emits -6, since it is even
• firstOrNull() returns -6, since it is negative
• …and we are done

This is much more memory efficient, as we are not creating intermediate List objects. Those gains can be quite significant for large lists and complex chains of higher-order functions.

How Do I Get a Sequence?

There are many ways to get your hands on a Sequence, either by creating one from scratch or getting one from something else.

sequenceOf()

Just as we have arrayOf(), listOf(), and so forth, we have a sequenceOf() global function in Kotlin to create a Sequence from a set of items known at compile time.

So, for example, the Sequence scenario outlined above looks like:

data class Event(val id: Int)

fun main() {
  val events = sequenceOf(Event(1), Event(-6), Event(5), Event(1337), Event(24601), Event(42))

  val evenNegativeEvent = events
    .map { it.id }
    .filter { it % 2 == 0 }
    .firstOrNull { it < 0 }

  println(evenNegativeEvent)
}

asSequence()

If you already have a List or Array, you can call asSequence() on it to get a Sequence based on the List or Array contents. This may be useful if some code other than yours is creating the List or Array, so you cannot start with a Sequence yourself.

generateSequence()

The generateSequence() global function in Kotlin creates a Sequence that is wrapped around a function type (e.g., lambda expression) that you supply. Where that function type gets its data from is up to you. Your function will be called as each item in the Sequence is needed, until such time as your function returns null to signal that you are out of data.

import kotlin.random.Random

fun percentileDice() = Random.nextInt(1,100)

fun main() {
  val sequence = generateSequence {
    percentileDice().takeIf { it < 95 }
  }

  println(sequence.toList())
}

The percentileDice() function generates a random number from 1 to 100, using Random.nextInt() from the Kotlin standard library. Our generateSequence() call then uses a lambda expression that:

• Calls percentileDice() to get a random number
• Uses takeIf() to see if it is less than 95 — takeIf() returns the object it is called upon if the lambda returns true, otherwise it returns null

The lambda expression ends with that takeIf() call, so the lambda expression returns the random number (if it is less than 95) or null. The result is that we have a Sequence of a random number of random numbers. We then use toList() to collect the values in a List, then print that List.

Running this might give you:

[33, 94, 19, 62, 81]

or:

[32, 84, 39, 21, 22, 51, 21, 78, 82, 3, 53, 30, 48, 64, 89, 33, 16, 28, 16, 2, 90, 38, 67, 34, 86, 71, 13]

or:

[]

That latter case is where the very first random number was over 95, so the Sequence terminated immediately.

Note that the null-means-done implementation of generateSequence() means that you cannot use it to generate a Sequence containing null objects.

Elsewhere

When working with APIs, whether from the Kotlin standard library or elsewhere, see if they have options to return a Sequence instead of a List or Array.