Kotlin’s knowledge induction (viii) — sequence

Before the order

When we explored the functional apis of collections earlier, we found that these functions iterate over collections and create new collections early, where the intermediate results of each step are stored. When there is a large amount of data, the call is very inefficient.

fun main(args: Array<String>) { val list = (1.. 10).toList() list.filter { it % 2 == 0 }.map { it * it }.forEach { println(it) } }Copy the code

The sequence

The sequence performs all processing steps individually for each element, avoiding the construction of intermediate variables and improving the performance of the entire collection processing chain. Also known as lazy collections, sequences, much like streams in Java8, are implementations of the concept of convection provided by Kotlin.

The entry point to the Kotlin lazy collection operation is the Sequence interface. The interface has only iterator methods for retrieving values from sequences.

public interface Sequence<out T> {
    public operator fun iterator(): Iterator<T>
}
Copy the code

Create a sequence

There are four ways to create a sequence:

• 1. Use top-level functionssequenceOf(), taking the element as its argument. (A bunch of top-level functions, like listOf, that create collections)

Val Numbers = sequenceOf,2,3,4,5,6,7,8,9,10 (1)Copy the code

• 2. Use Iterable’s extension functionsasSequence()Convert collections to sequences. (common)

val numbers = (1.. 10).toList().asSequence()Copy the code

• 3, use,generateSequence(). Given a first known element, provide a function to evaluate the next element. This function generates the elements of the sequence until the function argument returns NULL. If the function argument does not return null, the sequence will be an infinite sequence:

val numbers = generateSequence(6){
    it + 2
}
Copy the code

GenerateSequence () provides a finite sequence:

val numbers = generateSequence(6){
    if (it < 10) 
        it + 2 
    else 
        null
}
Copy the code

• 4, the use ofsequence()Function. This function receives a function of typeSequenceScope<T>.() -> UnitThe argument. Can be passed tosequence()Lambda expression of the functionSequenceScopeThe yield() and yieldAll() objects add sequence elements. Yield () is used to add a single sequence element; YieldAll () is used to convert elements of a list or sequence into elements of a new sequence.

Val numbers = sequence{yield(1) yieldAll(listOf(2,3)) yieldAll(setOf (4, 5)) yieldAll (generateSequence (6) {if (it < 10)
            it + 1
        else
            null
    })
}
Copy the code

Intermediate and terminal operations

Sequences can also invoke functional apis like collections, but sequence operations fall into two broad categories: intermediate operations and terminal operations.

Definition of intermediate operations: Intermediate operations are always lazy and return another sequence.

An intermediate operation can be determined by the return information of the function:

// Filter function, return Sequence<T>, intermediate operation. // Note that this is a function type argument with a Sequence<T> receiver! public fun <T> Sequence<T>.filter(predicate: (T) -> Boolean): Sequence<T> {return FilteringSequence(this, true, predicate)} // Map function, returns Sequence<T>, intermediate operation // Note that this is a function type parameter with Sequence<T> receiver!! public fun <T, R> Sequence<T>.map(transform: (T) -> R): Sequence<R> {return TransformingSequence(this, transform)
}
Copy the code

What about inertia? Execute the following example:

val list = (1.. 10).toList() list.asSequence() .filter { println("filter $it")
        it % 2 == 0
    }.map {
        println("map $it")
        it * it
    }
Copy the code

Definition of end operations: Trigger the execution of all deferred calculations (intermediate operations) and return a result, which may be a set, a number, etc.

//for// Note that this is a function type argument with a Sequence<T> receiver! public inline fun <T> Sequence<T>.forEach(action: (T) -> Unit): Unit {for (element inThis) action(element)} this) action(element)} this) action(element)} this) action(element)} public inline fun <T> Sequence<T>.count(predicate: (T) -> Boolean): Int { var count = 0for (element in this) if (predicate(element)) checkCountOverflow(++count)
    return count
}
Copy the code

Why are intermediate operations lazy

I guess many of you are like me, wondering why the intermediate operation is lazy? To find out, you can only look at the source code for analysis, first look at asSequence() :

public fun <T> Iterable<T>.asSequence(): Sequence<T> {
    return Sequence { this.iterator() }
}

public inline fun <T> Sequence(crossinline iterator: () -> Iterator<T>): Sequence<T> = object : Sequence<T> {
    override fun iterator(): Iterator<T> = iterator()
}
Copy the code

The asSequence() function creates an anonymous Sequence anonymous class object and stores the iterator of the collection as the return value of its iterator() method.

In the middle of operation

(You can skip the code and see the result)

# the filter functionPublic fun <T> Sequence<T>. Filter (predicate: (T) -> Boolean): Sequence<T> {// Returns a FilteringSequence objectreturn FilteringSequence(this, true, predicate)
}

internal class FilteringSequence<T>(
    private val sequence: Sequence<T>,
    private val sendWhen: Boolean = true, private val predicate: (T) -> Boolean ) : Sequence<T> { override fun iterator(): Iterator<T> = object : Iterator<T> {val Iterator = sequence. Iterator () // -1for unknown, 0 for done1,for continuevar nextState: Int = -1 var nextItem: T? = null // Calculate the implementation of the intermediate operation (in) private funcalcNext() {
            whileIterator.hasnext ()) {val item = iterator.next() // execute the predicate lambda to determine whether the condition is metifPredicate (item) == sendWhen) {// Predicate (item) == sendWhen) {// Get element nextItem = item and change state nextState = 1return}} nextState = 0} Override fun next(): Tif (nextState == -1)
                calcNext()
            if(nextState == 0) throw NoSuchElementException() Val result = nextItem nextItem = null nextState = -1 @suppress ("UNCHECKED_CAST") // Return valuereturnResult as T} override fun hasNext(): Boolean {result as T} override fun hasNext(): Boolean {result as T} override fun hasNext(): Boolean {result as T} override fun hasNext(): Booleanif (nextState == -1)
                calcNext()
            return nextState == 1
        }
    }
}
Copy the code

