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.
