Haskell es un lenguaje totalmente funcional y extremadamente conciso. Cualquiera que haya intentado escribir código en Haskell se da cuenta de lo conciso y elegante que es escribir lo mismo en un lenguaje imperativo. Lograr lo mismo en Java, en mi opinión, es imposible, pero Kotlin le permite moverse en esta dirección y probar un estilo totalmente funcional. Podemos derivar todas las funciones complejas que podamos necesitar de la base inicial de las 3 funciones más famosas: mapear, filtrar, reducir. Además, creé un
repositorio que puedes estudiar y ver las pruebas.
Antes de comenzar, me gustaría llamar la atención sobre el hecho de que no vale la pena implementar un enfoque funcional de esta manera, porque el código será críticamente lento y no debe usarse en aplicaciones de producción. Ciertamente, hay opciones para mejorarlo, pero el propósito del artículo no es revelar estas opciones, sino considerar un enfoque alternativo para escribir código. En cualquier caso, comprender este enfoque lo ayudará a trabajar con estructuras de datos recursivas, y puede apreciar la belleza y la elegancia de cómo se lee el código y cuánto más fácil es comprenderlo.
Funciones básicas
Las listas juegan un papel muy importante en el lenguaje y se les implementan muchas funciones útiles. Veamos algunos de ellos y cómo se pueden implementar en Kotlin.
head (x:_) = x head [] = badHead
Si hay elementos en la lista, devolveremos el primero, de lo contrario devolveremos un error.
No tenemos la oportunidad de escribir dicho código, pero, en general, si se mira de cerca, es muy similar a cuando la plantilla. También usaremos la función de extensión para luego poder usar este método en las listas y tener una forma un poco más concisa de obtener el valor, sin los corchetes al final, como una llamada al método.
val <T> List<T>.head: T get() = when (this.isEmpty()) { true -> throw NoSuchElementException("List is empty.") false -> this[0] }
Para usar convenientemente la recursividad, también nos gustaría dividir la lista en el primer elemento + todos los demás. Intentemos implementar la función de cola para esto.
Así es como se ve en Haskell:
tail (_:xs) = xs tail [] = errorEmptyList "tail"
Desafortunadamente, Kotlin no proporciona un nivel de coincidencia de patrones que los desarrolladores puedan describir con el mismo estilo, así que aquí tenemos que escribir un poco sobre cuándo.
val <T> List<T>.tail: List<T> get() = drop(1)
Es un poco deshonesto usar una función de la biblioteca de idiomas, pero por otro lado, en cualquier caso, tendríamos que escribir código para este método, por lo que sería mejor usar métodos que ya funcionen.
Ahora podemos dividir la lista en el primer elemento + el resto de la lista. También necesitaremos la función de concatenar la lista y un elemento, que luego se utilizará activamente para la conversión y otras operaciones en la lista.
operator fun <T> List<T>.plus(x: T): List<T> = ArrayList(this).also { it.add(x) }
Ahora podemos agregar una lista al elemento al final, y nuestra implementación de la función de mapa funciona y está lista para usar. Desafortunadamente, de nuevo, no hay forma de agregar un objeto a la lista de una manera más conveniente, por lo que utilizamos el método
add .
Por el momento tenemos casi todo lo que necesitamos. Lo único que necesitamos ahora es poder describir la condición límite para salir de la recursividad. Para esto, utilizaremos el
método estándar
isEmpty () . Paremos y veamos lo que tenemos en este momento:
- isEmpty (): ¿hay elementos en la lista?
- head - el primer elemento de la lista
- cola: una lista sin el primer elemento
- list + element: podemos concatenar la lista con un objeto
De hecho, eso es todo lo que necesitamos para obtener todos los métodos que necesitamos.
Para mi gusto, sería más conveniente usar la comparación de longitud de lista en las declaraciones
when . Kotlin ya nos proporciona el
tamaño para obtener la longitud de esta lista. Sin embargo, supongamos que queremos implementarlo nosotros mismos. Con nuestra funcionalidad, será bastante simple:
val <T> List<T>.size: Int get() = when (this.isEmpty()) { true -> 0 false -> 1 + this.tail.size }
Aplicación de funciones básicas.
Considere el ejemplo más común. Supongamos que tenemos una lista de enteros, y queremos resumirlos, olvidando la existencia de ciclos. Todo lo que tenemos son los métodos que derivamos anteriormente y la recursividad. Para hacer esto, usaremos el mismo enfoque que al calcular el tamaño de la lista:
fun sum(xs: List<Int>): Int = when (xs.size) { 0 -> 0 else -> xs.head + sum(xs.tail) }
La idea es muy simple: si no hay elementos en la lista, entonces la suma es 0; de lo contrario, es la suma del primer elemento y una llamada recursiva de la suma de la cola.
A pesar del hecho de que no nos importa la velocidad y las optimizaciones en este código, no podemos evitar recordar las capacidades del lenguaje para usar la recursividad de cola. La recursividad de cola es un caso especial de recursión en el que una llamada recursiva es la última operación antes de regresar de una función. Este tipo de recursión es notable porque está garantizado para permitirle reconstruir el código para la iteración. Como sabe, el principal problema de la recursividad es que durante la ejecución de la función es necesario almacenar la pila de llamadas para que cuando se alcance la condición límite, pueda regresar y volver a calcular el resultado final.
Puede parecer que la función de la cantidad que describimos es así, porque la última llamada es
sum (xs.tail) . Sin embargo, esto no es cierto. Si describe el código un poco diferente, será obvio:
fun sum(xs: List<Int>): Int = when (xs.size) { 0 -> 0 else -> { val head = xs.head val tailSum = sum(xs.tail) head + tailSum } }
Ahora vemos que, de hecho, la última llamada es la suma del primer elemento y la parte restante de la cola.
La buena noticia es que si agrega el modificador
tailrec a una función, el IDE le dirá que la función no lo es. Sin embargo, arreglar esto es bastante sencillo. Un truco común que corrige una función es usar una variable auxiliar para almacenar los resultados. Se ve así:
tailrec fun sum(xs: List<Int>, acum: Int): Int = when (xs.size) { 0 -> acum else -> sum(xs.tail, xs.head + acum) }
Para calcular la suma de los elementos, es suficiente pasar 0. como el segundo parámetro, y para que sea completamente idiomático, volveremos a hacer la función un poco más, ocultando los cálculos principales en la función interna sin que el mundo exterior tenga acceso al parámetro que No es necesario
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) }
Teniendo este conocimiento, puede ver que la función de tamaño que implementamos anteriormente no satisface las condiciones necesarias para la recursión de la cola.
Ahora estamos listos para implementar el mapa, filtrar y reducir usando Kotlin. Más adelante veremos que fue suficiente para darse cuenta solo de esto último, y el resto, en general, son derivados de él. Pero lo primero es lo primero.
Funciones principales
Mapa
Una implementación iterativa de esta función implica un movimiento secuencial a través de la lista, utilizando la función de conversión y agregando todos los elementos recibidos a la nueva colección. Usaremos llamadas recursivas donde la condición de límite es una lista vacía. Entonces la implementación se verá así:
fun <T, R> List<T>.map(f: (T) -> R): List<R> = when (this.size) { 0 -> listOf() else -> f(head) + tail.map(f) }
Si no hay elementos en la lista original, entonces devolvemos una lista vacía, de lo contrario, aplicamos la transformación al primer elemento y agregamos una llamada recursiva al final para el resto de la lista.
Sin embargo, todavía no tenemos una función para concatenar un elemento y una lista. Pero ya podemos darnos cuenta. Para comenzar, derivamos un caso más general de concatenación de un par de listas y luego lo usamos para agregar otra lista al 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
La implementación será muy similar al mapa. La única diferencia es que debe comprender si necesita agregar el elemento actual al resultado. Para hacer esto, llamaremos a la lambda que recibimos como parámetro. La implementación se verá así:
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) }
Si el elemento actual cumple la condición del filtro, agréguelo recursivamente al final de la lista; de lo contrario, continuaremos trabajando solo con el final de la lista.
REDUCIR
La función más difícil de entender y, al mismo tiempo, la más poderosa (en el mundo funcional se conoce como
pliegue ). Muy a menudo, se utiliza para contraer una lista en un solo elemento. Tiene un cierto valor inicial
s0 , y también hay una lista de elementos
a [] y una función
f , que devuelve uno nuevo para el valor inicial y el siguiente elemento de la lista.
f (s0, a [0]) = s1 . Y así, pasamos secuencialmente por toda la lista de elementos, obteniendo algún tipo de valor único en la salida. Un ejemplo bastante común es la suma de elementos de la matriz. En este caso, el valor inicial es 0 y la función devuelve la suma de dos elementos:
f (s, a [i]) = s + a [i] . Considere cómo podemos implementar recursivamente esta función.
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) }
En principio, la implementación es exactamente la misma que revisamos anteriormente. Si no hay elementos en la lista, devolvemos el valor actual; de lo contrario, calculamos el nuevo primer elemento y nuevamente llamamos a la función de reducción para él y al final de la lista.
Tenga en cuenta que también podemos crear modificaciones a esta función. Por ejemplo, no pase el valor inicial, pero use el primer elemento de la lista para esto. Para entender que reducir no termina ahí, imagine que usamos una lista diferente como valor inicial. En este caso, cada vez en la iteración almacenaremos no un valor, sino una lista, gracias a la cual nuestras capacidades aumentan considerablemente. Por ejemplo, intentemos aplicar la función reducir de tal manera que obtengamos la lista original en la salida:
fun <T> reduceSame(xs: List<T>) = reduce(listOf<T>(), xs) { ys, s -> ys + s }
Ahora, creo que supones que podríamos usar reducir, para una implementación alternativa de map, filter. Como aprendimos a devolver exactamente la misma lista con reduce, necesitamos hacer muy pocos cambios para poder convertir cada elemento. Para el filtro, todo es muy similar.
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 }
Además, a menudo olvidan que también podemos usar reducir no desde el principio de la lista, sino desde el final. Claro, solo podemos expandir la lista, y después de eso aplicar reducir, pero esto no es interesante. Tratemos de escribir y entender cómo reduce funciona para colapsar la lista en el orden inverso.
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) }
Si la lista no está vacía, aplicamos la función f al resultado de plegar la cola de la lista y el encabezado de la lista. Por lo tanto, el primer elemento se procesará en último lugar; penúltimo - segundo y así sucesivamente. Para esta opción, también puede agregar modificaciones que utilizarán el último elemento de la lista como valor inicial, etc.
Casi siempre, cuando trabaja con listas, puede usar alguna combinación de estas 3 funciones para obtener el resultado que le interesa.
Implementemos también la función
zip , que nos permitirá combinar 2 listas.
En la entrada tenemos 2 listas. Y queremos devolver una lista de pares cuya longitud es igual al mínimo de las listas originales.
Como de costumbre, debe pensar en salir de la recursividad y escribir una función.
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) } }
Puede agregar sus propias modificaciones, lo que le permitirá, en lugar de devolver un par de elementos, aplicar una determinada función a dos elementos. En Haskell, esta función se llama
zipWith . Y se implementa con la funcionalidad que logramos escribir de manera muy simple:
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) }
Muy a menudo, cuando se utiliza el enfoque funcional, surgen problemas cuando necesita realizar manipulaciones basadas no en objetos en listas, sino en índices. Por ejemplo, necesitamos sumar todos los elementos pares de una lista. Puede intentar lograr esto con reducción, manteniendo el valor actual como Pair <Int, Boolean> y agregando el valor if flag == true, y tome la negación de flag cada vez para el siguiente paso. Sin embargo, esto no se ve muy bonito, y el lector tendrá que descubrir qué quiere expresar con este código. Kotlin tiene secuencias infinitas, y son excelentes para resolver este problema. Si analizamos lo que queremos hacer, resulta que queremos filtrar todos los elementos con índices impares y sumar los restantes. Y para poder obtener índices, es suficiente llamar a
zip para la lista y
secuencia [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()
En la biblioteca estándar de Kotlin, puede encontrar la función zip para el par de secuencias.
Ahora veamos un rompecabezas simple que me inspiró a escribir esta guía, y cómo se ve su implementación en un lenguaje imperativo en Kotlin y al final en Haskell.
Es necesario calcular la cantidad máxima entre pares de números adyacentes en una matriz de enteros. La longitud de la matriz es mayor que 1, y no tiene que preocuparse por desbordarse al sumar elementos.
Enfoque imperativo de 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; }
Un enfoque funcional en Kotlin usando funciones escritas (propongo implementar la función max como entrenamiento usted mismo):
fun maxSum(xs: List<Int>) = zipWith(xs, xs.tail, {a, b -> a + b}).max()
Implementación de Haskell:
maxSum xs = maximum $ zipWith (+) xs (tail xs)
Como podemos ver, lo que implementamos en Kotlin (por cierto, podríamos usar reducir para resolver este problema) es muy similar a lo que se puede escribir en Haskell.
Conclusión
Sin lugar a dudas, esto no debe usarse en el desarrollo, porque todo se implementó de manera no óptima solo para demostrar un enfoque funcional. Además, casi todo lo que se escribió está en la biblioteca estándar de Kotlin, por lo que, tal vez en el futuro, en lugar de escribir otro bucle for, usará el estilo funcional que Kotlin nos proporciona.
Probablemente lo más difícil en el estilo funcional es que el problema se puede resolver de diferentes maneras. Lo más obvio puede ser engorroso y difícil de entender en el futuro, y escribir lo más comprensible puede tomar tiempo y pensar seriamente. Lo único que puede ayudar a dominar es la práctica constante y la capacitación.
PD: Como se mencionó anteriormente, puede ver el
repositorio con todos los ejemplos que se encuentran en el artículo. ¡Ejecute las pruebas y vea cómo funciona!
PPS: También puede ver un enfoque alternativo que implementa una
funcionalidad similar.
Y asegúrese de ver más adelante
https://arrow-kt.io/ . En mi opinión, no deberías mirar allí de inmediato, porque todo parece bastante aterrador, pero más tarde, cuando los funtores y las mónadas no te asusten, asegúrate de estudiarlo.