Powered by AppSignal & Oban Pro
Would you like to see your link here? Contact us
Notesclub
Sign in with GitHub
created by hec & contributors
terms privacy

Introducción a la Programación Funcional con Elixir

pf_en_elixir.livemd

avatar
Ángel Herranz
avatar
avatar
More notebooks
0

Introducción a la Programación Funcional con Elixir

Mix.install([{:hidden_cell, github: "BrooklinJazz/hidden_cell"}])

Bienvenidos

¿Alguna vez te has preguntado cómo la programación funcional puede transformar la forma en que abordas el desarrollo de software? Este taller es una invitación abierta para programadores de todos los lenguajes, ya seas novato en el mundo de la programación funcional o tengas experiencia en otros paradigmas.

Como vehículo de aprendizaje vas a usar el lenguaje de programación Elixir, un lenguaje funcional moderno y lleno de nuevas ideas, abordaremos los principios de la programación funcional sin la complejidad que suele asociarse a esta: inmutabilidad, recursividad, pattern matching y funciones de orden superior.

Este taller se ha preparado en forma de cuaderno Livebook. Livebook, una killer application de Elixir que te va a permitir no solo ejecutar código Elixir si no también modificarlo y reejecutarlo para poder hacer tus propias exploraciones y pruebas. Como referencia, es una aplicación similar a Jupyter, es un entorno de desarrollo interactivo que permite compartir conocimiento, desplegar aplicaciones, visualizar datos, ejecutar modelos de aprendizaje, depurar, etc.

Quizás la forma más sencilla de hacer el taller sea descargar este fichero en un directorio y poner en marcha Livebook usando un contenedor:

docker run -p 8080:8080 -p 8081:8081 --pull always -u $(id -u):$(id -g) -v $(pwd):/data ghcr.io/livebook-dev/livebook:0.14.5

Un poco de sintaxis para poder hablar Elixir

  • Elixir es lenguaje con mucho azúcar sintáctico (sintaxis diseñada para hacer las cosas más dulces tanto para escribir como para leer, con el coste de que el lenguaje es menos uniforme y consistente) > Sintactic sugar causes cancer of semicolon (Alan J. Perlis)
  • No voy a usar azucar sintáctico en este taller (aunque a veces no podremos escapar de ello porque Elixir va a responder azucarando algunos resultados).

Tipos básicos

  • Los tipos básicos son integer (big integers), float, binary (array de bytes, usado para representar strings) y átomos (atoms).
  • ¿Qué es un átomo? Constante que empieza por : y que sólo se representa a sí mismo.

Números

Importante: observa la siguiente celda, coloca el cursor del ratón sobre ella y verás que aparece arriba a la izquierda un enlace con texto Evaluate o Reevaluate para evaluar la expresión, haz click y verás el resultado.

# Primo más pequeño que no cabe en 64 bits
18_446_744_073_709_551_615
# Pi
3.141592653589793
  • Como ya has visto el símbolo # inicia un comentario de línea
  • Tú misma puedes crear celdas. Pasa el cursor justo por debajo de este texto y crea una celda de código Elixir para calcular la longitud del ecuador del planeta Tierra sabiendo que su radio es 6378 
# Longitud del ecuador

Binary (String)

# Los strings
"Don't panic"
# Un paquete IP
<<69,0,0,60,28,70,64,0,64,6,177,230,192,168,0,1,192,168,0,199,222,173,190,239,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0>>
# Mi nombre, con acento, en UTF 8
<<195,129,110,103,101,108>>

Átomos

  • Constantes, se usan masivamente
  • Convención: :snake_case 
:ok
:error
:not_found

Tres átomos especiales

:true
:false
:nil

Operador de igualdad (==)

:ok == :error
:ok == :ok

Variables y expresiones

  • Las variables en Elixir empiezan por minúscula
  • Aunque lo vamos a ver con más detalle, las variables en los lenguajes funcionales no son almacenes de datos, son como las variables matemáticas que se pueden ligar a un valor como en una ecuación matemática
  • En Elixir se pueden escribir expresiones, una por línea, el resultado final es la última expresión que se escriba

Por ejemplo:

pi = 3.141592653589793
r = 6378
2 * pi * r

La forma más acertada de leer toda esa expresión es

> Sea pi igual a 3.14…, sea r igual a 6378, en la expresión 2*pi*r

Módulos y funciones

  • Para poder definir funciones (sus nombres empiezan por minúscula) en Elixir éstas tienen que estar dentro de un módulo (cuyo nombre empieza por mayúscula a los efectos de este taller)
  • Deguro que identificas claramente las palabras clave que permiten definir módulos y funciones dentro de los módulos: 
