Мои любимые примеры функционального программирования в языке Kotlin

Одной из замечательных особенностей Kotlin является то, что он поддерживает функциональное программирование. Давайте посмотрим и обсудим некоторые простые, но выразительные функции, написанные на языке Kotlin.

Работа с коллекциями

Kotlin поддерживает удобную работу с коллекциями. Есть множество разнообразных функций. Предположим, что мы создаем некоторую систему для университета. Нам нужно найти лучших студентов, которые достойны стипендии. У нас есть следующая модель Student:

class Student(     val name: String,     val surname: String,     val passing: Boolean,     val averageGrade: Double )

Теперь мы можем вызвать следующую функцию, чтобы получить список десяти лучших студентов, которые соответствуют всем критериям:

students.filter { it.passing && it.averageGrade > 4.0 } // 1     .sortedBy { it.averageGrade } // 2     .take(10) // 3     .sortedWith(compareBy({ it.surname }, { it.name })) // 4 

• Оставляем только сдавших экзамен студентов, средний балл которых более 4.0.
• Сортируем их по среднему баллу.
• Оставляем первых десять студентов.
• Сортируем их по алфавиту. Компаратор сначала сравнивает фамилии, и если они равны, то он сравнивает имена.

Что, если вместо порядка по алфавиту нам нужно сохранить изначальный порядок студентов? Мы можем это сделать, используя индексы:

students.filter { it.passing && it.averageGrade > 4.0 }     .withIndex() // 1     .sortedBy { (i, s) -> s.averageGrade } // 2     .take(10)     .sortedBy { (i, s) -> i } // 3     .map { (i, s) -> s } // 4

• Привязываем текущий индекс итерации к каждому элементу.
• Сортируем по среднему баллу и оставляем первые десять студентов.
• Снова сортируем, но теперь по индексу.
• Удаляем индексы и оставляем только студентов.

Этот пример наглядно показывает, как проста и интуитивно понятна работа с коллекциями в Kotlin.

Супермножество (булеан)

Если вы изучали алгебру в университете, вы можете вспомнить, что такое супермножество. Для любого множества его супермножеством является множество всех его подмножеств, включая само оригинальное множество и пустое множество. Например, если у нас есть следующий набор:

{1,2,3}

То его супермножество:

{{}, {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3}}

В алгебре такая функция очень полезна. Как нам её реализовать?

Если вы хотите бросить себе вызов, то остановитесь читать прямо сейчас и попытайтесь решить эту проблему самостоятельно.

Давайте начнем наш анализ с простого наблюдения. Если мы возьмем какой-либо элемент множества (например, 1), то в супермножестве будет равное количество множеств с этим элементом ({1}, {1,2}, {1,3}, {1,2,3}) и без него ({}, {2}, {3}, {2,3}).

Обратите внимание, что второй набор – это супермножество ({2,3}), а первый – это супермножество ({2,3}) с нашим добавленным элементом (1) к каждому множеству. Таким образом, мы можем вычислить супермножество, взяв первый элемент, вычислив супермножество для всех остальных и вернув сумму результата и результата с добавлением первого элемента к каждому множеству:

fun <T> powerset(set: Set<T>): Set<Set<T>> {    val first = set.first()    val powersetOfRest = powerset(set.drop(1))    return powersetOfRest.map { it + first } + powersetOfRest }

Но данный метод работать не будет. Проблема заключается в пустом множестве: first вызовет ошибку, когда множество пустое. Здесь на помощь приходит определение супермножества — супермножеством пустого множества является пустое множество: powerset({}) = {{}}. Вот как выглядит исправленный алгоритм:

fun <T> powerset(set: Set<T>): Set<Set<T>> =     if (set.isEmpty()) setOf(emptySet())     else {        val powersetOfRest = powerset(set.drop(1))        powersetOfRest + powersetOfRest.map { it + set.first() }     }

Давайте посмотрим, как это работает. Предположим, нам нужно вычислить powerset({1,2,3}). Алгоритм будет действовать следующим образом:

powerset({1,2,3}) = powerset({2,3}) + powerset({2,3}).map { it + 1 }

powerset({2,3}) = powerset({3}) + powerset({3}).map { it + 2}

powerset({3}) = powerset({}) + powerset({}).map { it + 3}

powerset({}) = {{}}

powerset({3}) = {{}, {3}}

powerset({2,3}) = {{}, {3}} + {{2}, {2, 3}} = {{}, {2}, {3}, {2, 3}}

