Haskell é uma linguagem totalmente funcional e extremamente concisa. Quem já tentou escrever código em Haskell percebe como é conciso e elegante o que escreve a mesma coisa em uma linguagem imperativa. Conseguir o mesmo em Java, na minha opinião, é impossível, mas o Kotlin permite que você se mova nessa direção e experimente um estilo totalmente funcional. Podemos derivar todas as funções complexas que precisamos desde a base das 3 funções mais famosas: mapear, filtrar, reduzir. Além disso, criei um
repositório que você pode estudar e ver os testes.
Antes de começar, gostaria de chamar a atenção para o fato de que não vale a pena implementar uma abordagem funcional dessa maneira, porque o código será extremamente lento e não deve ser usado em aplicativos de produção. Certamente existem opções para aprimorá-lo, mas o objetivo do artigo não é revelar essas opções, mas considerar uma abordagem alternativa para escrever código. De qualquer forma, o entendimento dessa abordagem o ajudará com estruturas de dados recursivas, e você poderá apreciar a beleza e a elegância de como o código é lido e o quão mais fácil é entender.
Funções básicas
As listas desempenham um papel muito importante na linguagem e muitas funções úteis são implementadas para elas. Vejamos alguns deles e como eles podem ser implementados no Kotlin.
head (x:_) = x head [] = badHead
Se houver elementos na lista, retornaremos o primeiro, caso contrário, retornaremos um erro.
Não temos a oportunidade de escrever esse código, mas, em geral, se você olhar de perto, é muito parecido com o modelo. Também usaremos a função de extensão para poder usar posteriormente esse método em listas e ter uma maneira um pouco mais concisa de obter o valor, sem os colchetes no final, como uma chamada de método.
val <T> List<T>.head: T get() = when (this.isEmpty()) { true -> throw NoSuchElementException("List is empty.") false -> this[0] }
Para usar convenientemente a recursão, também gostaríamos de dividir a lista no primeiro elemento + em todos os outros. Vamos tentar implementar a função tail para isso.
Aqui está o que parece no haskell:
tail (_:xs) = xs tail [] = errorEmptyList "tail"
Infelizmente, o Kotlin não fornece um nível de correspondência de padrões que os desenvolvedores possam descrever no mesmo estilo; portanto, aqui temos que escrever um pouco quando.
val <T> List<T>.tail: List<T> get() = drop(1)
É um pouco desonesto usar uma função da biblioteca de idiomas, mas, por outro lado, teríamos que escrever código para esse método, portanto, seria melhor usar métodos já em funcionamento.
Agora podemos dividir a lista no primeiro elemento + no restante da lista. Também precisamos da função de concatenar a lista e um elemento, que será usado ativamente posteriormente para conversão e outras operações na lista.
operator fun <T> List<T>.plus(x: T): List<T> = ArrayList(this).also { it.add(x) }
Agora, podemos adicionar uma lista ao elemento no final, e nossa implementação da função map fica funcionando e pronta para uso. Infelizmente, novamente, não há como adicionar um objeto à lista de maneira mais conveniente; portanto, usamos o método
add .
No momento, temos quase tudo o que precisamos. A única coisa que precisamos agora é ser capaz de descrever a condição de contorno para sair da recursão. Para fazer isso, usaremos o método
isEmpty () padrão. Vamos parar e ver o que temos no momento:
- isEmpty () - existem elementos na lista
- head - o primeiro elemento da lista
- tail - uma lista sem o primeiro elemento
- list + elemento - podemos concatenar a lista com um objeto
Na verdade, é tudo o que precisamos para obter todos os métodos que precisamos.
Para meu gosto, seria mais conveniente usar a comparação do comprimento da lista nas declarações
when . O Kotlin já nos fornece o
tamanho para obter o tamanho dessa lista. No entanto, suponha que queremos implementá-lo nós mesmos. Com nossa funcionalidade, será bastante simples:
val <T> List<T>.size: Int get() = when (this.isEmpty()) { true -> 0 false -> 1 + this.tail.size }
Aplicação de funções básicas
Considere o exemplo mais comum. Suponha que tenhamos uma lista de números inteiros e que queremos resumir, esquecendo a existência de ciclos. Tudo o que temos são os métodos que derivamos acima e recursão. Para fazer isso, usaremos a mesma abordagem ao calcular o tamanho da lista:
fun sum(xs: List<Int>): Int = when (xs.size) { 0 -> 0 else -> xs.head + sum(xs.tail) }
A ideia é muito simples: se não houver elementos na lista, a soma será 0; caso contrário, é a soma do primeiro elemento e uma chamada recursiva da soma da cauda.
Apesar de não nos importarmos com velocidade e otimizações neste código, não podemos deixar de lembrar os recursos do idioma para usar a recursão de cauda. Recursão de cauda é um caso especial de recursão em que uma chamada recursiva é a última operação antes de retornar de uma função. Esse tipo de recursão é digno de nota porque é garantido para permitir que você reconstrua o código para iteração. Como você sabe, o principal problema da recursão é que, durante a execução da função, é necessário armazenar a pilha de chamadas para que, quando a condição de limite for atingida, você possa voltar e recalcular o resultado final.
Pode parecer que a função da quantidade que descrevemos seja exatamente assim, porque a última chamada é
soma (xs.tail) . No entanto, isso não é verdade. Se você descrever o código de maneira um pouco diferente, ficará óbvio:
fun sum(xs: List<Int>): Int = when (xs.size) { 0 -> 0 else -> { val head = xs.head val tailSum = sum(xs.tail) head + tailSum } }
Agora vemos que, de fato, a última chamada é a soma do primeiro elemento e a parte restante da cauda.
A boa notícia é que, se você adicionar o modificador
tailrec a uma função, o IDE informará que a função não é. No entanto, corrigir isso é bem direto. Um truque comum que corrige uma função é usar uma variável auxiliar para armazenar os resultados. É assim:
tailrec fun sum(xs: List<Int>, acum: Int): Int = when (xs.size) { 0 -> acum else -> sum(xs.tail, xs.head + acum) }
Para calcular a soma dos elementos, basta passar 0. como o segundo parâmetro não é necessário.
fun sum(xs: List<Int>):Int { tailrec fun sumInner(xs: List<Int>, acum: Int): Int = when (xs.size) { 0 -> acum else -> sumInner(xs.tail, xs.head + acum) } return sumInner(xs, 0) }
Tendo esse conhecimento, você pode ver que a função de tamanho que implementamos acima não satisfaz as condições necessárias para a recursão da cauda.
Agora estamos prontos para implementar o mapa, filtrar e reduzir usando o Kotlin. Mais tarde veremos que bastava perceber que apenas o último, e o restante, de um modo geral, são derivados dele. Mas as primeiras coisas primeiro.
Funções principais
MAPA
Uma implementação iterativa dessa função envolve movimento seqüencial pela lista, usando a função de conversão e adicionando todos os elementos recebidos à nova coleção. Usaremos chamadas recursivas em que a condição de contorno é uma lista vazia. A implementação ficará assim:
fun <T, R> List<T>.map(f: (T) -> R): List<R> = when (this.size) { 0 -> listOf() else -> f(head) + tail.map(f) }
Se não houver elementos na lista original, retornaremos uma lista vazia; caso contrário, aplicaremos a transformação ao primeiro elemento e adicionaremos uma chamada recursiva ao final pelo restante da lista.
No entanto, ainda não temos uma função para concatenar um elemento e uma lista. Mas já podemos perceber isso. Para começar, derivamos um caso mais geral de concatenação de um par de listas e, depois disso, o usamos para adicionar outra lista ao elemento.
operator fun <T> List<T>.plus(xs: List<T>): List<T> = when (xs.size) { 0 -> ArrayList(this) else -> (this + xs.head) + xs.tail } operator fun <T> T.plus(xs: List<T>): List<T> = listOf(this) + xs
Filtro
A implementação será muito semelhante ao mapa. A única diferença é que você precisa entender se precisa adicionar o elemento atual ao resultado. Para fazer isso, chamaremos o lambda que recebemos como parâmetro. A implementação terá a seguinte aparência:
fun <T> List<T>.filter(f: (T) -> Boolean): List<T> = when (this.size) { 0 -> listOf() else -> if (f(head)) head + tail.filter(f) else tail.filter(f) }
Se o elemento atual atender à condição do filtro, adicione-o recursivamente ao final da lista, caso contrário, continuaremos trabalhando apenas com o final da lista.
REDUZIR
A mais difícil de entender e, ao mesmo tempo, a função mais poderosa (no mundo funcional, é conhecida como
fold ). Na maioria das vezes, é usado para recolher uma lista para um único item. Você tem um certo valor inicial
s0 e também há uma lista de elementos
a [] e uma função
f , que retorna um novo para o valor inicial e o próximo elemento da lista.
f (s0, a [0]) = s1 . E assim, passamos sequencialmente por toda a lista de elementos, obtendo algum tipo de valor único na saída. Um exemplo bastante comum é a soma dos elementos da matriz. Nesse caso, o valor inicial é 0 e a função retorna a soma de dois elementos:
f (s, a [i]) = s + a [i] . Considere como podemos implementar recursivamente essa função.
fun <T, R> reduce(s: T, xs: List<R>, f: (T, R) -> T): T = when (xs.size) { 0 -> s else -> reduce(f(s, xs.head), xs.tail, f) }
Em princípio, a implementação é exatamente a mesma que analisamos acima. Se não houver elementos na lista, retornamos o valor atual, caso contrário, calculamos o novo primeiro elemento e, novamente, chamamos a função de redução para ele e o final da lista.
Observe que também podemos criar modificações nessa função. Por exemplo, não passe o valor inicial, mas use o primeiro elemento da lista para isso. Para entender que reduzir não termina aí, imagine que usamos uma lista diferente como valor inicial. Nesse caso, cada vez na iteração, armazenaremos não um valor, mas uma lista, graças à qual nossas capacidades aumentam bastante. Por exemplo, vamos tentar aplicar a função de redução de forma que a saída seja a lista original:
fun <T> reduceSame(xs: List<T>) = reduce(listOf<T>(), xs) { ys, s -> ys + s }
Agora, eu acho, você acha que poderíamos usar o filtro de redução, para uma implementação alternativa do mapa. Desde que aprendemos a retornar exatamente a mesma lista com redução, precisamos fazer muito poucas alterações para poder converter cada elemento. Para filtro, tudo é muito parecido.
fun <T, R> List<T>.map2(f: (T) -> R): List<R> = reduce(mutableListOf(), this) { xs, s -> (xs + f(s)).toMutableList() } fun <T> List<T>.filter2(f: (T) -> Boolean): List<T> = reduce(mutableListOf(), this) { ys, s -> if (f(s)) return@reduce (ys + s).toMutableList() else ys }
Além disso, eles frequentemente esquecem que também podemos usar a redução não desde o início da lista, mas do final. Claro, podemos apenas expandir a lista e, depois disso, reduzir, mas isso não é interessante. Vamos tentar escrever e entender como reduzir funciona para recolher a lista na ordem inversa.
fun <T, R> reduceRight(s: T, xs: List<R>, f: (T, R) -> T): T = when (xs.size) { 0 -> s else -> f(reduceRight(s, xs.tail, f), xs.head) }
Se a lista não estiver vazia, aplicamos a função f ao resultado de dobrar a cauda da lista e o cabeçalho da lista. Assim, o primeiro elemento será processado por último; penúltimo - 2º e assim por diante. Para esta opção, você também pode adicionar modificações que usarão o último elemento da lista como um valor inicial, etc.
Quase sempre, ao trabalhar com listas, você pode usar alguma combinação dessas 3 funções para obter o resultado em que está interessado.
Vamos também implementar a função
zip , que nos permitirá combinar 2 listas.
Na entrada, temos 2 listas. E queremos retornar uma lista de pares cujo comprimento é igual ao mínimo das listas originais.
Como sempre, você precisa pensar em sair da recursão e escrever uma função.
fun <T, R> zip(xs: List<T>, ys: List<R>): List<Pair<T, R>> { return when (xs.isEmpty() || ys.isEmpty()) { true -> listOf() false -> Pair(xs.head, ys.head) + zip(xs.tail, ys.tail) } }
Você pode adicionar suas próprias modificações, o que permitirá, em vez de retornar um par de elementos, aplicar uma determinada função a dois elementos. No Haskell, essa função é chamada
zipWith . E é implementado com a funcionalidade que conseguimos escrever de maneira muito simples:
fun <T, R, C> zipWith(xs: List<T>, ys: List<R>, f: (T, R) -> C): List<C> = zip(xs, ys).map { f(it.first, it.second) }
Muitas vezes, ao usar a abordagem funcional, surgem problemas quando você precisa executar manipulações baseadas não em objetos em listas, mas com base em índices. Por exemplo, precisamos somar todos os elementos pares de uma lista. Você pode tentar fazer isso com reduzir, mantendo o valor atual como Pair <Int, Boolean> e adicionando o valor se flag == true e aceitar a negação do flag toda vez na próxima etapa. No entanto, isso não parece muito bonito, e o leitor terá que descobrir o que você deseja expressar com este código. Kotlin tem seqüências infinitas e são ótimas para resolver esse problema. Se analisarmos o que queremos fazer, acontece que queremos filtrar todos os elementos com índices ímpares e somar os demais. E para obter índices, basta chamar
zip para a lista e
sequência [0,1,2 ..]
fun sumWithEvenIndexes(xs: List<Int>) = zip(xs, generateSequence(0) { it + 1 }.take(xs.size).toList()) .filter { it.second % 2 == 0 } .map { it.first } .sum()
Na biblioteca padrão Kotlin, você pode encontrar a função zip para o par de seqüências.
Agora, vejamos uma tarefa simples que me inspirou a escrever este guia e como sua implementação se parece em uma linguagem imperativa no Kotlin e no final em Haskell.
É necessário calcular a quantidade máxima entre pares de números adjacentes em uma matriz de números inteiros. O comprimento da matriz é maior que 1 e você não precisa se preocupar em transbordar ao somar elementos.
Abordagem imperativa do Java:
public Integer maxSum(List<Integer> array) { Integer max = array.get(0) + array.get(1); for (int i = 2; i < array.size(); i++) if (array.get(i) + array.get(i-1) > max) max = array.get(i) + array.get(i-1); return max; }
Uma abordagem funcional no Kotlin usando funções escritas (proponho implementar a função max como um treinamento):
fun maxSum(xs: List<Int>) = zipWith(xs, xs.tail, {a, b -> a + b}).max()
Implementação Haskell:
maxSum xs = maximum $ zipWith (+) xs (tail xs)
Como podemos ver, o que implementamos no Kotlin (a propósito, poderíamos usar o reduzir para resolver esse problema) é muito semelhante ao que pode ser escrito em Haskell.
Conclusão
Sem dúvida, isso não deve ser usado no desenvolvimento, porque tudo foi implementado de maneira não otimizada apenas para demonstrar uma abordagem funcional. Além disso, quase tudo o que foi escrito está na biblioteca padrão do Kotlin; portanto, talvez no futuro, em vez de escrever outro loop for, você use o estilo funcional que o Kotlin nos fornece.
Provavelmente o mais difícil no estilo funcional é que o problema pode ser resolvido de maneiras diferentes. O mais óbvio pode ser complicado e difícil de entender no futuro, e escrever o mais compreensível pode levar tempo e reflexão. A única coisa que pode ajudar no domínio é a prática e o treinamento constantes.
PS: Como mencionado acima, você pode ver o
repositório com todos os exemplos que estão no artigo. Execute os testes e veja como funciona!
PPS: você também pode procurar uma abordagem alternativa que implemente
funcionalidade semelhante.
E não deixe de ver mais tarde
https://arrow-kt.io/ . Na minha opinião, você não deve olhar para lá imediatamente, porque tudo parece bem assustador, mas mais tarde, quando functores e mônadas não o assustarem, não deixe de estudá-lo.