defmodule Universe do
  def meaning(x) do
    x + 1
  end
end
  • Y a continuación puedes usar esa función de nombre meaning cualificando su nombre con el nombre del módulo Universe: Universe.meaning(41)
  • Bajo ningún concepto hay que confundir ese punto con el punto de invocación de métodos en los lenguajes orientados a objeto.
  • Prueba tú mismo el resultado 
Universe.meaning(41)

Alan Turing vs Alonzo Church

  • En la década de 1930 se fijan dos modelos computaciones equivalentes: La máquina de Turing y el $\lambda$-Cálculo de Church.
  • Los lenguajes imperativos (C, Java, Python, JS, etc.), en esencia, siguen el modelo de computación de las máquinas de Turing:

> Hay una serie de almacenes mutables de datos (variables), el estado, nuestros programas imperativos modifican esos almacenes, paso a paso, y el resultado de la computación queda en uno de esos almacenes.

  • Veamos un ejemplo sencillo en Python: 
n = 3
suma = 0
while n > 0:
suma += n
n -= 1
  • Podemos seguir la ejecución paso a paso y entendemos cómo se modifican las variables hasta que el programa termina
Estado Paso Nuevo estado
n = ?, suma = ? n = 3 n = 3, suma = ?
n = 3, suma = ? suma = 0 n = 3, suma = 0
n = 3, suma = 0 while n > 0: n = 3, suma = 0
n = 3, suma = 0 suma += n n = 3, suma = 3
n = 3, suma = 3 n -= 1 n = 2, suma = 3
n = 2, suma = 3 while n > 0: n = 2, suma = 3
n = 2, suma = 3 suma += n n = 2, suma = 5
n = 2, suma = 5 n -= 1 n = 1, suma = 5
n = 1, suma = 5 while n > 0: n = 1, suma = 5
n = 1, suma = 5 suma += n n = 1, suma = 6
n = 1, suma = 6 n -= 1 n = 0, suma = 6
n = 0, suma = 6 while n > 0: n = 0, suma = 6
  • Los lenguajes funcionales, en esencia, siguen el modelo de computación del $\lambda$-Cálculo:

> Un programa funcional es un conjunto de funciones matemáticas y el resultado es lo que devuelve una función para ciertos datos. El modelo de computación es la reducción de expresiones: en cada paso de reducción se substituye una expresión (redex) por su definición substituyendo las variables que aparecían en la definición.

  • Veamos un ejemplo en Elixir de un programa con varias funciones: (==), (+), (-), if-then-else, y suma.
  • La más importante para nosotros es suma: 
defmodule Suma do
  def suma(n) do
    if n == 1 do 1 else n + suma(n-1) end
  end
end
Suma.suma(3)
  • ¿Cómo se ejecuta esa expresión? ¿De qué forma la ejecución llega a 6?
  • Sigue atentamente la ejecución, paso a paso, en cada paso aparece subrayada la expresión que se va a reducir (redex = expresión reducible) por su definición:

Suma.suma(3)

$\rightarrow$ if 3 == 1`` do 1 else 3 + suma(3 - 1) end

$\rightarrow$ if false do 1 else 3 + suma(3 - 1) end

$\rightarrow$ 3 + suma(``3 - 1``)

$\rightarrow$ 3 + ``suma(2)

$\rightarrow$ 3 + if ``2 == 1``do 1 else 2 + suma(2 - 1) end

$\rightarrow$ 3 + ``if false do 1 else 2 + suma(2 - 1) end`` $\rightarrow$3 + (2 + suma(2 - 1))

$\rightarrow$ 3 + (2 + ``suma(1)``)

$\rightarrow$ 3 + (2 + if ``1 == 1``do 1 else 1 + suma(1 - 0) end)

$\rightarrow$ 3 + (2 + ``if true do 1 else 1 + suma(1 - 0) end``)

$\rightarrow$ 3 + (``2 + 1``)

$\rightarrow$ 3 + 3

$\rightarrow$ 6

Recursión

  • La recursión es uno de los elementos básicos de la programación funcional.
  • También, por experiencia, sabemos que es uno de los puntos más complejos de aprender.
  • Sin embargo es mucho más sencillo de lo que parece:

