Skip to main content

Funciones de orden superior

⏱ Dedicación recomendada: 0 minutos
Esto considera el contenido visible y relevante, e ignora texto colapsado o marcado como opcional.

r8vnhill/functional-programming-kt
Be lazy...

Puedes ejecutar el siguiente comando para crear el módulo 

./gradlew setupHofModule

Mientras se crean los archivos necesarios, puedes leer el código para saber qué está pasando.

import tasks.ModuleSetupTask

tasks.register<ModuleSetupTask>("setupHofModule") {
    description = "Creates the base module and files for the higher-order functions lesson"
    module.set("hof")
    doLast {
        createFiles(
            "functional.map",
            main to "Map.kt",
            test to "MapTest.kt"
        )
        createFiles(
            "functional.filter",
            main to "Filter.kt"
        )
        createFiles(
            "functional.fold",
            main to "Fold.kt",
            test to "FoldTest.kt"
        )
    }
}

Preocúpate de que el plugin hof esté aplicado en el archivo build.gradle.kts de tu proyecto.

./gradlew setupHofModule

Preocúpate de que el nuevo módulo esté incluido en el archivo settings.gradle.kts.

Las funciones de orden superior son aquellas que reciben otras funciones como parámetros o retornan una función como resultado. Esto permite un nivel adicional de abstracción y reutilización de código.

Por ejemplo, una función que aplique otra función a todos los elementos de una lista podría tener el siguiente tipo:

(List<A>, (A) -> B) -> List<B>

o

List<A>.((A) -> B) -> List<B>

Esto indica que la función toma una lista de tipo A, una función que transforma elementos de tipo A en B, y devuelve una nueva lista de tipo B.

Otro ejemplo es una función que componga dos funciones y retorne una nueva función. Su tipo sería:

(f: (A) -> B, g: (B) -> C) -> ((A) -> C)

Esto significa que la función toma dos funciones f y g y devuelve una nueva función que transforma un valor de tipo A a tipo C pasando por los dos pasos intermedios (primero aplica f y luego g).

Asociación a la derecha​

En la notación de funciones, el operador -> se asocia a la derecha, lo que significa que:

(A) -> (B) -> C

Es equivalente a:

(A) -> ((B) -> C)

Esto implica que la función acepta un parámetro de tipo A y retorna una función que a su vez toma un parámetro de tipo B y retorna un valor de tipo C. Este concepto es clave en la currificación, una técnica común en la programación funcional.

Currificación

La currificación es un proceso en programación funcional que consiste en transformar una función que toma múltiples argumentos en una secuencia de funciones, cada una de las cuales toma un único argumento. Esto permite aplicar parcialmente la función y facilita la reutilización y composición de funciones. En lugar de pasar todos los argumentos a la vez, la función currificada se llama con un solo argumento, devolviendo otra función que espera el siguiente argumento, y así sucesivamente.

Supongamos que tenemos una función que suma dos números:

fun add(a: Int, b: Int): Int = a + b

La función add toma dos argumentos (a y b) y devuelve su suma. Ahora, vamos a currificar esta función.

La versión currificada de la función add se vería así:

fun addCurried(a: Int): (Int) -> Int {
    fun add(b: Int): Int = a + b
    return ::add
}

En esta versión, addCurried toma un solo argumento (a) y devuelve una función que espera el segundo argumento (b). Cuando llamamos a esta nueva función con b, devuelve la suma de a y b.

Podemos usar la función currificada de la siguiente manera:

val addFive = addCurried(5) // Devuelve una función que suma 5
val result = addFive(3)     // Aplica la función con el argumento 3
println(result)             // Output: 8

En este caso, addFive es una función que suma 5 a cualquier número que se le pase como argumento. Luego, llamamos a addFive(3) y obtenemos 8 como resultado.

Beneficios

  1. Aplicación parcial: Permite aplicar solo algunos argumentos a una función y obtener una nueva función que espera los argumentos restantes.
  2. Composición de funciones: Facilita la composición de funciones al permitir encadenar y combinar funciones de manera flexible.
  3. Reutilización y flexibilidad: Las funciones currificadas son más flexibles y reutilizables, ya que se pueden adaptar y combinar de diversas formas.

