[Kotlin] Sequence

interface Sequence<out T>

시퀀스의 iterator를 통해 값들을 반환한다. 값들은 lazily 하게 계산되고, 시퀀스는 잠재적으로 무한하게 값을 넣을 수 있다.

시퀀스는 여러번 반복될 수 있지만 몇몇 시퀀스 구현들은 한 번만 반복되도록 제어한다. 후자의 시퀀스는 두 번 반복을 시도할 때 exception을 발생시킨다.

 

interface Iterable<out T>

Iterable 인터페이스를 상속하는 클래스들은 반복 가능한 일련의 요소들로서 표현될 수 있다.

 

kotlinlang.org/docs/sequences.html#from-a-function

Sequences - Help | Kotlin

kotlinlang.org/api/latest/jvm/stdlib/kotlin.sequences/-sequence/

Sequence - Kotlin Programming Language

 

collenctions와 함께, 코틀린 standard library는 sequence(Sequence <T>)라는 또 다른 container 타입을 가지고 있다.

시퀀스는 Iterable과 같은 함수들을 제공하나, multi-step collection(다단계 수집) 처리에 또 다른 접근방법을 구현한다.

 

Iterable의 처리는 여러 단계들을 포함할 때, 그 단계들은 열심히 처리된다. 각 처리 단계가 완료하고 중간 컬렉션인 결과를 반환한다. 다음 단계는 이 중간 컬렉션을 수행한다. 시퀀스의 여러 단계 처리는 가능할 때 게으르게 실행된다. 실제 계산은 전체 프로세스 체인의 결과가 요청될 때에만 일어난다. 

연산 실행 순서도 다르다. Sequence는 모든 하나의 요소마다 모든 처리 단계를 한 단계씩 수행하고, Iterable은 전체 collection의 각 단계를 완료하고 다음 단계로 진행한다.

그래서 시퀀스는 중간 단계의 결과물 생성을 피하기 때문에 전체 콜렉션 처리 체인의 성능을 증가시킨다.
그러나 시퀀스의 게으르다는 특성이 더 작은 콜렉션을 처리하거나 더 간단한 계산을 할 때 상당한 오버헤드를 만든다. 
따라서 Sequence와 Iterable을 동시에 고려해 상황에 따라 어느 것이 더 나은지 결정해야 한다.

 

생성

요소들로

sequnceOf() 함수로 요소들을 매개변수들로 나열한다.

val numbersSequence = sequenceOf("four", "three", "two", "one")

fun <T> sequenceOf(vararg elements: T): Sequence<T>

지정된 값을 반환하는 시퀀스를 생성한다.

Iterable로 

이미 Iterable 객체(List, Set 등)를 가지고 있다면 asSequence()를 호출한다.

val numbers = listOf("one", "two", "three", "four")
val numbersSequence = numbers.asSequence()

asSequence

fun <T>  Array<out T>.asSequence(): Sequence<T>

fun ByteArray.asSequence(): Sequence<Byte>

fun ShortArray.asSequence(): Sequence<Short>

fun IntArray.asSequence(): Sequence<Int>

fun LongArray.asSequence(): Sequence<Long>

fun FloatArray.asSequence(): Sequence<Float>

fun DoubleArray.asSequence(): Sequence<Double>

fun BooleanArray.asSequence(): Sequence<Boolean>

fun CharArray.asSequence(): Sequence<Char>

fun <T> Iterable<T>.asSequence(): Sequence<T>

fun <K, V> Map<out K, V>.asSequence(): Sequence<Entry<K, V>>

함수로

generateSequnce()를 호출해 함수에 기반한 시퀀스를 생성한다. 매개변수로 함수를 넣는다. 선택적으로, 첫 요소는 명시적인 값이나 함수 호출 결과로 지정할 수 있다. 제공된 함수가 null을 리턴할 때 시퀀스 생성이 중지된다. 

 

generateSequence

 

fun <T: Any> getnerateSequence(

    nextFunction: () -> T?

): Sequence<T>

nextFunction이 null을 반환할 때까지 각 iteration에서 다음 값을 계산하는 nextFunction을 호출하는 시퀀스를 반환한다.

 

fun <T: Any> generateSequence(

    seed: T?,

    nextFunction: (T) -> T?

): Sequence<T>

seed 값을 시작 nextFunction 함수의 시작하는 값으로 정의하고, nextFunction이 null을 반환할 때까지 각 iteration에서 다음 값을 계산하는 nextFunction을 호출하는 시퀀스를 반환한다.

 

fun <T: Any> generateSequence(

    seedFunction: () -> T?,

    nextFunction: () -> T?

): Sequence<T>

 

 

아래 예제의 시퀀스는 무한대이다.

fun main() {
    val oddNumbers = generateSequence(1) { it + 2 } // `it` is the previous element
    println(oddNumbers.take(5).toList())
    //println(oddNumbers.count())     // error: the sequence is infinite
}

결과

[1, 3, 5, 7, 9]

유한한 시퀀스를 generateSequence()로 생성하기 위해서는 제공하는 함수가 마지막 요소 뒤에 null을 반환하도록 한다.

fun main() {
    val oddNumbersLessThan10 = generateSequence(1) { if (it < 8) it + 2 else null }
    println(oddNumbersLessThan10.count())
}

결과

5

chunck로