> Para definir una función recursiva basta con pensar que la función ya funciona y ahora buscas los casos básicos en los que puedes definir la función. Ej. asumimos que suma ya funciona, entonces pensamos en un casos básico ($n = 1$, $resultado = 1$) y un caso no básico ($n > 1$): ¿puedo devolver el resultado suponiendo que suma ya funciona? Sí: $n + suma(n-1)$.

Practicando la recursión

¿Te suena esta sucesión? :)

0 1 1 2 3 5 8 13 …
0 1 2 3 4 5 6 7 …

Completa la siguiente celda con la definición de una función a la que le pasas un índice y te devuelve el número de Fibonacci asociado a ese índice.

Recuerda, asume que la función ya funciona y ahora piensa en los casos (índices 0, 1 y n > 1).

defmodule Ej10 do
  def fib(i) do
    
  end
end

Y ahora prueba que tu función hace lo que tiene que hacer.

Ej10.fib(7)

Estructuras de datos

  • Antes de continuar necesitamos estructuras de datos más potentes que los tipos básicos: introduciremos tuplas y listas
  • Nota: Elixir tiene estructuras más potentes aún como por ejemplo diccionarios (llamados maps en Elixir, *no confundir con la función map* que veremos en el taller)

Tuplas

  • Producto cartesiano de diferente aridad (tuplas de 2, 3, 4 elementos, etc.)
  • Sintaxis con llaves
  • Memoria contigua, no se suele hacer que crezcan o decrezcan
  • Veamos un par de ejemplos que representan las posibles respuestas de un servidor HTTP 
{:ok, "..."}
{:error, 404, "Resource not found"}

Listas

  • Todos los lenguajes funcionales tienen listas
  • Una lista puede ser la lista vacía
  • O la lista que tiene un elemento y un resto (otra lista)
  • Como se puede ver la definición vuelva a hacer uso de la recursión
  • Sintaxis de la lista vacía: 
[]
  • Ya tenemos una lista, la lista vacía
  • Ahora ya podemos construir una lista con un elemento.
  • Sintaxis de la lista que tiene un primer elemento y un resto: 
    [ elemento | resto ]
  • Es decir, se escribe [, luego el elemento, luego el caracter pipe |, luego otra lista y luego ]
  • ¿Puedes escribir tú la lista con un único elemento, el 1?
  • Como idea date cuenta de que la única lista que conoces es [] 
# Escribe aquí la lista con un 1
  • A continuación tienes una celda oculta que puedes evaluar. Puedes ver la solución haciendo click en la propia celda y luego pulsando el icono <> en la parte superior derecha. 
[ 1 | [] ]
  • ¿Y una lista con un 2 y un 1?
  • ¿Y con un 3, un 2 y un 1?
  • ¿Y con un 4, un 3, un 2 y un 1? 
[4 | [ 3 | [ 2 | [ 1 | [] ] ] ] ]
  • Ya habrás observado que Elixir, y cualquier otro lenguaje funcional, te ofrecerá una versión azucarada para escribir literales de listas: elementos separados por comas dentro de paréntesis cuadrados.
  • Sin embargo, no te dejes engañar por las apariencias porque internamente la representación es la que has visto anteriormente: 
[1 | [2 | [3 | [4 | []]]]]

Variables matemáticas y la NO asignación

  • El segundo elemento fundamental de la programación funcional es que las variables no son almacenes de datos
  • Las variables en programación funcional son variables matemáticas
  • Cuando en programación funcional se escribe algo como x = 42 lo que estamos diciendo es > Sea x igual a 42 en la expresión siguiente
  • Probemos: 
x = 42
x * x
  • El operador (=) no es una asignación
  • Más bien es la igualdad de las matemáticas
  • Se le puede llamara operador de matching
  • El lenguaje funcional intenta hacer cierta dicha igualdad ligando (binding) las variables involucradas
  • Los lenguajes funcionales imponen ciertas restricciones y sólo se van a ligar las variables cuando aparecen en la parte izquierda de la ecuación
  • Quizás te parezca que simplemente estamos cambiando la palabra asignar por ligar pero veremos que va más allá

Encaje de patrones (o Pattern Matching)

  • El segundo elemento fundamental de la programación funcional es el encaje de patrones
  • En Elixir hay una función para hacer una petición GET de HTTP: :httpc.request/1 (el /1 indica que la función admite un parámetro)
  • Para poder hacer esa llamada antes necesitamos poner en marcha dos servicios: SSL e INETS, lo hacemos así: 
