Bitácora

Séptima clase

funcionallistas-infinitaslazy-evaluationsimulacro

17 de Mayo, 2020

¿Qué vimos hoy?

Listas infinitas

Ya vimos que en Haskell podemos modelar una biblioteca 📚 con las listas, por ejemplo: 

biblioteca = [elVisitante, shingekiNoKyojin1, fundacion, sandman5, brisignr, legado]

Y también podemos modelar una lista del 1 al 5:

unoAlCinco = [1,2,3,4,5]

Pero si quisiéramos hacer una lista del 1 al 1000… ¡¿deberíamos escribir mil veces los números?! 😱 Por suerte, nuestro gran amigo Haskell puede ayudarnos gracias a las listas por rangos:

unoAlMil = [1..1000]

También podemos definir una lista de los números pares entre 1 y 100 de esta forma:

paresAlCien = [2,4..100]

Y no solo sirve para números 🔢, sino también para letras 🔡: 

abecedario = ['a'..'z']

Y así como podemos definir listas con límites o con rangos, también podemos tener… 🥁 ¡listas infinitas!

infinita = [1..]

(¿Lo probaste en la consola y te olvidaste qué hacer para que pare? 😰 Apretá ctrl + c. 😉)

Lazy evaluation

Sabemos aplicar la función ´head´ a una lista:

head ["hola", "como", "estás?"]
> "hola"

Pero, ¿qué pasará con una lista infinita? 😮 

head [1..]
> 1

Por si quedan dudas de qué es lo que acaba de pasar, Haskell no esperó a que terminara la lista sino que tomó directamente lo que necesitaba. Eso es porque su forma de trabajo es la evaluación perezosa o lazy evaluation. Esto no pasa con todos los lenguajes. Otros (que seguramente ya utilizaste) usan la evaluación ansiosa o eager evaluation en donde, por ejemplo, esperarían a que la lista termine de cargar (infinitamente nunca 😵) para devolver el primer elemento. Sipi, Haskell es lo más. 😍

Ahora, ¿cómo funciona lazy evaluation? Este tipo de evaluación se basa en una estrategia que se llama call-by-name… ¿eeehhh? 😨 Simplemente es operar primero las funciones de por fuera, antes que las funciones de sus parámetros. Es decir, las funciones se aplican antes de que se evalúen los parámetros. 😎 Si volvemos al ejemplo anterior:

head [1..]
-- aplicará primero head, antes que evaluar la lista infinita
> 1

Pero también hay funciones en las cuales necesitamos evaluar primero los parámetros, antes que la función en sí:

(*) (2+3) 5
(2+3) * 5 

-- (*) necesita que sus parámetros sean números para poder evaluar, entonces se evalúa primero (2+3).

5 * 5
> 25

Evaluar primero los parámetros para luego pasarle el valor final a las funciones, lo llamamos call-by-value. Y es la estrategia en la que se basa la eager evaluation. Veamos:

head [1..]
-- espera a que termine la lista infinita (nunca 😝)
head [1,2..]
-- espera a que termine la lista infinita (nunca 😝)
head [1,2,3..]
-- espera a que termine la lista infinita (nunca 😝)
head [1,2,3,4..]
-- ... y así hasta el infinito de los tiempos ⏳. ¡No termina!

Vimos los siguientes casos teniendo en cuenta estas preguntas:

  • ¿terminarán de evaluar con lazy evaluation?
  • ¿y con eager evaluation?
  • ¿qué nos devuelve? 🤔
take 15 [1,3..]
-- Sí termina con lazy. No terminaría con eager. Devuelve [1,3,5,7,9,11,13,15,17,19,21,23,25,27,29]

last [1..]
-- No termina con lazy y tampoco con eager.

length [1..]
-- No termina con lazy y tampoco con eager.

sum [3, 6..3*10]
-- Termina con ambas y devuelve 165.

any even [2, 4..]
-- Termina con lazy pero no con eager. Devuelve True.

all even [2, 4..]
-- No termina

all odd [2, 4..]
-- Devuelve False

head (filter (3<) [1..])
-- Termina con lazy pero no con eager. Devuelve 4.

head (filter (<0) [1..])
-- No termina con lazy y tampoco con eager.

map (*2) [1..]
-- No termina pero devuelve [2, 4, 6…]

fst ("Hola", [1..])
-- Devuelve "Hola". No terminaría de evaluarse con eager.

fst (3, 7/0)
-- Devuelve 3. Con eager rompería porque no se puede dividir por 0.

fst("Hola", head [])
-- Devuelve "Hola". Con eager porque no se puede hacer head de la lista infinita.

snd ([1, "Hola"], 2)
-- Rompe porque las listas deben ser homogéneas.

Parcial de práctica: Tierra de bárbaros y una posible solución.

Podes ver nuestro github acá.

Y saber mas sobre nosotros acá