de Marcin Moskala

Unul dintre lucrurile minunate despre Kotlin este că acceptă programarea funcțională. Să vedem și să discutăm câteva funcții simple, dar expresive, scrise în Kotlin.

Exemplele mele preferate de programare functionala din Kotlin

Prelucrarea colecției

Kotlin are unele dintre cele mai bune suport pentru procesarea colecției. Este expresiv și acceptă o mulțime de funcții. Pentru a vedea un exemplu, să spunem că realizăm un sistem pentru o universitate. Trebuie să găsim cei mai buni studenți care merită o bursă. Avem urmăritori Student model:

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

Acum putem face următoarea procesare pentru a obține o listă cu cei mai buni 10 studenți care corespund tuturor criteriilor:

students.filter { it.passing && it.averageGrade > 4.0 } // 1
    .sortedBy { it.averageGrade } // 2
    .take(10) // 3
    .sortedWith(compareBy({ it.surname }, { it.name })) // 4
  1. Primim doar studenți care promovează și cu o medie de punctaj mai mare de 4,0.
  2. Sortăm după nota medie.
  3. Luăm primii 10 elevi.
  4. Sortăm elevii alfanumeric. Comparatorul compară mai întâi numele de familie și, dacă este egal, atunci compară numele.

Ce se întâmplă dacă, în loc de ordine alfanumerică, trebuie să menținem studenții în aceeași ordine ca înainte? Ce putem face este să păstrăm ordinea folosind indexuri:

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
  1. Adăugăm indexul curent la fiecare element.
  2. Avem nevoie să destructură valoarea și indexul înainte de utilizare.
  3. Sortăm după index.
  4. Eliminăm indexul și păstrăm doar studenții.

Aceasta arată cât de simplă și intuitivă este prelucrarea colecției în Kotlin.

ad-banner
Exemplele mele preferate de programare functionala din Kotlin

Powerset

Dacă ați avut algebră la Universitatea dvs., atunci vă puteți aminti ce este un set de puteri. Pentru orice set, setul său de putere este setul tuturor subseturilor sale, inclusiv acest set și setul gol. De exemplu, dacă avem următorul set:

{1,2,3}

Setul său de putere este următorul:

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

O astfel de funcție este foarte utilă în algebră. Cum îl putem implementa?

Dacă doriți să vă provocați, opriți-vă chiar acum și încercați să o rezolvați mai întâi.

Să începem analiza noastră de la simpla observație. Dacă luăm orice element al mulțimii (cum ar fi 1), atunci setul de puteri va include un număr egal de mulțimi cu aceste elemente ({1}, {1,2}, {1,3}, {1,2,3}), și fără acestea ({}, {2}, {3}, {2,3}).

Rețineți că al doilea este un powerset({2,3}), iar primul este un powerset({2,3}) cu 1 adăugat la fiecare set. Deci putem calcula setul de puteri luând primul element, calculând setul de puteri pentru toate celelalte și returnând suma rezultatului și a rezultatului cu primul element adăugat la fiecare set:

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
}

Declarația de mai sus nu va funcționa corect. Problema este cu setul gol: first va arunca o eroare când setul este gol. Aici, definiția vine cu o soluție: powerset ({}) = {{}}. Când îl remediem, vom avea algoritmul pregătit:

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() }
    }
1611540907 439 Exemplele mele preferate de programare functionala din Kotlin

Să vedem cum funcționează. Să presupunem că trebuie să calculăm powerset({1,2,3}). Algoritmul îl va număra astfel:

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}}

Funcția de mai sus poate fi îmbunătățită. Putem folosi let funcție pentru a face notația mai scurtă și mai compactă:

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() }

Putem defini această funcție și ca o funcție de extensie a Collection deci putem folosi această funcție ca și cum ar fi metoda Set (setOf(1,2,3).powerset() in loc de 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() }

O mare îmbunătățire este de a face powerset coada recursivă. În implementarea de mai sus, starea de powerset crește cu fiecare iterație (apel recurent), deoarece starea iterației anterioare trebuie păstrată în memorie.

În schimb, am putea folosi o buclă imperativă sau tailrec modificator. Vom folosi a doua opțiune pentru a menține lizibilitatea funcției. tailrec modificatorul permite doar un singur apel recursiv în ultima instrucțiune. Acesta este modul în care ne putem schimba funcția pentru a o utiliza eficient:

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() })

Implementarea de mai sus face parte din KotlinDiscreteMathToolkit bibliotecă, care definește o mulțime de alte funcții utilizate în matematică discretă.

Sortare rapida

E timpul pentru exemplul meu preferat. Vom vedea cum o problemă dificilă poate fi simplificată și ușor de citit folosind un stil funcțional de programare și instrumente.

Vom implementa Sortare rapida algoritm. Algoritmul este simplu: alegem un element (pivot) și distribuim toate celelalte elemente în listă cu elemente mai mari și mai mici decât pivotul. Apoi sortăm recursiv aceste sub-tablouri. În cele din urmă, adăugăm lista sortată a elementelor mai mici, pivotul și lista sortată a elementelor mai mari. Pentru simplificare, vom lua primul element ca pivot. Iată implementarea completă:

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]

Arată grozav, nu-i așa? Aceasta este frumusețea programării funcționale.

1611540907 487 Exemplele mele preferate de programare functionala din Kotlin

Prima preocupare a unei astfel de funcții este timpul de execuție al acesteia. Nu este deloc optimizat pentru performanță. În schimb, este scurt și foarte ușor de citit.

Dacă aveți nevoie de o funcție extrem de optimizată, puteți utiliza una din biblioteca standard Java. Se bazează pe algoritmi diferiți în funcție de anumite condiții și are implementări reale scrise naiv. Ar trebui să fie mult mai eficient. Dar cât de exact? Să comparăm aceste două funcții. Să sortăm câteva matrice diferite cu elemente aleatorii și să comparăm timpii de execuție. Iată codul pe care l-am folosit în acest scop:

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() }}")
    }

Pe mașina mea am obținut următorul rezultat:

Sortarea Java stdlib a 100000 de elemente a durat 83
sortarea quickSort a 100000 de elemente a durat 163
Sortarea Java stdlib a 1000000 de elemente a durat 558
sortarea quickSort a 1000000 de elemente a durat 859
Sortarea Java stdlib a 10000000 de elemente a durat 6182
sortarea quickSort a 10000000 de elemente a durat 12133`

După cum putem vedea, quickSort funcția este în general de 2 ori mai lentă. Chiar și pentru liste uriașe. Are aceeași scalabilitate. În cazuri normale, diferența va fi în general între 0,1 ms față de 0,2 ms. Rețineți că este mult mai simplu și mai ușor de citit. Acest lucru explică de ce, în unele cazuri, putem folosi o funcție puțin mai puțin optimizată, dar lizibilă și simplă.

Dacă sunteți interesat de Kotlin, verificați Academia Kotlin. Este o publicație excelentă și o comunitate dedicată pentru Kotlin.

Public, de asemenea, resurse excelente pe pagina mea Stare de nervozitate. Pentru a mă menționa acolo folosiți @marcinmoskala. Dacă puteți folosi ajutorul meu, nu uitați asta Sunt deschis pentru consultări.