:ssl.start()
:inets.start()
:ok
  • Si la petición :httpc.request/1 va bien, nos devuelve una tupla de dos elementos
  • El primer elemento es :ok
  • El segundo elemento es a su vez una tupla con tres elementos:
    • El primer elemento es a su vez una tupla de tres elementos:
      • la versión de HTTP,
      • el estado de la respuesta (200, 404, 500, etc.)
      • y el texto asociado al estado (“OK”, “NOT FOUND”, “SERVER ERROR”)
    • El segundo elemento es una lista con las cabeceras
    • El tercero es una lista de caracteres con el payload de la respuesta
  • Vamos a escribir una ecuación para ligar varias variables con los valores mencionados con el resultado de invocar :httpc.request("https://google.com"): 
{:ok, {{protocol, status, status_txt}, headers, body}} = :httpc.request("https://google.com")
  • Las variables protocol, status, status_txt, headers y body han quedado ligadas
  • Puedes comprobar tú mismo los valores a los que las variables ha quedado ligados: 
protocol
status
status_txt
headers
body
  • body es la lista de bytes representando los caracteres el el body de la respuesta, puedes pedirle a Elixir que lo imprima en la salida estándar. 
IO.puts(body)

Practicando el Pattern Matching

  • En este taller vamos a hacer todo a mano
  • Vamos a definir la función longitud sobre las listas
  • Para ello vamos a usar la recursión aplicando lo aprendido:
    • Asumimos que la función ya funciona
    • Pensamos en los casos básicos de los datos:

      • lista vacía []

      • lista con al menos un elemento [primero | resto]

    • Vamos a escribir una función por casos (¡como se hacía en las mates!)
    • Cada caso es como definir una función pero su parámetro es un patrón en el que encaja dicho caso 
defmodule Ej20 do
  def long([]) do
    # Escribe a continuación el valor de la longitud de la lista vacía en este caso
  end

  def long([primero | resto]) do
    # Escribe a continuación la expresión de la longitud de la lista [primero | resto]
    # asumiendo que la función long YA FUNCIONA
  end
end
  • Prueba tu código con la siguiente celda: 
Ej20.long([9,8,7,6,5,4,3,2,1])
  • Vete a la celda en la que está definido el módulo Ej20 y añade una segunda función sum que sume todos los elementos de una lista.
  • Y a continuación vamos a escribir unos tests “de verdad” 
ExUnit.start(auto_run: false)

defmodule Test20 do
  use ExUnit.Case, async: true

  test "long works" do
    assert Ej20.long([]) == 0
    assert Ej20.long([0]) == 1
    assert Ej20.long([9,8]) == 2
    assert Ej20.long([9,8,7,6,5,4,3,2,1]) == 9
  end

  test "sum works" do
    assert Ej20.sum([]) == 0
    assert Ej20.sum([0]) == 0
    assert Ej20.sum([9,8]) == 17
    assert Ej20.sum([9,8,7,6,5,4,3,2,1]) == 45
  end
end

ExUnit.run()

¿Preguntas?

Quizás este sea un buen momento para hacer preguntas si no las has hecho ya, claro. ¡¡¡Siénte libre!!!

Practicando con listas

  • ¿Se te ocurre alguna forma de representar los datos de temperatura de varias capitales?
  • Pista: puedes usar listas de pares
  • En la siguiente celda vamos a ligar una variable capitales con una lista de pares capital-temperatura: 
capitales = [
  {"Londres", 13.0},
  {"París", 10.0},
  {"Berlín", 5.0},
  {"Roma", 13.0},
  {"Lisboa", 22.0},
  {"Moscú", 1.0},
  {"Madrid", 16.0},
  {"Ankara", 0.0},
  {"Trípoli", 17.0},
  {"Teherán", 10.0},
  {"Atenas", 17.0},
  {"Budapest", -3.0},
  {"Varsovia", 2.0}
]

Vamos a procesar esos datos escribiendo varias funciones en el siguiente módulo:

  • celsius2fahrenheit: devuelve la lista pero con la temperatura en grados Fahrenheit: $C \times \frac{9}{5} + 32$
  • celsius2kelvin: devuelve la lista pero con la temperatura en grados Kelvin: $C + 273.15$
  • minimum: devuelve la tupla con la mínima temperatura
  • maximum: devuelve la tupla con la máxima temperatura
  • mean: devuelve la temperatura media 
defmodule Ej30 do
  
end

Puedes probar tu implementación con los siguientes tests:

ExUnit.start(auto_run: false)

