Um dos grandes recursos do Kotlin é que ele suporta programação funcional. Vamos dar uma olhada e discutir algumas funções simples, mas expressivas, escritas em Kotlin.
Trabalhar com coleções
O Kotlin suporta trabalho conveniente com coleções. Existem muitos recursos diferentes. Suponha que criemos algum sistema para uma universidade. Precisamos encontrar os melhores alunos que merecem uma bolsa de estudos. Temos o seguinte modelo de Student :
class Student( val name: String, val surname: String, val passing: Boolean, val averageGrade: Double )
Agora podemos chamar a seguinte função para obter uma lista dos dez melhores alunos que atendem a todos os critérios:
students.filter { it.passing && it.averageGrade > 4.0 } // 1 .sortedBy { it.averageGrade } // 2 .take(10) // 3 .sortedWith(compareBy({ it.surname }, { it.name })) // 4
- Deixamos apenas os alunos que passaram no exame, cuja pontuação média é superior a 4,0.
- Classifique-os pela pontuação média.
- Deixamos os dez primeiros alunos.
- Classifique-os em ordem alfabética. O comparador primeiro compara os sobrenomes e, se forem iguais, compara os nomes.
E se, em vez de ordem alfabética, precisarmos manter a ordem original dos alunos? Podemos fazer isso usando índices:
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
- Vincule o índice de iteração atual a cada elemento.
- Classifique pela pontuação média e deixe os dez primeiros alunos.
- Classifique novamente, mas agora por índice.
- Excluímos índices e deixamos apenas alunos.
Este exemplo demonstra como é simples e intuitivo o trabalho com coleções no Kotlin.
Se você estudou álgebra em uma universidade, pode se lembrar do que é um superconjunto. Para qualquer conjunto, seu superconjunto é o conjunto de todos os seus subconjuntos, incluindo o próprio conjunto original e o conjunto vazio. Por exemplo, se tivermos o seguinte conjunto:
{1,2,3}
Esse é o seu superconjunto:
{{}, {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3}}
Na álgebra, essa função é muito útil. Como a implementamos?
Se você quiser se desafiar, pare de ler agora e tente resolver esse problema sozinho.
Vamos começar nossa análise com uma simples observação. Se pegarmos algum elemento do conjunto (por exemplo, 1), o superconjunto terá um número igual de conjuntos com esse elemento ({1}, {1,2}, {1,3}, {1,2,3}) e sem ele ({}, {2}, {3}, {2,3}).
Observe que o segundo conjunto é um superconjunto ({2,3}) e o primeiro é um superconjunto ({2,3}) com o nosso elemento adicionado (1) a cada conjunto. Assim, podemos calcular o superconjunto pegando o primeiro elemento, calculando o superconjunto para todos os outros e retornando a soma do resultado e do resultado com a adição do primeiro elemento a cada conjunto:
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 }
Mas esse método não funcionará. O problema é um conjunto vazio: first lançará um erro quando o conjunto estiver vazio. Aqui, a definição de um superconjunto vem para o resgate - o superconjunto de um conjunto vazio é um conjunto vazio: powerset ({}) = {{}}. Aqui está a aparência do algoritmo corrigido:
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() } }
Vamos ver como isso funciona. Suponha que precisamos calcular o conjunto de poderes ({1,2,3}). O algoritmo agirá da seguinte maneira:
powerset ({1,2,3}) = powerset ({2,3}) + powerset ({2,3}). map {it + 1}
conjunto de poderes ({2,3}) = conjunto de poderes ({3}) + conjunto de poderes ({3}). map {it + 2}
powerset ({3}) = conjunto de poderes ({}) + conjunto de poderes ({}). 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}}
Mas podemos melhorar ainda mais nossa função. Vamos usar a função let para tornar a notação mais curta e mais compacta:
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() }
Também podemos definir essa função como uma função de extensão para Collection , para que possamos usá-la como se fosse o setOf(1,2,3).powerset() Set ( setOf(1,2,3).powerset() vez 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() }
Também podemos reduzir os efeitos negativos da recursão criada. Na implementação acima, o estado do superconjunto cresce a cada iteração (com cada chamada recursiva), porque o estado da iteração anterior deve ser armazenado na memória.
Em vez disso, poderíamos usar um loop regular ou tailrec função tailrec . Usaremos a segunda opção para manter a legibilidade da função. O modificador tailrec permite apenas uma chamada recursiva na última linha de função executada. Veja como podemos mudar nossa função para usá-la com mais eficiência:
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() })
Essa implementação faz parte da biblioteca KotlinDiscreteMathToolkit , que define muitas outras funções usadas em matemática discreta.
Hora do exemplo mais interessante. Você verá como um problema complexo pode ser simplificado e tornado legível usando o estilo e as ferramentas de programação funcional.
Implementamos um algoritmo de classificação rápida. O algoritmo é simples: selecionamos algum elemento (pivô ( barra russa)) e distribuímos todos os outros elementos em duas listas: uma lista com elementos maiores que a barra e menor. Em seguida, classificamos recursivamente esses subarrays. Finalmente, combinamos uma lista classificada de elementos menores, uma barra e uma lista classificada de elementos maiores. Para simplificar, considere o primeiro elemento como uma barra. Aqui está a implementação completa:
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() }
Parece lindo, certo? Essa é a beleza da programação funcional.
O primeiro problema com essa função é o tempo de execução. Ela é completamente não otimizada. Mas é curto e fácil de ler.
Se você precisar de uma função otimizada, poderá usá-la na biblioteca Java padrão. É baseado em vários algoritmos, dependendo de certas condições, e é escrito de forma nativa. Isso deve ser muito mais eficiente. Mas quanto exatamente? Vamos comparar essas duas funções. Vamos classificar várias matrizes diferentes com elementos aleatórios e comparar o tempo de execução:
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() }}") }
Aqui estão os resultados que obtivemos:
A classificação Java stdlib de 100000 elementos levou 83
A classificação quickSort de 100000 elementos levou 163
A classificação Java stdlib de 1.000.000 de elementos levou 558
A classificação quickSort de 1.000.000 de elementos levou 859
A classificação stdlib de Java de 10.000.000 de elementos levou 6182
A classificação quickSort de 10.000.000 de elementos levou 12133
Como você pode ver, a função quickSort quase duas vezes mais lenta. Mesmo para grandes listas. Em casos normais, a diferença será tipicamente de 0,1 ms a 0,2 ms. Isso explica por que, em alguns casos, podemos usar uma função um pouco menos otimizada, mas bem legível e simples.