powerset({1,2,3}) = {{}, {2}, {3}, {2, 3}} + {{1}, {1, 2}, {1, 3}, {1, 2, 3}} = {{}, {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3}}

Но мы можем улучшить нашу функцию ещё больше. Давайте используем функцию let, чтобы сделать обозначения короче и компактнее:

fun <T> powerset(set: Set<T>): Set<Set<T>> =     if (set.isEmpty()) setOf(emptySet())     else powerset(set.drop(1))            .let { it+ it.map { it + set.first() }

Мы также можем определить эту функцию как функцию-расширения для Collection, чтобы мы могли использовать эту функцию так, как если бы это был метод Set (setOf(1,2,3).powerset() вместо powerset(setOf(1,2,3))):

fun <T> Collection<T>.powerset(): Set<Set<T>> =     if (isEmpty()) setOf(emptySet())     else drop(1)            .powerset()            .let { it+ it.map { it + first() }

Ещё мы можем уменьшить негативные последствия от созданной рекурсии. В приведенной выше реализации состояние супермножества растет с каждой итерацией (с каждым рекурсивным вызовом), потому что состояние предыдущей итерации должно храниться в памяти.

Вместо этого мы могли бы использовать обычный цикл или модификатор функции tailrec. Мы будем использовать второй вариант, чтобы сохранить читабельность функции. Модификатор tailrec допускает только один рекурсивный вызов в последней выполняемой строке функции. Вот как мы можем изменить нашу функцию для более эффективного её использования:

fun <T> Collection<T>.powerset(): Set<Set<T>> =      powerset(this, setOf(emptySet()))  private tailrec fun <T> powerset(left: Collection<T>, acc: Set<Set<T>>): Set<Set<T>> =     if (left.isEmpty()) acc     else powerset(left.drop(1), acc + acc.map { it + left.first() })

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

Быстрая сортировка (quicksort)

Время для самого интересного примера. Вы увидите, как сложную проблему можно упростить и сделать читабельной с использованием стиля и инструментов функционального программирования.

Мы реализуем алгоритм быстрой сортировки. Алгоритм прост: мы выбираем какой-нибудь элемент (pivot (рус. стержень)) и распределяем все остальные элементы в два списка: список с элементами больше, чем стержень, и меньше. Затем мы рекурсивно сортируем эти подмассивы. Наконец, мы соединяем отсортированный список меньших элементов, стержень и отсортированный список более крупных элементов. Для упрощения возьмем первый элемент в качестве стержня. Вот полная реализация:

fun <T : Comparable<T>> List<T>.quickSort(): List<T> =      if(size < 2) this     else {         val pivot = first()         val (smaller, greater) = drop(1).partition { it <= pivot}         smaller.quickSort() + pivot + greater.quickSort()     } // Usage listOf(2,5,1).quickSort() // [1,2,5]

Выглядит шикарно, правда? Это и есть прелесть функционального программирования.

Первой проблемой такой функции является время ее выполнения. Она совершенно неоптимизированная. Зато она короткая и легко читаемая.

Если вам нужна оптимизированная функция, вы можете использовать функцию из стандартной библиотеки Java. Она основана на различных алгоритмах, зависящих от некоторых условий, и написана нативно. Это должно быть намного более эффективным. Но насколько именно? Давайте сравним эти две функции. Давайте отсортируем несколько разных массивов со случайными элементами и сравним время выполнения:

val r = Random() listOf(100_000, 1_000_000, 10_000_000)     .asSequence()     .map { (1..it).map { r.nextInt(1000000000) } }     .forEach { list: List<Int> ->         println("Java stdlib sorting of ${list.size} elements took ${measureTimeMillis { list.sorted() }}")         println("quickSort sorting of ${list.size} elements took ${measureTimeMillis { list.quickSort() }}")     }

Вот такие результаты мы получили:

Java stdlib sorting of 100000 elements took 83
quickSort sorting of 100000 elements took 163
Java stdlib sorting of 1000000 elements took 558
quickSort sorting of 1000000 elements took 859
Java stdlib sorting of 10000000 elements took 6182
quickSort sorting of 10000000 elements took 12133

Как видно, функция quickSort практически в 2 раза медленнее. Даже для огромных списков. В обычных случаях разница будет, как правило, составлять от 0,1мс до 0,2мс. Это объясняет, почему в некоторых случаях мы можем использовать функцию, которая немного менее оптимизирована, но зато хорошо читаема и проста.