How Sequence Work Compare to List Under The Hood In Kotlin

Photo by Alexander Andrews on Unsplash

Today, I am gonna talk about Sequence in Kotlin and how it works under the wood. As Sequence, what we mainly talk about is the operator lambda function and how is it difference from List interface.

Sequence is similar to Collection library from Java

public interface Sequence<out T> {

public operator fun
iterator(): Iterator<T>
}

The same as List, instead, it only has one function which return iterator object.

The operators are all extension function which we would talk about below.

This is a simple way to create a Sequence object

val seq : Sequence = listOf(1,2,3).asSequence()

asSequence() function is a Iterable extension function

public fun <T> Iterable<T>.asSequence(): Sequence<T> {    // Create by Sequence anonymous class use the iterator same as list object     return Sequence { this.iterator() }
}

From above of code, we can tell we need to create a List object first, then use asSequence function to transform List object to Sequence object.

So why we need Sequence if we already have List. Here is a simple difference from their operator perspective.

We have two simple operator function.

val list : List<Int> = listOf(1,2,3).also { list ->
list.map { it + 1 }.filter { it != 1 }
}
val seq : Sequence = listOf(1,2,3).also { seq ->
seq.map { it + 1 }.filter { it != 1 }
}

On List object, it would go through all the elements inside the list, return a new List object, then go to the next operator function filter , we start again the process.

We take a simple look at map function from List

public inline fun <T, R> Iterable<T>.map(transform: (T) -> R): List<R> {
return mapTo(ArrayList<R>(collectionSizeOrDefault(10)), transform)
}
public inline fun <T, R, C : MutableCollection<in R>> Iterable<T>.mapTo(destination: C, transform: (T) -> R): C {
for (item in this)
destination.add(transform(item))
return destination
}

We can see it would create a new List object for storing the new transformed elements to destination

So if we have 10 operator, it would create 10 List objects and it needs to iterate all elements until they all have added to the list.

Now, Let’s take a look at Sequence source code.

The signature for each operator is similar, so I take map function as a sample.

public fun <T, R> Sequence<T>.map(transform: (T) -> R): Sequence<R> {
return TransformingSequence(this, transform)
}

Same as List, it takes a lambda function as an argument.

internal class TransformingSequence<T, R>
constructor(private val sequence: Sequence<T>, private val transformer: (T) -> R) : Sequence<R> {
override fun iterator(): Iterator<R> = object : Iterator<R> {
val iterator = sequence.iterator()
override fun next(): R {
return transformer(iterator.next())
}

override fun hasNext(): Boolean {
return iterator.hasNext()
}
}

internal fun <E> flatten(iterator: (R) -> Iterator<E>): Sequence<E> {
return FlatteningSequence<T, R, E>(sequence, transformer, iterator)
}
}

But here is the major difference.

For map , it would create a new Sequence object from TransformingSequence which is implement Sequence interface and it has its own implementation for iterator function.

TransformingSequence has two properties, a sequence which refers to the previous sequence and a transformer as transformation lambda function.

On iterator function, if you take a closer look, you will understand now.

Basically, sequence only transforms the element when you call next()

If we need to use the sequence after transformation, we need to call a toList()

So no matter how many operators you have, it only operates the operator when you call toList . For each operator, it would transform the sequence to a difference object, and update the current iterator .

On iterator implementation

override fun next(): R {
return transformer(iterator.next())
}

We can see that this is a recursive function.

We get the current element from the previous sequence , use transformer to transform the current element to a new element, then we iterate the next element.

So on the sample

val seq : Sequence = listOf(1,2,3).also { seq -> 
seq.map { it + 1 }.filter { it != 1 }.toList()

It would do the map function, 1+1 then go through filter 2 != 1 , and so on…

That’s it ! Thank you for reading !

If I have some mistakes on this article, please comment below.

If you want to read more about Sequence , check out this article.

--

--

--

Enjoy Coding everyday

Love podcasts or audiobooks? Learn on the go with our new app.

Recommended from Medium

Pragmatic Rules for Teams building Restful Services

How to Enable and Set Rolling for MYSQL General Log in a MYSQL RDS Instance

Ideas Become Reality: Rapid Prototyping Web Apps With Django & Python

“WePiggy’s Billionaires” Activity on WePiggy-Harmony Is About to End

Creating a parser for a programming language (xdlang part 3)

The other kind of JavaScript fatigue

Raspberry Pi Course for Beginners

Sharp electric sport wagon packs speedy-charging 800V tech

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Jimmy leo

Jimmy leo

Enjoy Coding everyday

More from Medium

SOLID Principle

Coroutine Fundamental

Lost in Java Time with Android

The Easiest Way to Reuse ViewModel Factory using Dagger