Kotlin Christmas

Lists vs. Sequences

A 3 minute read written by
Øyvind Midtbø
23.12.2019

Previous postNext post

The Kotlin library comes with several container types. Two of these are List and Sequence. At the first glance these two look quite similar, but we will look at the differences in this article.

A List implements the Collection interface, which again implements the Iterable interface. A List is an ordered collection of elements, and every element can be accessed by an index.

val numbersList = listOf(1, 2, 3, 4)
println(numbersList[1]) // 2
println(numbersList.indexOf(4)) // 3

The listOf() method returns an immutable list, and as a result you can't add or remove objects. If you want to work with a mutable list, you can specify that when creating the list:

val mutableNumbersList = mutableListOf("a", "a", "b", "c", "d")
mutableNumbersList.remove("a") // Removes the first occurrence
mutableNumbersList.add("e")
println(mutableNumbersList) // [a, b, c, d, e]

Note that although the list is created as a constant with the val keyword, you can still add or remove objects. The reason for that is that write operations modify the object and not the object reference.

A Sequence offers the same functionality as Iterable, but implements another approach to multi-step collection processing.

val numbersSequence = sequenceOf(1, 2, 3, 4)
println(numbersSequence.elementAt(1)) // 2
println(numbersSequence.indexOf(4)) // 3

You can also create a sequence from an Iterable:

val letters = listOf("a", "b", "c", "d")
val lettersSequence = letters.asSequence()

On both sequences and lists you can operate upon collection of elements, like you can see in this example:

data class Country(val name: String, val population: Long)

val countries = listOf(
    Country("Norway", 5_300_000),
    Country("Denmark", 5_600_000),
    Country("Sweden", 10_100_000),
    Country("Finland", 5_500_000),
    Country("Germany", 82_800_000)
)

val bigCountries1 = countries
    .filter { it.population > 6_000_000 }
    .map { it.name }

println(bigCountries1) // [Sweden, Germany]

val bigCountries2 = countries
    .asSequence()
    .filter { it.population > 6_000_000 }
    .map { it.name }
    .toList()

println(bigCountries2) // [Sweden, Germany]

Now let's look at the difference between sequences and lists. If a sequence operation returns another sequence, it’s an intermediate function. If it doesn’t return a sequence, it’s terminal. Sequences are lazy, so intermediate functions for sequences don’t do any calculations. All the calculations are added to the sequence, and they are not executed until a terminal operation is called. On a list, however, the intermediate function does the calculation and returns a new collection.

If we expand the example above with some print statements, we can see how the program executes:

println("List:")
val bigCountries1 = countries
    .filter {
        println("Filters the population: ${it.name}")
        it.population > 6_000_000
    }
   .map {
        println("Maps the name: ${it.name}")
        it.name
    }

println(bigCountries1) // [Sweden, Germany]
println("\nSequence:")

val bigCountries2 = countries
    .asSequence()
    .filter {
        println("Filters the population: ${it.name}")
        it.population > 6_000_000
    }
    .map {
        println("Maps the name: ${it.name}")
        it.name
    }
    .toList()

println(bigCountries2) // [Sweden, Germany]

The output:

List:
Filters the population: Norway
Filters the population: Denmark
Filters the population: Sweden
Filters the population: Finland
Filters the population: Germany
Maps the name: Sweden
Maps the name: Germany
[Sweden, Germany]

Sequence:
Filters the population: Norway
Filters the population: Denmark
Filters the population: Sweden
Maps the name: Sweden
Filters the population: Finland
Filters the population: Germany
Maps the name: Germany
[Sweden, Germany]

We can see that the map() function is executed immediately after filter() for Sweden and Germany when the terminal function toList() is called.

In this next example I want to get the three first numbers bigger than 10 in a list. First I can execute the functions directly on the list:

val numbers = listOf(30, 22, 1, 11, 19, 5, 1)

val bigNumbers = numbers
    .filter {
        println("Filters $it")
        it > 10
     }
    .take(3)

println(bigNumbers)

As you can see on the output, all the filter() functions are executed before we take the three first numbers:

Filters 30
Filters 22
Filters 1
Filters 11
Filters 19
Filters 5
Filters 1
[30, 22, 11]

Let's try the same on the sequence:

val bigNumbers = numbers
    .asSequence()
    .filter {
        println("Filters $it")
        it > 10
    }
    .take(3)
    .toList()

println(bigNumbers)

The output:

Filters 30
Filters 22
Filters 1
Filters 11
[30, 22, 11]

Because the intermediate function filter() isn't called before the terminal function toList() is called, the compiler knows that only the first three numbers bigger than 10 are included, and as a result the filter() function is only executed four times.

If you are dealing with big data sets, or doing lots of processing on the data set, it might be smart to consider sequences instead of a normal list.

Read the next post