Mis ejemplos favoritos de programación funcional en Kotlin

Una de las grandes características de Kotlin es que admite programación funcional. Echemos un vistazo y analicemos algunas funciones simples pero expresivas escritas en Kotlin.

Trabaja con colecciones

Kotlin admite trabajos convenientes con colecciones. Hay muchas características diferentes. Supongamos que creamos un sistema para una universidad. Necesitamos encontrar a los mejores estudiantes que merecen una beca. Tenemos el siguiente modelo de Student :

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

Ahora podemos llamar a la siguiente función para obtener una lista de los diez mejores estudiantes que cumplen con todos los criterios:

 students.filter { it.passing && it.averageGrade > 4.0 } // 1 .sortedBy { it.averageGrade } // 2 .take(10) // 3 .sortedWith(compareBy({ it.surname }, { it.name })) // 4 

• Dejamos solo a los estudiantes que aprobaron el examen, cuyo puntaje promedio es más de 4.0.
• Ordénelos por el puntaje promedio.
• Dejamos a los primeros diez estudiantes.
• Clasifícalos alfabéticamente. El comparador primero compara los apellidos, y si son iguales, entonces compara los nombres.

¿Qué sucede si, en lugar del orden alfabético, necesitamos mantener el orden original de los estudiantes? Podemos hacer esto 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 

• Vincula el índice de iteración actual a cada elemento.
• Ordenar por el puntaje promedio y dejar a los primeros diez estudiantes.
• Ordenar de nuevo, pero ahora por índice.
• Eliminamos índices y dejamos solo estudiantes.

Este ejemplo demuestra cuán simple e intuitivo es el trabajo con colecciones en Kotlin.

SuperSet (booleano)

Si estudiaste álgebra en una universidad, puedes recordar qué es un superconjunto. Para cualquier conjunto, su superconjunto es el conjunto de todos sus subconjuntos, incluido el conjunto original en sí y el conjunto vacío. Por ejemplo, si tenemos el siguiente conjunto:

{1,2,3}

Ese es su superconjunto:

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

En álgebra, tal función es muy útil. ¿Cómo lo implementamos?

Si quieres desafiarte a ti mismo, deja de leer ahora mismo y trata de resolver este problema tú mismo.

Comencemos nuestro análisis con una simple observación. Si tomamos algún elemento del conjunto (por ejemplo, 1), el superconjunto tendrá un número igual de conjuntos con este elemento ({1}, {1,2}, {1,3}, {1,2,3}) y sin ella ({}, {2}, {3}, {2,3}).

Tenga en cuenta que el segundo conjunto es un superconjunto ({2,3}), y el primero es un superconjunto ({2,3}) con nuestro elemento agregado (1) a cada conjunto. Por lo tanto, podemos calcular el superconjunto tomando el primer elemento, calculando el superconjunto para todos los demás y devolviendo la suma del resultado y el resultado con la adición del primer 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 } 

Pero este método no funcionará. El problema es un conjunto vacío: first arrojará un error cuando el conjunto esté vacío. Aquí la definición de un superconjunto viene al rescate: el superconjunto de un conjunto vacío es un conjunto vacío: powerset ({}) = {{}}. Así es como se ve el algoritmo corregido:

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

Veamos como funciona. Supongamos que necesitamos calcular powerset ({1,2,3}). El algoritmo actuará de la siguiente manera:

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}

conjunto de potencia ({}) = {{}}

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

Pero podemos mejorar nuestra función aún más. Usemos la función let para hacer la notación más corta y 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() } 

También podemos definir esta función como una función de extensión para Collection , de modo que podamos usar esta función como si fuera el setOf(1,2,3).powerset() Set ( setOf(1,2,3).powerset() lugar 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() } 

También podemos reducir los efectos negativos de la recursión creada. En la implementación anterior, el estado del superconjunto crece con cada iteración (con cada llamada recursiva), porque el estado de la iteración anterior debe almacenarse en la memoria.

En cambio, podríamos usar un bucle regular o tailrec función tailrec . Utilizaremos la segunda opción para mantener la legibilidad de la función. El modificador tailrec solo permite una llamada recursiva en la última línea de función ejecutada. Así es como podemos cambiar nuestra función para usarla de manera más eficiente:

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

Esta implementación es parte de la biblioteca KotlinDiscreteMathToolkit , que define muchas otras funciones utilizadas en matemáticas discretas.

Quicksort

Tiempo para el ejemplo más interesante. Verá cómo un problema complejo puede simplificarse y hacerse legible utilizando las herramientas de estilo y programación funcional.

Implementamos un algoritmo de ordenación rápida. El algoritmo es simple: seleccionamos algún elemento (pivote ( barra rusa)) y distribuimos todos los demás elementos en dos listas: una lista con elementos más grandes que la barra y más pequeños. Luego ordenamos recursivamente estas submatrices. Finalmente, combinamos una lista ordenada de elementos más pequeños, una barra y una lista ordenada de elementos más grandes. Para simplificar, tome el primer elemento como una barra. Aquí está la implementación 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() } // Usage listOf(2,5,1).quickSort() // [1,2,5] 

Se ve hermosa, ¿verdad? Esta es la belleza de la programación funcional.

El primer problema con dicha función es su tiempo de ejecución. Ella es completamente inoportuna. Pero es corto y fácil de leer.

Si necesita una función optimizada, puede usar la función de la biblioteca estándar de Java. Se basa en varios algoritmos dependiendo de ciertas condiciones y está escrito de forma nativa. Esto debería ser mucho más eficiente. ¿Pero cuánto exactamente? Comparemos estas dos funciones. Ordenemos varias matrices diferentes con elementos aleatorios y comparemos el tiempo de ejecución:

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

Aquí están los resultados que obtuvimos:

La clasificación de Java stdlib de 100000 elementos tomó 83
La ordenación rápida de 100000 elementos tomó 163
La clasificación de Java stdlib de 1,000,000 de elementos tomó 558
La clasificación rápida de 1,000,000 de elementos tomó 859
La clasificación de Java stdlib de 10,000,000 elementos tomó 6182
La clasificación rápida de 10,000,000 elementos tomó 12133

Como puede ver, la función quickSort casi 2 veces más lenta. Incluso para grandes listas. En casos normales, la diferencia será típicamente de 0.1ms a 0.2ms. Esto explica por qué en algunos casos podemos usar una función que está ligeramente menos optimizada, pero que es fácil de leer y simple.