Limitaciones

  1. Mayor complejidad: Currificar funciones puede hacer que el código sea más difícil de entender para personas que no estén familiarizadas con el paradigma funcional, ya que las funciones currificadas implican múltiples llamadas en cadena.
  2. Rendimiento: Dependiendo de la implementación y del entorno, el uso de funciones currificadas puede tener un impacto en el rendimiento debido a la creación de múltiples funciones anidadas. Esto podría ser menos eficiente que una llamada directa con todos los argumentos.
  3. Menor intuitividad en algunos casos: En contextos donde se espera que todas las funciones reciban múltiples parámetros, la currificación puede parecer menos intuitiva, especialmente cuando se convierte en una práctica generalizada en código de gran escala.
Ejercicio: Tipos de Funciones

Indica el tipo de:

  1. Una función que toma una lista y un predicado (una función que devuelve un booleano) y retorna una lista con solo los elementos que cumplan el predicado.
  2. Una función que toma un String que representa un idioma y devuelve una función que toma un nombre y retorna un saludo adecuado a ese idioma.
  3. Una función que toma una lista y una función que combina los elementos de la lista, y retorna un único elemento que resulta de aplicar dicha función.
Solución
  1. (List<A>, (A) -> Boolean) -> List<A>
  2. (String) -> (String) -> String
  3. (List<A>, (List<A>) -> A) -> A

Map​

Vamos a programar la función map. Esta función toma una lista y una función, luego aplica esa función a todos los elementos de la lista, devolviendo una nueva lista con los resultados.

hof/src/test/kotlin/com/github/username/functional/map/MapTest.kt
checkAll(Arb.list(Arb.int())) { list ->
    map(list, ::double).sum() shouldBe list.sum() * 2
}

Implementación iterativa de map​

La implementación básica de map toma una lista de cualquier tipo y una función que se aplica a cada elemento de esa lista. La función map recorre la lista original, aplica la función a cada elemento, y devuelve una nueva lista con los resultados.

hof/src/main/kotlin/com/github/username/functional/map/Map.kt
package com.github.username.functional.map

fun <T, R> map(list: List<T>, f: (T) -> R): List<R> {
    val result = mutableListOf<R>()
    for (i in list) {
        result.add(f(i))
    }
    return result
}

En este código, se crea una lista mutable result que almacenará los resultados. A continuación, la función recorre cada elemento de la lista original, aplica la función f, y añade el resultado a result. Finalmente, se retorna la nueva lista con los resultados aplicados.

Problema de Mutabilidad

El uso de estructuras mutables como MutableList puede generar efectos secundarios y errores inesperados. En programación funcional, se recomienda evitar la mutabilidad y trabajar con estructuras inmutables para reducir el riesgo de errores y mejorar la mantenibilidad del código.

Implementación Recursiva​

Una forma más funcional de implementar map sería utilizando recursión en lugar de un bucle. Esta implementación evita el uso de estructuras mutables, lo cual es más acorde con los principios de la programación funcional.

hof/src/main/kotlin/com/github/username/functional/map/Map.kt
package com.github.username.functional.map

fun <T, R> map(list: List<T>, f: (T) -> R): List<R> = 
    if (list.isEmpty()) {
        emptyList()
    } else {
        listOf(f(list.first())) + map(list.drop(1), f)
    }

En este caso, la función map verifica si la lista está vacía. Si lo está, retorna una lista vacía. Si no, aplica la función f al primer elemento de la lista (list.first()), lo agrega a una nueva lista, y luego llama recursivamente a map con el resto de los elementos de la lista (list.drop(1)).

Ejercicio: Implementación de filter

Programa la función filter, que toma una lista de valores de tipo T y un predicado, y retorna una nueva lista con solo los elementos que cumplen el predicado. Utiliza recursión.

Solución
hof/src/main/kotlin/com/github/username/functional/filter/Filter.kt
package com.github.username.functional.filter

fun filter(list: List<Int>, f: (Int) -> Boolean): List<Int> =
    if (list.isEmpty()) {
        emptyList()
    } else {
        val head = list.first()
        val tail = list.drop(1)
        if (f(head)) {
            listOf(head) + filter(tail, f)
        } else {
            filter(tail, f)
        }
    }

Fold​

Imagina que tienes una lista de números y quieres sumarlos todos. Una forma de hacerlo es recorrer cada número y sumar su valor al total. Este proceso de "acumular" valores es exactamente lo que hace una función como fold.

En programación funcional, fold toma una lista y la "reduce" a un solo valor aplicando una operación (por ejemplo, sumar o multiplicar) a todos sus elementos, uno por uno.