defmodule Test30 do
  use ExUnit.Case, async: true

  test "c2f works" do
    assert Ej30.celsius2fahrenheit(0.0) == 32.0
    assert Ej30.celsius2fahrenheit(42.0) == 107.6
    assert Ej30.celsius2fahrenheit(100.0) == 212.0
  end

  test "c2k works" do
    assert Ej30.celsius2kelvin(0.0) == 0.0 + 273.15
    assert Ej30.celsius2kelvin(42.0) == 42.0 + 273.15
    assert Ej30.celsius2kelvin(100.0) == 100.0 + 273.15
  end

  test "min/max/mean work" do
    capitales = [
      {"Londres", 13.0},
      {"París", 10.0},
      {"Berlín", 5.0},
      {"Roma", 13.0},
      {"Lisboa", 22.0},
      {"Moscú", 1.0},
      {"Madrid", 16.0},
      {"Ankara", 0.0},
      {"Trípoli", 17.0},
      {"Teherán", 10.0},
      {"Atenas", 17.0},
      {"Budapest", -3.0},
      {"Varsovia", 2.0}
    ]

    assert Ej30.minimum(capitales) == {"Budapest", -3.0}
    assert Ej30.maximum(capitales) == {"Lisboa", 22.0}
    assert Ej30.mean(capitales) ==
      Enum.reduce(capitales, 0, fn {_,c}, s -> s + c end) / length(capitales)
  end
end

ExUnit.run()

Inmutabilidad

  • En un lenguaje orientado a objetos podríamos programar un método insert que podríamos invocar sobre capitales (algo parecido a capitales.insert({"Munich", 5})) para poder modificar el objeto.
  • En un lenguaje funcional esa posibilidad no existe, cualquier dato computado por el lenguaje no es posible modificarlo.
  • Esta propiedad, la inmutabilidad, facilita el razonamiento sobre el código y hace la concurrencia más manejable.
  • Te reto a que implementes una función que mute el contenido de una lista, por ejemplo una función que actualice las capitales añadiendo otra (ej. {"Munich", 5}) como primer o último elemento: 
defmodule Ej40 do
  def insert(temperaturas, dato) do
    # Intenta modificar temperaturas añadiendo dato
  end
end
  • Ejecuta la función y comprueba el efecto de la misma volviendo a consultar el valor de la variable capitales 
# Intenta ejecutar Ej40.insertar para modificar capitales
# Y ahora volvemos a consultar el valor al que está ligado la variable
capitales

Elixir permite el shadowing de variables

Quizás ya hayas encontrado una posibilidad para modificar la variable capitales añadiendo una nueva ciudad, algo como esto:

capitales = Ej40.insert(capitales, {"Munich", 5})

Seguro que has pensado, ¡Te he pillado! Con que no tiene estado, ¿eh?.

Realmente sigue sin haber estado, las variables realmente no pueden cambiar y lo que ocurre es que Elixir (y muchos otros lenguajes funcionales) permiten el shadowing de variables.

  • Al volver a hacer un matching con una variable que ya estaba ligada lo que estamos haciendo es introducir una nueva variable con el mismo nombre y hacer que la anterior deje de ser visible.
  • Esto significa que no hay nada que puedas hacer con la nueva variable que permita modificar un dato previo y por lo tanto se conserva la inmutabilidad.

Supongamos que tenemos las capitales originales:

capitales = [
  {"Londres", 13.0},
  {"París", 10.0},
  {"Berlín", 5.0},
  {"Roma", 13.0},
  {"Lisboa", 22.0},
  {"Moscú", 1.0},
  {"Madrid", 16.0},
  {"Ankara", 0.0},
  {"Trípoli", 17.0},
  {"Teherán", 10.0},
  {"Atenas", 17.0},
  {"Budapest", -3.0},
  {"Varsovia", 2.0}
]

Supongamos que queremos crear un dato con las capitales y el número de capitales:

cuenta_capitales = {length(capitales), capitales}

Y supongamos que “cambiamos” capitales:

capitales = Ej40.insert(capitales, {"Munich", 5})

¿Qué pasa con cuenta_capitales?

cuenta_capitales

Orden superior (1/3)

  • Otro elemento esencial de la programación funcional es el orden superior: las funciones son ciudadanos de primera categoría en el lenguaje.
  • Eso significa que las funciones pueden ser pasadas como parámetros y pueden ser devueltas como resultados.
  • ¿Te has fijado que las funciones celsius2fahrenheit y celsius2kelvin son iguales? La única diferencia es la fórmula que aplican en el recorrido.
  • En programación funcional (ahora ya heredado en tantos y tantos lenguajes imperativos) ese “patrón” lo puede realizar la función map.
  • map es una función de orden superior, toma una lista como primer elemento, una función como segundo argumento, y aplica la función a cada elemento de la lista.
  • Una definición recursiva por casos tendría este esquema por casos:
    • El map de la lista vacía es la lista vacía.
    • El map de una lista con un primer elemento y un resto es una lista cuyo primer elemento es aplicar la función al primer elemento de la lista y el resto se define recursivamente.

