List comprehensions y generadores: Haskell y Python para principiantes

Un feature que siempre me gustó de Python son las list comprehensions (o listas por comprensión) y los generadores. En este post voy a escribir un texto que me hubiera gustado encontrar un tiempo atrás cuando por primera vez me topé con estas maravillas.

Una lista por comprensión es una forma de obtener una lista de manera "descriptiva", por ejemplo la lista de las primeras 10 potencias de 2:

[1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024]

Podría obtenerse como:

[2**n for n in range(0,11)]

Que se pdoría leer como: "2 elevado a la n, para n en el rango de 0 a 11". En este caso range() es un generador de números.

Qué significa que sea un generador? simplemente que retorna un iterador y a medida que se le pidan cosas las va a ir produciendo (existe otra función que hace esto mismo con mejoras en el consumo de memoria, llamada xrange(), pero no me voy a poner a explicarlo acá).

Entonces podríamos por ejemplo, querer hacer un generador que me devuelva los números de la secuencia de fibonacci (nunca le encontré el sentido a usar esta secuencia, salvo para jugar, que es lo que estamos haciendo...). Entonces veamos un poco qué herramientas nos provee python (algunas) para hacer generadores.

El siguiente código va contando. Hasta cuando? por siempre, me devuelve un número atrás del otro siempre que yo le pida:

def contar():
  x = 0
  while True:
   yield x
   x = x + 1

El operador yield alcanza para crear un generador. Lo que hace es devolver el control al caller de la función generadora. Al volver a llamarse el generador, retoma la ejecución desde la línea siguiente al yield, haciendo lo que queremos y no devolviendo siempre 0, o colgarse (por el while True).

En una consola de python, podemos probarlo:

>>> a = contar()
>>> a.next()
0
>>> a.next()
1
>>> a.next()
2
>>> a.next()
3
>>> a.next()
4

Lo mismo hacemos ahora, pero para generar la venerada secuencia (notar que los dos primeros están aparte pues son los casos base de la definición recursiva de la secuencia)

def fib():
  i = 0 
  first = 0 
  yield first
  second = 1  
  yield second
  while True:
    next = first + second 
    first = second
    second = next
    yield next

Ahora bien, todo muy lindo pero de donde vienen estas bondades como las listas por comprensión y los generadores? Bueno, las listas por comprensión al menos, fue un feature que Python "tomó prestado" de otro lenguaje... Haskell, del paradigma funcional.

Cómo hacemos esto mismo que acabamos de hacer en Python en Haskell? Empecemos por las listas por comprensión:

Main> [2^n| n<-[0..10]]
[1,2,4,8,16,32,64,128,256,512,1024]

Que "leído" sería: "Los dos-a-la-N que vienen de tomar n de la lista de 0 a 10", como Haskell habla mas que nada, el lenguaje de los matemáticos, no tiene problemas similares al range(n,m) de python, que va de n a (m-1)...

Sigamos. Qué notan de raro en la línea en haskell? Un generador!, en realidad dos! Por qué?

Main> [0..10]
[0,1,2,3,4,5,6,7,8,9,10]

Genera la secuencia de 0 a 10. Mientras que n <-[0..10]
en el contexto de la lista por comprensión, va "tomando" n's de la lista.

Algo importante para decir, es que los generadores dentro de las listas por comprensión, tanto en Python como en Haskell pueden anidarse, prueben estos códigos en Python y Haskell respectivamente:

Main> [ (x,y)| x<-[0..5], y<-[11..15] ]

[(x,y) for x in range(0,6) for y in range(11,16)]

Dan lo mismo!

Una prueba de velocidad

Ya es suficiente como para que el que este leyendo esto siga investigando por su cuenta las bondades de los generadores y las listas por comprensión tanto en Python como en Haskell, al final del post hay algunos links.
Pero me quedé jugando, y probé algunas cosas... por ejemplo. Fíjense estas definiciones de funciones que hay para ir tomando los números de fibonacci en Haskell:

fibo 0 = 0
fibo 1 = 1
fibo n = fib (n-1) + fib (n-2)


fib :: Int -> Integer
fib n = fibs !! n
  where
    fibs = 0 : 1 : zipWith (+) fibs (tail fibs)

fibo es la versión recursiva, LENTA que me va dando los números de la lista. Cada vez que quiere calcular el n-ésimo número, tiene que calcular los (n-1) y (n-2)-ésimos, y para calcular cada uno de estos seguir hacia atrás, por lo que el orden de este algoritmo es exponencial.
En cambio fib es una versión que hace uso de una SUPER bondad de los lenguajes funcionales que son los folds, funciones de alto orden (les recomiendo leer este último link!). Esta implementación tiene orden lineal, o sea, que la podemos poner a competir con la versión que habíamos armado para python y que la competencia sea mas justa... hagamoslo!

Los competidores:

fib :: Int -> Integer
fib n = fibs !! n
  where
    fibs = 0 : 1 : zipWith (+) fibs (tail fibs)

VS.

def fib():
  i = 0 
  first = 0 
  yield first
  second = 1  
  yield second
  while True:
    next = first + second 
    first = second
    second = next
    yield next

Los invito a que lo prueben... En el próximo post mis resultados...

Espero que este post les haya dejado algo!

Links:
Este link es en la doc de python una comparación con Haskell.
http://www.haskell.org/haskellwiki/List_comprehension
http://www.haskell.org/haskellwiki/Fold
http://www.zvon.org/other/haskell/Outputprelude/zipWith_f.html
http://docs.python.org/tutorial/datastructures.html#list-comprehensions
http://docs.python.org/tutorial/classes.html#generators