http://blog.comunidadhaskell.org/pg/blog/carliros/read/107/estructuras-d
En esta oportunidad quiero compartir una traduccion de una de los subtitulos del libro: Purely Functional Data Structure [Chris Okasaki], que me parecio muy buena.
Estructuras de Datos Funcionales vs. Imperativas
Los beneficios metodologicos de los lenguajes funcionales son bien conocidos, pero aun la mayoria de los programas son escritos en lenguajes imperativos como C. Esta aparente contradiccion es facilmente explicado por el hecho de que los lenguajes funcionales han sido historicamente mas lentos que sus mas tradicionales primos, pero esta brecha se esta reduciendo. Se han hecho impresionantes avances desde un amplio frente, desde tecnologias basicas de compiladores a analisis sofisticados y optimizaciones. Sin embargo, hay un aspecto de la programacion funcional que todo escritor de compiladores debe mitigar - el uso de estructuras de datos inapropiadas o inferiores.
Porque las estructuras de datos funcionales son mas dificultuosas para diseñar e implementar que las imperativas? Hay 2 problemas basicos. Primero, desde el punto de vista de diseño e implementacion de estructuras de datos eficientes, la estructura de la programacion funcional contra actualizaciones destructivas (ej. asignaciones) es una desventaja asombrosa, equivalente a confiscar los cuchillos de un chef master. Al igual que los cuchillos, las actualizaciones destructivas pueden ser dañinas cuando son mal usadas, pero tremendamente efectivas cuando son usadas apropiadamente. Las estructuras de datos imperativas a menudo confian en la asignacion de una forma crucial, y por eso se encuentran diferentes soluciones para los programas funcionales.
La segunda dificultad es que se espera que las estructuras de datos funcionales sean mas flexibles que sus contrapartes imperativas. En particular, cuando actualizamos una estructura de datos imperativa, tipicamente aceptamos que la version antigua de la estructura de datos ya no estara disponible, pero cuando actualizamos una estructura de datos funcional, esperamos que la antigua y nueva version de la estructura de datos estara disponible para futuros procesamientos. Una estructura de datos que soporta multiples versiones es llamado persistente [persistent], mientras que una estrutura de datos que permite solo una simple version en un tiempo es llamado efimera [ephemeral]. Los lenguajes de programacion funcional tienen la propiedad curiosa de que todas las estructuras de datos son auntomaticamente persistentes.
Las estructuras de datos imperativas son tipicamente efimeras, pero cuando una estructura de datos persistente es requerida, los programadores imperativos no se sorprenden si la estructura de datos persistente es mas complicada y talves incluso asintoticamente menos eficiente que una equivalente estructura de datos efimera.
Ademas, los teoricos han establecido limites inferiores sugeriendo que los lenguajes de programacion funcional podrian ser fundamentalmente menos eficientes que los lenguajes imperativos en algunas situaciones. En vista de todos estos puntos, las estructuras de datos funcionales se parecen algunas veces al oso que baila, de quien se dice, "lo maravilloso no es que el danza muy bien, sino de que el danza de alguna manera!". En la practica, sin embargo, la situacion no es tan triste. Como podremos ver, es a menudo posible eleborar estructuras de datos funcionales que son asintoticamente tan eficientes como las mejores soluciones imperativas.