sequence() 함수로 임의의 크기의 chunck(덩어리)들을 요소 하나씩 시퀀스 요소로 생성할 수 있다. 이 함수는 yield()와 yieldAll() 함수들을 포함하는 람다 표현식을 사용한다. 이 yield()와 yieldAll()은 시퀀스 consumer에 요소를 반환하고 consumer가 다음 요소를 요청할 때까지 sequence() 실행을 중단한다. yield()는 매개변수를 하나만 쓴다. yieldAll()은 Iterable 객체, Iterator, 아니면 다른 시퀀스를  매개변수로 쓴다. yieldAll()의 시퀀스 매개변수는 무한할 수 있다. 그러나 이런 호출은 맨 마지막 순서여야 한다. 다른 후속 호출들이 실행되지 않을 수 있기 때문이다.

 

fun main() {
    val oddNumbers = sequence {
        yield(1)
        yieldAll(listOf(3, 5))
        yieldAll(generateSequence(7) { it + 2 })
    }
    println(oddNumbers.take(5).toList())
}

결과

[1, 3, 5, 7, 9]

 

kotlin-stdlib/kotlin.sequences/SequenceScope

 

abstract suspend fun yield(value:T)

생성중인(being built) Iterator에 value를 제공하고 다음 value가 요청될 때까지 일시 중단한다.

 

abstract suspend fun yieldAll(iterator: Iterator<T>)

 iterator로부터 모든 값들이 반복되고 다음 값이 요청될 때까지 생성되고 중단할 Iterator로 모든 값들을 산출한다.

suspend fun yieldAll(element: Iterable<T>)

iterator로부터 모든 값들이 반복되고 다음 값이 요청될 때까지 생성되고 중단할 Iterator로 값들의 collection 하나를 산출한다.

suspend fun yieldAll(sequence: Sequence<T>)

iterator로부터 모든 값들이 반복되고 다음 값이 요청될 때까지 생성되고 중단할 Iterator로 값들이 무한대일 수 있는 시퀀스를 산출한다.

 

 

시퀀스 작업

시퀀스 연산(작업)은 상태 요구사항에 따라 아래의 그룹들로 분류할 수 있다.

• Stateless 연산들은 상태를 필요로 하지 않고 각 element를 독립적으로 처리하는데, 예를 들어서, map() 또는 filter()가 있다. Stateless 연산들이 element를 처리하는데 일정량의 state가 필요할 수도 있다. 예를 들면 take(), drop()이 있다.
• State 연산들은 상당량의 상태를 요구하는데, 대개 시퀀스의 element의 수에 비례한다.

만약 시퀀스 연산이 다른 시퀀스를 lazily 하게 생성해 반환하다면, intermediate라고 불린다. 다른 경우에 이 연산은 terminal이다. terminal 연산의 예로는 toList()와 sum()이 있다. 시퀀스 요소들은 terminal 연사들에서만 받아올 수 있다.

 

시퀀스들은 여러 번 반복될 수 있으나 몇몇 시퀀스 구현들은 한 번만 반복되도록 제한한다. 

 

Iterable

단어 리스트를 가지고 있다고 해보자. 아래의 코드는 글자 수가 3을 넘으면 단어를 필터링하고 필터링된 단어의 첫 4개만 길이를 출력한다.

fun main() {    
    val words = "The quick brown fox jumps over the lazy dog".split(" ")
    val lengthsList = words.filter { println("filter: $it"); it.length > 3 }
        .map { println("length: ${it.length}"); it.length }
        .take(4)

    println("Lengths of first 4 words longer than 3 chars:")
    println(lengthsList)
}

결과

filter: The
filter: quick
filter: brown
filter: fox
filter: jumps
filter: over
filter: the
filter: lazy
filter: dog
length: 5
length: 5
length: 5
length: 4
length: 4
Lengths of first 4 words longer than 3 chars:
[5, 5, 5, 4]

 

이 코드를 실행할 때, filter()와 map() 함수가 코드에서 나타난 순서대로 실행되는 것을 볼 수 있다. 처음에, 모든 요소들이 filter를 거치고, 필터링을 거친 단어들이 length를 지나, 마지막 두 줄의 출력이 나온다.

 

리스트가 어떻게 처리되는지는 다음과 같다.

https://kotlinlang.org/docs/sequences.html#sequence

Sequence

시퀀스로 똑같이 작성할 수 있다.

fun main() {
    val words = "The quick brown fox jumps over the lazy dog".split(" ")
    //convert the List to a Sequence
    val wordsSequence = words.asSequence()

    val lengthsSequence = wordsSequence.filter { println("filter: $it"); it.length > 3 }
        .map { println("length: ${it.length}"); it.length }
        .take(4)

    println("Lengths of first 4 words longer than 3 chars")
    // terminal operation: obtaining the result as a List
    println(lengthsSequence.toList())
}

결과

Lengths of first 4 words longer than 3 chars
filter: The
filter: quick
length: 5
filter: brown
length: 5
filter: fox
filter: jumps
length: 5
filter: over
length: 4
[5, 5, 5, 4]

이 코드의 아웃풋은 결과 리스트가 만들어질 때 filter()와 map() 함수가 호출되는 것을 보여준다. 그래서 "Length of..." 문장을 제일 먼저 볼 수 있는 것이고, 시퀀스 처리가 그 후에 진행된다. 필터링을 통과한 요소들에 대해서는, 다음 요소를 필터링하기 전에 map이 실행한다. 결과 크기가 4에 도달할 때, 처리 과정은 멈추는데, take(4)가 반환할 수 있는 가능한 가장 큰 사이즈이기 때문이다.

시퀀스 처리 과정은 다음과 같이 된다.

https://kotlinlang.org/docs/sequences.html#sequence

이 예제에서, 시퀀스 처리는 리스트로 같은 작업을 23 단계로 처리하는 것 대신 18단계를 가진다.