Розробка

Мої улюблені приклади функціонального програмування в мові 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 мс. Це пояснює, чому в деяких випадках ми можемо використовувати функцію, яка трохи менше оптимізована, але зате добре читається і проста.

Related Articles

Залишити відповідь

Ваша e-mail адреса не оприлюднюватиметься. Обов’язкові поля позначені *

Close