# the map function
public fun <T, R> Sequence<T>.map(transform: (T) -> R): Sequence<R> {
    returnTransformingSequence(this, transform) } 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(): RreturnTransformer (iterator.next())} Override fun hasNext(): Boolean {// Use the hasNext() function of the iterator from the previous sequencereturn iterator.hasNext()
        }
    }

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

The code combined with other intermediate operations results in:

• 1. All intermediate operations get the iterator of the previous sequence (since it is a lambda with the receiver of the sequence).
• Iterator (), which implements Sequence, returns an anonymous iterator object.
• 3. The hasNext() function of the iterator object itself calls the hasNext() function of the iterator of the previous sequence, or encapsulates the iterator of the previous sequence.
• 4. The next() function of its iterator object calls the function type argument received by the intermediate operation, and returns a value.
• In general, intermediate operations encapsulate layers of iterators without iterating inside using while or for.

At the end of the operating

(You can skip the code and see the result)

# forEach functionPublic inline fun <T> Sequence<T>. ForEach (action: (T) -> Unit): Unit {public inline fun <T> Sequence<T>.for (element in this) 
        action(element)
}
Copy the code

# the count functionpublic inline fun <T> Sequence<T>.count(predicate: (T) -> Boolean): Int {var count = 0 // iterate (this refers to the Sequence returned by the last middle operation)for (element in this) 
        if (predicate(element)) 
            checkCountOverflow(++count)
    return count
}
Copy the code

The code combined with the other end operations results in:

• 1. The end operation uses the intermediate operation to return the Sequence object (because the end operation is also a lambda with a Sequence receiver) to get the iterator used in the forEach loop. This explains why an intermediate operation needs a terminal operation to be executed, because iterators can only be used in forEach. Only then can the return value of the intermediate operation be returned from next() in the iterator.
• Each element is evaluated in forEach as a value passed to the parameter of the function type.

The overall process is as follows:

If you look at it from a Java perspective, it makes more sense. Let’s start with a wave of decompiled code:

public static final void main(@NotNull String[] args) {
      List list = CollectionsKt.listOf(new Integer[]{1, 2, 3, 4, 5, 6, 7, 8, 9, 10});
      Sequence $this$forEach$iv = SequencesKt.map(SequencesKt.filter(CollectionsKt.asSequence((Iterable)list), (Function1)null.INSTANCE), (Function1)null.INSTANCE);
      int $i$f$forEach = false;
      Iterator var4 = $this$forEach$iv.iterator();

      while(var4.hasNext()) {
         Object element$iv = var4.next();
         int it = ((Number)element$iv).intValue();
         int var7 = false;
         boolean var8 = false; System.out.println(it); }}Copy the code

Extract key codes (1) :

//(1) create a nested Sequence instance of the intermediate operation, and obtain the Sequence object Sequence of the last intermediate operation$this$forEach$iv = SequencesKt.map(SequencesKt.filter(CollectionsKt.asSequence((Iterable)list), (Function1)null.INSTANCE), (Function1)null.INSTANCE);
Copy the code

Simplify this line of code:

Sequence listToSequence = CollectionsKt.asSequence((Iterable)list)

Sequence filterSequence = SequencesKt.filter(listToSequence,(Function1)null.INSTANCE)

Sequence mapSequence = SequencesKt.map(filterSequence,,(Function1)null.INSTANCE)

Sequence $this$forEach$iv = mapSequence
Copy the code

As you can see, the Sequence objects generated by each intermediate operation are nested according to the order in which they are called. Finally, the Sequence object of the last intermediate operation is obtained.

Extract key codes (2) :

// Get the Sequence object Iterator var4 = for the last intermediate operation$this$forEach$iv.iterator(); The next() method of the iterator is called. The next() method of the intermediate operation is executed according to the nested instant of the intermediate operation, and the return value of the intermediate operation is returned. The return value of the last intermediate operation is passed to the end operationwhile(var4.hasNext()) {
 Object element$iv= var4.next(); / /.. }Copy the code

The for loop for the end operation becomes a while loop, but iterates over iterators. In the process of iteration, iterators of each intermediate operation are constantly called to perform the intermediate operation, and finally the value obtained by the intermediate operation is handed over to the terminal operation for processing.

conclusion

Kotlin’s Sequence uses the decorator design pattern to dynamically extend anonymous Sequence objects of collection transformations. The decorative design pattern is about making classes more powerful without inheritance (for example, Java I/O streams). Finally, the iterator of Sequence is called in the end operation for iteration, the intermediate operation is triggered, and its return value is obtained for processing and output.

References:

• Kotlin in Action
• Kotlin website

Android Kotlin series:

Kotlin’s Knowledge generalization (I) — Basic Grammar

Kotlin knowledge generalization (2) – make functions easier to call

Kotlin’s knowledge generalization (iii) — Top-level members and extensions

Kotlin knowledge generalization (4) – interfaces and classes

Kotlin’s knowledge induction (v) — Lambda

Kotlin’s knowledge generalization (vi) — Type system

Kotlin’s knowledge induction (7) — set

Kotlin’s knowledge induction (viii) — sequence

Kotlin knowledge induction (ix) — Convention

Kotlin’s knowledge induction (10) — Delegation

Kotlin’s knowledge generalization (xi) — Higher order functions

Kotlin’s generalization of knowledge (xii) – generics

Kotlin’s Generalization of Knowledge (XIII) — Notes

Kotlin’s Knowledge induction (xiv) — Reflection