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

Original author: Marcin Moskala
  • Translation

Одной из замечательных особенностей 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.


Работа с коллекциями в 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мс. Это объясняет, почему в некоторых случаях мы можем использовать функцию, которая немного менее оптимизирована, но зато хорошо читаема и проста.

AdBlock has stolen the banner, but banners are not teeth — they will be back

More
Ads

Comments 17

    +7
    Не холивара ради, просто увидел первую картинку в посте и вспомнилась чудесная фраза:
    Объективно, объекты функциональнее функций
      +1

      Ясно ж почему медленнее сортировка. В Котлине по умолчанию все операции над коллекциями активные (выполняются моментально и возвращают копию), а не ленивые: хочешь ленивых вычислений, отметь их через asSequence. Поэтому все наши операции по разделению списка идут через выделения памяти и копирования, а вот Java-версия наверняка написана in-place, тем более там не QuickSort.

        0
        Ребята! Ну TimSort же!
          –5
          И что это делает в хабе java?
            0
            привыкайте, в хабе ruby тоже постоянно проскакивает фреймворк phoenix, который к руби не относится (что раздражает).
            Почему вас заминусили мне непонятно.
            +1
            мы выбираем какой-нибудь элемент (pivot (рус. стержень))

            en.wiktionary.org/wiki/pivot
            Pivot — ось, вокруг которой что-то крутится. Также — нечто очень важное (of pivotal importance).
              +1
              Обычно в данном контексте по-русски это (pivot) именуется опорным, или ведущим, элементом.
              +1
              Допустим, что (внезапно в 100% случаях) университет хранит данные о своих студентах в некой базе данных. И гораздо проще взять из базы напрямую уже отсортированный и отфильтрованный список через SQL, а не вытаскивать целиком всю базу каждый раз и фильтровать ее Котлином.

              Это проще, быстрее и правильней, но тут извините не пахнет смузи и фалафелем.
                +1
                Можно не вытаскивать целиком, но фильтровать котлином github.com/x2bool/kuery =)
                  0
                  jooq, querydsl, hibernate, mybatis, spring data…
                +2
                После заставки читать статью желание пропало ибо функционально ориентированное программирование появилось раньше ООП.
                  0

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

                  0
                  В правильном™ ФП powerset делается монадами:
                  Prelude Control.Monad> powerset = filterM $ const [True, False]
                  Prelude Control.Monad> powerset [0..2]                         
                  [[0,1,2],[0,1],[0,2],[0],[1,2],[1],[2],[]]
                  
                    0

                    Измерять производительность такой реализации quick sort на случайных данных не совсем честно — она себя хорошо ведёт как раз в таких случаях. Но при этом может работать очень плохо и вообще выбрасывать StackOverflowException в других случаях. У Timsort такой особенности нет.

                    • UFO just landed and posted this here
                        0

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

                          0
                          И ООП в этом мало. Кажется, раньше это называлось процедурным программирванием.

                        Only users with full accounts can post comments. Log in, please.