Una lista infinita que sí se puede usar
La evaluación perezosa es la forma en que Haskell calcula un valor solo cuando alguien lo necesita. Gracias a ella puedes definir una lista infinita, como todos los números naturales, y usar solo los primeros.
Así se escriben programas que parecen pedir un trabajo imposible y acaban en un instante.
Al final de esta lección
Nota
Puedo escribir una función recursiva y explicar por qué una lista infinita se puede usar.
Palabras clave
| Palabra | Qué significa | Ejemplo |
|---|---|---|
| Recursión | una función que se llama a sí misma | |
| Caso base | el caso más simple, que no vuelve a llamar | |
| Evaluación perezosa | calcular un valor solo cuando se necesita | |
| Lista infinita | una lista sin final, de la que se toman unos pocos | [1 ..] |
| Generador | en Python, una función con yield que da un valor cada vez |
Las celdas que rellenan los estudiantes quedan en blanco en esta vista previa.
Una función recursiva se llama a sí misma
En Haskell no se escriben bucles: se escribe recursión. La función resuelve un caso muy simple, el caso base, y para el resto se llama a sí misma con un dato más pequeño.
El factorial de 5 es 5 por el factorial de 4. El factorial de 0 es 1 y es el caso base, el que para la cadena.
Dos funciones recursivas
-- El caso base va primero: la lista vacía suma 0.
addAll :: [Int] -> Int
addAll [] = 0
addAll (x : rest) = x + addAll rest
-- Una cuenta atrás. Con 0 se para.
countDown :: Int -> [Int]
countDown 0 = []
countDown n = n : countDown (n - 1)
Lee la función recursiva del laboratorio
docker exec haskell cat Fold.hsSe muestra aquí y no se ejecuta. Crea una cuenta gratuita para pulsar Ejecutar y escribirlo en el terminal de tu propio laboratorio.
Ejecuta el archivo de la recursión
docker exec haskell runghc Fold.hsSe muestra aquí y no se ejecuta. Crea una cuenta gratuita para pulsar Ejecutar y escribirlo en el terminal de tu propio laboratorio.
Define el factorial y calcula el de 5
docker exec haskell ghc -e "let fact n = if n == 0 then 1 else n * fact (n - 1) in fact 5"Se muestra aquí y no se ejecuta. Crea una cuenta gratuita para pulsar Ejecutar y escribirlo en el terminal de tu propio laboratorio.
Una cuenta atrás desde 4
docker exec haskell ghc -e "let count n = if n == 0 then [] else n : count (n - 1) in count 4"Se muestra aquí y no se ejecuta. Crea una cuenta gratuita para pulsar Ejecutar y escribirlo en el terminal de tu propio laboratorio.
Ejemplo: cómo se calcula el factorial de 3
| Llamada | Se convierte en | Cuando termina vale |
|---|---|---|
| fact 3 | 3 por fact 2 | 6 |
| fact 2 | 2 por fact 1 | 2 |
| fact 1 | 1 por fact 0 | 1 |
| fact 0 | Caso base | 1 |
Las celdas que rellenan los estudiantes quedan en blanco en esta vista previa.
Haskell calcula solo lo que se necesita
En la evaluación perezosa, un valor no se calcula hasta que otra parte del programa lo necesita. Por eso [1 ..], la lista infinita de los naturales, no llena la memoria.
take 5 [1 ..] pide solo cinco elementos, y solo se calculan cinco. Lo demás nunca existe. Los Runs siguientes encadenan funciones sobre una lista infinita.
Los cinco primeros números naturales
docker exec haskell ghc -e "take 5 [1 ..]"Se muestra aquí y no se ejecuta. Crea una cuenta gratuita para pulsar Ejecutar y escribirlo en el terminal de tu propio laboratorio.
Dobla una lista infinita y toma cinco
docker exec haskell ghc -e "take 5 (map (* 2) [1 ..])"Se muestra aquí y no se ejecuta. Crea una cuenta gratuita para pulsar Ejecutar y escribirlo en el terminal de tu propio laboratorio.
Cuadrados pares hasta que pasen de 40
docker exec haskell ghc -e "takeWhile (< 40) (filter even (map (^ 2) [1 ..]))"Se muestra aquí y no se ejecuta. Crea una cuenta gratuita para pulsar Ejecutar y escribirlo en el terminal de tu propio laboratorio.
Los tres primeros cuadrados mayores de 1000
docker exec haskell ghc -e "take 3 (filter (> 1000) (map (^ 2) [1 ..]))"Se muestra aquí y no se ejecuta. Crea una cuenta gratuita para pulsar Ejecutar y escribirlo en el terminal de tu propio laboratorio.
Una lista que se define con ella misma
docker exec haskell ghc -e "let ones = 1 : ones in take 3 ones"Se muestra aquí y no se ejecuta. Crea una cuenta gratuita para pulsar Ejecutar y escribirlo en el terminal de tu propio laboratorio.
Un error frecuente
Advertencia
Mucha gente cree que una lista infinita bloquea el programa. Solo lo bloquea si pides toda la lista, por ejemplo sumarla entera. Si pides unos pocos elementos con take, acaba al instante. Pedir pocos elementos es seguro; pedirlos todos no termina.
En Python, un generador también es perezoso
Python no es perezoso por defecto, pero un generador sí lo es. Es una función con yield: entrega un valor y se queda esperando a que le pidan el siguiente.
count_from(1) puede ser infinita porque nunca se calcula entera. next(stream) pide un valor, y solo uno.
Pide los números de uno en uno
# Un generador entrega un valor solo cuando se lo piden.
def count_from(start):
n = start
while True:
yield n
n = n + 1
stream = count_from(1)
print(next(stream))
print(next(stream))
print(next(stream))
# Añade dos líneas más con print(next(stream)) y vuelve a ejecutar.
Para ir más lejos
Los generadores de Python se pueden encadenar como las listas de Haskell. map_stream(f, filter_stream(test, stream)) filtra primero y transforma después, sin calcular nada de más.
Piensa en una consulta que lee un archivo de un millón de líneas pero solo necesita las diez primeras que coinciden. Explica qué parte del trabajo se ahorra.