Importante: En Elixir, la forma de escribir que una función ligada en una variable f se aplica a un valor v es usando el . como operador de aplicación de funciones: f.(v). Personalmente creo es una de las cosas más feas de Elixir.

El siguiente ejercicio consiste en definir un módulo Ej50 que contendrá algunas funciones de orden superior siendo map la primera. Defínela por casos tal y como está indicado:

defmodule Ej50 do
  def map([],f) do
    
  end
  
  def map([x | xs], f) do
    
  end
end
  • ¿Cómo podríamos probar Ej50.map?
  • Supongamos que queremos probarlo sumando uno a todos los elementos de una lista.
  • Un ejemplo para el primer parámetro es sencillo, podría ser [1,2,3,4,5]
  • Pero ¿y el segundo parámetro?
  • Podríamos definir una función inc que toma un dato x y devuelve x+1
  • Añade tú esa función al módulo Ej50, después de la función map y ahora prueba esto: 
Ej50.map([1,2,3,4,5], &amp;Ej50.inc/1)
  • Otra vez un poco feo: Elixir usa el prefijo & para referirse a la función y exige que digas a qué versión de la función te refieres, en este caso la que acepta sólo 1 argumento. Feo :(

Lambda abstracciones (funciones anónimas)

  • En muchas ocasiones no se quere definir una función para poder pasarla como argumento
  • Para ello los lenguajes funcionales ofrecen la posibilidad de crear funciones insitu
  • Estas constricciones se llaman lambda abstracciones (también funciones anónimas)
  • La sintaxis es fn x -> e end, y dicha expresión es **la función que toma una x y devuelve un valor e.
  • Veamos su uso con el map sobre [1,2,3,4,5] 
Ej50.map([1,2,3,4,5], fn x -> x + 1 end)

Practicando el orden superior (1/3)

  • Para practicar el orden superior te voy a pedir que reimplementes el módulo Ej30 usando orden superior.
  • Empecemos por las funciones celsius2fahranheit y celsius2kelvin
  • ¿Puedes implementarlas con map?
  • Hazlo todo en el siguiente módulo: 
defmodule Ej60 do
  # Implementa aquí las funciones de Ej30 usando orden superior
end

Orden superior (2/3)

  • ¿Te has dado cuenta de que las funciones que calculan la longitud de una lista y la suma de sus elementos (módulo Ej20) siguen el mismo patrón? A saber:
    • Para la lista vacía se devuelve la solución (0 en ambos casos)
    • Para la lista no vacía se hace la llamada recursiva y luego se hace una operación sobre el resultado (para la longitud se suma 1 y para la suma se suma el valor del primer elemento de la lista)
  • Asombrosamente este patrón es ubicuo, también lo puedes detectar en el resto de las funciones del módulo módulo Ej30 (minimum, maximum y mean). Obsérvalo.
  • ¿Sería posible capturar este patrón con orden superior igual que capturamos el patrón del map?
  • ¿Qué hace falta?
  • El patrón necesita una lista, un valor resultado cuando la lista es vacía y una función que realice la operación concreta.
  • El nombre de dicho patrón es reduce, ¿te atreves a implementarlo? 
defmodule Ej70 do
  # Implementa le patrón reduce por casos
  def reduce(lista, base, funcion) do
    
  end
end

Pistas:

  • Para el caso de la lista vacía basta devolver base
  • Para el caso de la lista con un primer elemento y un resto hay que llamar recursivamente a reduce y, de alguna forma, hay que ejecutar la función usando el primer elemento de la lista y otro dato, ¿pero qué dato?

Orden superior (3/3)

Estamos a punto de terminar el taller, espero que lo estés pasando bien :)

  • Hemos dicho que las funciones son ciudanos de primer orden y hemos visto ejemplos de cómo se pueden pasar funciones como parámetros y de lo útil que es.
  • Pero las funciones pueden también devoler funciones.
  • ¿Para qué podría servir algo así?
  • Imagina que necesitamos una función que genere saludos personalizados dependiendo del idioma.
  • La idea es que una función inicial reciba el idioma y devuelva una función que, a su vez, reciba el nombre de la persona para generar el saludo. 