¿Cómo funciona?​

  1. Elemento inicial: Necesitamos un valor inicial que actúe como "base". Este valor se usa para comenzar la acumulación.
  2. Función de acumulación: Usamos una función que toma dos valores: el acumulador (que guarda el resultado parcial) y el siguiente elemento de la lista. La función combina estos dos valores y devuelve un nuevo valor acumulado.
  3. Recorrer la lista: Aplicamos esta función de acumulación a cada elemento de la lista, combinándolo con el valor acumulado hasta ese punto.

Ejemplo con suma​

Si tienes la lista [1, 2, 3] y quieres sumar los números, el proceso sería algo así:

  • Partimos con un acumulador inicial, por ejemplo, 0.
  • Tomamos el primer número (1) y lo sumamos al acumulador (0 + 1 = 1).
  • Tomamos el siguiente número (2) y lo sumamos al acumulador (1 + 2 = 3).
  • Tomamos el último número (3) y lo sumamos al acumulador (3 + 3 = 6).

El resultado final es 6.

Probando fold​

Ahora que tenemos una idea de cómo funciona fold, podríamos comenzar por escribir algunas pruebas para esta función.

hof/src/test/kotlin/com/github/username/functional/fold/FoldTest.kt
checkAll(Arb.list(Arb.int())) { list ->
    fold(list, 0, ::add) shouldBe list.sum()
}
¿Qué acabamos de hacer?

En este código, generamos una lista de números aleatorios y comprobamos que el resultado de fold con la función de suma (add) sea igual a la suma de los elementos de la lista original.

Implementación recursiva de fold​

A continuación, vamos a implementar una versión recursiva de fold:

hof/src/main/kotlin/com/github/your_user/functional/fold/Fold.kt
package cl.ravenhill.functional.fold

fun <T, R> fold(list: List<T>, initial: R, combine: (R, T) -> R): R =
    if (list.isEmpty()) {
        initial
    } else {
        val first = list.first()
        val rest = list.drop(1)
        val newAcc = combine(initial, first)
        fold(rest, newAcc, combine)
    }
¿Qué acabamos de hacer?
  • [3] Recibe una lista de tipo T, un valor inicial de tipo R, y una función que combina un valor de tipo R con un valor de tipo T para producir un nuevo valor de tipo R.
  • [4-5] Si la lista está vacía, retorna el valor inicial.
  • [7-8] Si no, toma el primer elemento de la lista y el resto de la lista.
  • [9] Combina el valor inicial con el primer elemento.
  • [10] Llama recursivamente a fold con el resto de la lista y el nuevo valor acumulado.
Ejercicio: Generación de acrónimos

Supongamos que necesitas implementar una función que construya un acrónimo a partir de una lista de palabras. En específico, tu objetivo es construir una nueva palabra a partir de la primera letra de cada palabra de la lista. Si la palabra tiene menos de 3 letras, la ignoras.

Implementa la función acronym: (List<String>) -> String que cumpla con esta especificación utilizando la función fold.

acronym(listOf("Functional", "Programming", "in", "Kotlin")) shouldBe "FPK"
Solución
fun combine(acc: String, word: String): String =
    if (word.length >= 3) acc + word.first() else acc
fun acronym(words: List<String>) = fold(words, "", ::combine)

¿Qué aprendimos?​

En esta lección, exploramos el concepto y la implementación de funciones de orden superior en Kotlin, enfocándonos en la flexibilidad y expresividad que estas funciones aportan a la programación funcional. A través de ejemplos prácticos como map, filter, y fold, demostramos cómo utilizar funciones de orden superior para transformar y reducir listas de datos.

Puntos clave:​

  1. Funciones de orden superior: Las funciones de orden superior permiten operar y transformar colecciones de forma declarativa, pasando funciones como argumentos o retornándolas como resultados.
  2. Implementación de map y fold: Implementamos map y fold tanto en versiones iterativas como recursivas, siguiendo principios de inmutabilidad y eliminando efectos secundarios para mejorar la predictibilidad y la seguridad del código.

Estas herramientas son fundamentales para avanzar en la programación funcional en Kotlin y otros lenguajes. Al comprender estos conceptos y su implementación, puedes diseñar soluciones más modulares y reutilizables, apoyando la creación de APIs y librerías que aprovechen la abstracción y flexibilidad de las funciones de orden superior.

Bibliografías Recomendadas

  • 📚 "Getting started with functional programming in Kotlin". (2021). Marco Vermeulen, Rúnar Bjarnason, Paul Chiusano, en Functional Programming in Kotlin, (pp. 17-30.) Manning.