Последовательности (Sequences)

Стандартная библиотека Kotlin помимо коллекций содержит еще один тип контейнера - последовательности (Sequence<T>). Последовательности предлагают те же функции, что и Iterable, но реализуют другой подход к многоэтапной обработке коллекции.

Если обработка Iterable состоит из нескольких шагов, то они выполняются немедленно: при завершении обработки каждый шаг возвращает свой результат - промежуточную коллекцию. Следующий шаг выполняется для этой промежуточной коллекции. В свою очередь, многоступенчатая обработка последовательностей по возможности выполняется "лениво": фактически вычисления происходят только тогда, когда запрашивается результат выполнения всех шагов.

Порядок выполнения операций также различается: Sequence выполняет все шаги один за другим для каждого отдельного элемента. Тогда как Iterable завершает каждый шаг для всей коллекции, а затем переходит к следующему шагу.

Таким образом, последовательности позволяют избежать создания промежуточных результатов для каждого шага, тем самым повышая производительность всей цепочки вызовов. Однако "ленивый" характер последовательностей добавляет некоторые накладные расходы, которые могут быть значительными при обработке небольших коллекций или при выполнении более простых вычислений. Следовательно, вы должны рассмотреть, а затем самостоятельно решить, что вам подходит больше - Sequence или Iterable.

Создание последовательностей

С помощью элементов

Чтобы создать последовательность, вызовите функцию sequenceOf() и передайте ей элементы в качестве аргументов.

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

С помощью `Iterable`

Если у вас уже есть объект Iterable (например, List или Set), то вы можете создать из него последовательность, вызвав функцию asSequence().

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

С помощью функции

Ещё один способ создать последовательность - использовать функцию, которая вычисляет элементы последовательности. Для этого вызовите generateSequence() и в качестве аргумента передайте ей эту функцию. При желании вы можете указать первый элемент как явное значение или результат вызова функции. Генерация последовательности останавливается, когда предоставленная функция возвращает null. Последовательность в приведённом ниже примере бесконечна.

fun main() {
    val oddNumbers = generateSequence(1) { it + 2 } // `it` - это предыдущее значение
    println(oddNumbers.take(5).toList()) // [1, 3, 5, 7, 9]
    //println(oddNumbers.count())     // ошибка: последовательность бесконечна
}

Для создания конечной последовательности передайте в generateSequence() такую функцию, которая после последнего нужного вам элемента вернёт null.

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

С помощью чанков (chunks)

Наконец, есть функция sequence(), которая позволяет создавать элементы последовательности один за другим или кусками (chunks) произвольного размера. Эта функция принимает лямбда-выражение, содержащее вызовы функций yield() и yieldAll(). Они возвращают элемент потребителю последовательности и приостанавливают выполнение sequence() до тех пор, пока потребитель не запросит следующий элемент. Функция yield() принимает в качестве аргумента один элемент; yieldAll() может принимать объект Iterable, Iterator или другую Sequence. Аргумент Sequence, переданный в 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]
}

Операции с последовательностями

Операции с последовательностями можно разделить на следующие группы:

Stateless (без сохранения состояния) - операции, которым не требуется создавать промежуточное состояние. Они обрабатывают каждый элемент независимо, например, функции map() и filter(). К этой же группе относятся операции, которым требуется создавать небольшое константное количество промежуточных состояний, например, take() или drop().
Stateful (с отслеживанием состояния) - данным операциям требуется создавать большое количество промежуточных состояний, которое, как правило, пропорционально количеству элементов в последовательности.

Если операция возвращает другую последовательность, которая создаётся "лениво", то такая операция называется промежуточной (intermediate). В противном случае эта операция будет терминальной (terminal). Примеры терминальных операций: toList() или sum(). Элементы последовательности можно получить только с помощью терминальных операций.

Последовательности можно итерировать несколько раз; однако некоторые реализации последовательностей могут ограничивать итерацию до одного раза. Это специально упоминается в их документации.

Примеры работы с последовательностью

Давайте на примере разберём разницу между Iterable и Sequence.

Iterable

Предположим, у вас есть список слов. Отфильтруем слова длиной более трёх символов и выведем на печать длину первых четырёх таких слов.

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) // [5, 5, 5, 4]
}

Попробуйте запустить этот код и увидите, что функции filter() и map() выполняются в том же порядке, в котором они появляются в коде. Сначала все слова фильтруются с помощью filter(), а затем для оставшихся слов вычисляется их длина с помощью map().

Визуально это выглядит следующим образом:

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()) // [5, 5, 5, 4]
}

Если вы запустите этот код, то увидите, что функции filter() и map() вызываются в момент обращения к списку. Сначала в лог будет выведена строка “Lengths of..” и только после неё начинается вычисление результата. Обратите внимание и на порядок вызова функций. Если элемент соответствует условию фильтра, то функция map(), не дожидаясь окончания фильтрации, вычисляет длину слова. Когда размер последовательности достигает 4, вычисление останавливается, потому что это максимально возможный размер, который может вернуть take(4).