defmodule Saludos do
  def generar_saludo(idioma) do
    case idioma do
      :es -> fn nombre -> "Hola, #{nombre}!" end
      :en -> fn nombre -> "Hello, #{nombre}!" end
      :fr -> fn nombre -> "Bonjour, #{nombre}!" end
      _ -> fn nombre -> "Hi, #{nombre}!" end
    end
  end
end

saludo_es = Saludos.generar_saludo(:es)
saludo_en = Saludos.generar_saludo(:en)

# saludos_es y saludos_en son funciones que esperan el nombre
# de una persona para saludar en el idioma adecuado

IO.puts(saludo_es.("María"))
IO.puts(saludo_en.("John"))

1BRC

Mi última propuesta es que intentes escribir usando orden superior básico (maps y reduces) una función que sea capaz de procesar entradas como las del reto The One Billion Row Challenge:

  • Por supuesto no vamos a procesar un billion (1000 millones) de datos ciudad-temperatura, pero tendremos dos ficheros: uno con 1000 entradas para probar, otro con 1 millón para ver que vamos razonablemente bien de velocidad.
  • Cada línea del fichero de entrada tiene un nombre de ciudad y una temperatura.
  • La salida la vamos a dar en forma de lista de tuplas de esta forma {nombre_de_ciudad, {temp_minima, temp_maxima, temp_media}} donde no se puede repetir la misma ciudad (¡Eso es un diccionario!)
  • Piensa en el algoritmo y mira a ver si se parece a este que te propongo:
    1. Leer todas las líneas (lista de strings).
    2. Procesar cada string para generar una tupla {nombre_de_ciudad, medida}.
    3. Empezar con un diccionario vacío y procesar cada tupla anterior actualizando el diccionario, cada entrada del diccionario tiene esta forma {nombre_de_ciudad,{medida_min, medida_max, medida_suma, num_medidas}}
    4. Se procesa el diccionario para calcular la media.
    5. Finalmente el reto exige que el resultado esté ordenado alfabéticamente por ciudad.

Paso 1 y 2: lectura de medidas

  • Te regalo un código que devuelve la lista de medidas en una lista de tuplas como las acordadas: {nombre_de_ciudad, medida} (variable medidas)
  • Observa el uso de la función de orden superior map para convertir cada string en una tupla. 
stream = File.stream!("/data/files/measurements_1krc.txt")
paso1 = Enum.to_list(stream)
paso2 = Ej50.map(
  lineas,
  fn linea ->
    [ciudad, medida_str] = String.split(linea, ";")
    {medida, "\n"} = Float.parse(medida_str)
    {ciudad, medida}
  end
)

Diccionario

  • Para poder realizar los pasos 3 y 4 del algoritmo necesitamos un módulo para implemnentar las funciones de un diccionario.
  • Seguro que puedes completarlo. 
defmodule Ej80 do
  def get(dict, key) do
    # Devuelve {:ok, value} si se encuentra key y :error
    # si no se encuentra
  end

  def put(dict, key, value) do
    # Devuelve el diccionario actualizando key con value
  end

  def update(dict, key, f) do
    # Actualiza el diccionario con un nuevo valor para key
    # calculado con la función f (que recibe como argumento
    # el valor antiguo). Devuelve dict si key no se encuentra.
  end
end
ExUnit.start(auto_run: false)

defmodule TestDict do
  use ExUnit.Case, async: true

  test "dict works" do
    dic0 = []

    assert Ej80.get(dic0,"a") == :error

    dic1 = Ej80.put(dic0,"z",1)

    # Se puede "asertar" que se puede hacer patern matching
    assert :error = Ej80.get(dic1,"a")
    assert {:ok, 1} = Ej80.get(dic1,"z")

    dic4 = [{"a",1}, {"b", 2}, {"c", 3}, {"d",4}]
    assert :error = Ej80.get(dic4,"z")
    assert {:ok, 1} = Ej80.get(dic4,"a")
    assert {:ok, 3} = Ej80.get(dic4,"c")
    assert {:ok, 4} = Ej80.get(dic4,"d")

    dic5 = Ej80.put(dic4, "e", 5)
    assert :error = Ej80.get(dic5,"z")
    assert {:ok, 1} = Ej80.get(dic5,"a")
    assert {:ok, 3} = Ej80.get(dic5,"c")
    assert {:ok, 4} = Ej80.get(dic5,"d")
    assert {:ok, 5} = Ej80.get(dic5,"e")

    # Shadowing de dict5!
    dic5 = Ej80.put(dic5, "a", 42)
    dic5 = Ej80.put(dic5, "c", 43)
    dic5 = Ej80.put(dic5, "e", 44)
    assert :error = Ej80.get(dic5,"z")
    assert {:ok, 42} = Ej80.get(dic5,"a")
    assert {:ok, 2} = Ej80.get(dic5,"b")
    assert {:ok, 43} = Ej80.get(dic5,"c")
    assert {:ok, 44} = Ej80.get(dic5,"e")

    inc = fn x -> x + 1 end
    assert {:ok, 3} = Ej80.get(Ej80.update(dic5,"b",inc), "b")

    # Cuidado porque esto no tiene porqué ser así
    # (ej. update podría invertir el diccionario)
    assert Ej80.update(dic5,"z",inc) == dic5
  end
