jueves, 10 de septiembre de 2009

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

sábado, 5 de septiembre de 2009

Se fue Pycon Argentina 2009

Hoy terminó Pycon 2009, la verdad es que nos llevo mucho tiempo prepararla y superó las expectativas en todos los sentidos (asistentes, salió todo perfecto, no se robaron nada... :D). Las charlas estuvieron muy buenas y variadas y la gente parece haberla disfrutado mucho.

En cuanto estén los slides de las charlas comento las que pude ver. Ahora me voy a dormir, que no doy mas.

martes, 2 de junio de 2009

Pycon Argentina Call for Charlas (CFCh)

Se agradece la difusión. y espero verlos a todos ahi! (quienquiera que lea este blog!)
----

Call For Charlas (CFCh)
PyCon Argentina - http://ar.pycon.org/
Primera Conferencia Argentina de Python
Buenos Aires - 4 y 5 de Septiembre de 2009'''


PyAr, el grupo de usuarios de Python de Argentina invita a toda la comunidad de usuarios de Python y de Software Libre en general a proponer presentaciones y charlas para la Primera Conferencia Argentina de Python.

En este evento nos juntaremos desarrolladores y programadores tanto principiantes como avanzados; bloggers, autores y diseñadores web; gerentes, administradores y emprendedores; científicos, ingenieros, curiosos y todo aquel que tenga ganas de acercarse a la comunidad Python en Argentina.

El autor de cada charla seleccionada podrá participar presencialmente, como orador en el evento. En los casos en que la charla sea realizada por varios autores, se permitirá un máximo de 3 oradores.

Aclaración: Por cuestiones presupuestarias, sólo se podrán financiar los pasajes, total o parcialmente, de algunos autores seleccionados que residan fuera de Capital Federal o Gran Buenos Aires. Por favor aclarar junto a la propuesta de charla si se solicita ayuda económica.

Agradecemos la contribución de todos en la difusión de este llamado y del evento en si mediante los banners diseñados para tal fin y que se encuentran en http://ar.pycon.org/2009/helping/publicize/

Dónde enviar las Charlas
Las charlas deben ser ingresadas para su aprobación en
http://ar.pycon.org/2009/conference/proposals/submit/
La fecha límite de envío de charlas es el Lunes 29 de Junio inclusive.
En caso de consultas o inconvenientes, contactarse con charlas[.--arroba-- .]python.org.ar

Cómo enviar las Charlas
El envío de la propuesta de charla debe tener los siguientes datos:

  • Título:

  • Autor(es): Nombre y apellido, breve descripción de cada uno, foto, asociación, grupo de usuarios, organismo, o empresa a la que pertenece, si corresponde.

  • Tiempo estimado de duración: Las charlas generalmente son de 45'. En caso de que sea mayor o menor el tiempo requerido solicitamos su justificación.

  • Breve descripción de la charla: Uno o dos párrafo(s) que explique -no tan brevemente- el contenido de la presentación.

  • Nivel objetivo de la charla: introductorio / intermedio / avanzado

  • Tipo de publico: Desarrolladores avanzados, desarrolladores principiantes, empresarios, docentes, público en general

  • Conocimientos previos: Especificar que conocimientos previos deberán tener los asistentes.

  • Tags: web, gui, databases, frameworks, orm, ide, ciencia, educación, juegos, comunidad, etc.

  • Teléfono del/los autor/es: Para poder comunicarnos.

  • Ciudad de residencia del/los autor/es.




Qué formato deben tener las Presentaciones
El envío de las diapositivas y/o presentaciones debe tener alguno de los siguientes formatos:

  • Openoffice.org presentation

  • HTML standard

  • Postscript o PDF

  • Texto plano



Licencia
Debe especificarse una licencia que permita que !PyAr distribuya el material en un CD de Documentación y que permita ser descargado del sitio web de !PyAr. Se recomienda Creative Commons o similares.