end

ExUnit.run()

Paso 3

  • En este paso reduciremos la lista con la función de orden superior Ej70.reduce
  • La función reduce necesita tres argumentos:
    1. la lista de entrada (las medidas)
    2. el caso base para cuando la lista anterior no tenga datos (un diccionario)
    3. la función de acumulación (que toma una medida y un diccionario y actualiza el diccionario con esa medida)
  • Puedes dejar la lista en una variable que se llame paso3

Paso 4

  • El paso 3 acumulaba, por cada ciudad, temperatura mínima, máxima, suma de las medidas y número de medidas.
  • Por cada entrada hay que dejar mínima y máxima y calcular la media
  • Puedes dejar la lista en una variable paso4

Paso 5

  • Para ordenar la lista te propongo implementar una función de orden superior para ordenar
  • Es de orden superior porque recibe la lista de entrada y una función de comparación (menor o igual)
  • Puedes implementar un merge-sort (necesitarás tres funciones, la función de ordenación en si misma, una para partir una lista en dos, y otra para mezclar dos listas y ordenadas) 
defmodule Ej90 do
  def sort(l, c) do
  
  end
end
  • Pues ya tenemos todo para dejar en una variable paso5 la lista ordenada con los datos del reto

Prueba con 1 millón

  • Sube hasta la celda con las medidas y cambia el fichero a "/data/files/measurements_1mrc.txt"

Soluciones

En esa sección puedes ver algunas soluciones a los ejercicios incluyendo comentarios explicativos. A continuación podrás ver una celda con los tests a esas soluciones.

defmodule Sol do
  def map([], _f) do
    # Aplicar _f a todos los elementos de la lista vacía devuelve la lista vacía
    []
  end
  def map([x | xs], f) do
    # Aplicar f a todos los elementos de la lista cuyo primer elementos es x y
    # el resto es xs es la lista cyyo primer elementos es f aplicado a x y el
    # resto es aplicar map a xs con f
    [f.(x) | map(xs, f)]
  end

  def insert([], y) do
    [y]
  end
  def insert([x | xs], y) do
    [x | insert(xs, y)]
  end

  # Esta versión de reduce procesa la lista de izquierda a derecha
  def reduce_left([], acc, _) do
    acc
  end
  def reduce_left([x | xs], acc, f) do
    reduce_left(xs, f.(acc,x), f)
  end

  # Esta versión de reduce procesa la lista de derecha a izquierda
  def reduce_right([], acc, _) do
    acc
  end
  def reduce_right([x | xs], acc, f) do
    f.(reduce_right(xs, acc, f), x)
  end

  # Funciones del diccionario
  def get(dict, key) do
    case dict do
      [] -> :error
      [{^key, value} | _] -> {:ok, value}
      [_ | es ] -> get(es, key)
    end
  end

  def put(dict, key, value) do
    case dict do
      [] -> [{key, value}]
      [{^key, _} | es] -> [{key, value} | es]
      [e | es ] -> [e | put(es, key, value)]
    end
  end

  def update(dict, key, f) do
    case dict do
      [] -> []
      [{^key, v} | es] -> [{key, f.(v)} | es]
      [e | es ] -> [e | update(es, key, f)]
    end
  end
end

ExUnit.start(auto_run: false)

defmodule TestSol do
  use ExUnit.Case, async: true

  test "map works" do
    sum1 = fn x -> x + 1 end
    assert Sol.map([], sum1) == []
    assert Sol.map([1], sum1) == [2]
    assert Sol.map([2,3,4,5], sum1) == [3,4,5,6]
  end

  test "insert works" do
    assert Sol.insert([], 42) == [42]
    assert Sol.insert([1,2,3,4], 42) == [1,2,3,4,42]
  end
end

ExUnit.run()
Back