Estructuras de Datos Funcionales vs. Imperativas
February 9, 2010 por Carlos Gomez
Comentarios (0)
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.
Setters and Getters en Haskell
August 6, 2009 por Carlos Gomez
Comentarios (2)
Nota.- Para su mejor comprencion he hecho varios cambios aqui, uno de ellos es el nombre del contructor de datos, de Persona a Per.
Ahora, Como definimos los setters y getters de una estructura de datos Persona?
Responderemos a esta pregunta, en el resto de este blog, asi nuestra estructura de datos es Persona con los datos de ci, nombre, apellido y edad.
data Persona = Per CI Name LastName Edad
deriving Show
type CI = Int
type Name = String
type LastName = String
type Edad = Int
Esto define una funcion constructora de datos de tipo:
Per ::CI -> Name -> LastName -> Edad -> Persona
Veamos algunos ejemplos:
p1 :: Persona
p1 = Per 1212 "Juan" "Block" 35p2 :: Persona
p2 = Persona 2323 "Pedro" "Ramos" 25
Ahora definamos algunas funciones set y get para Persona
setCI :: Persona -> CI -> Persona
setCI (Persona ci nm ap ed) ci' = Per ci' nm ap ed
setNombre :: Persona -> Name -> Persona
setNombre (Persona ci nm ap ed) nm' = Per ci nm' ap edsetApellido :: Persona -> LastName -> Persona
setApellido (Persona ci nm ap ed) ap' = Per ci nm ap' edsetEdad :: Persona -> Edad -> Persona
setEdad (Persona ci nm ap ed) ed' = Per ci nm ap ed'
getCI :: Persona -> CI
getCI (Persona ci _ _ _) = cigetNombre :: Persona -> Name
getNombre (Persona _ nm _ _) = nmgetApellido :: Persona -> LastName
getApellido (Persona _ _ ap _) = apgetEdad :: Persona -> Edad
getEdad (Persona _ _ _ ed) = ed
Si hacemos algunas pruebas obtenemos:
gt;*Main> getCI p1
nos retornaria el CI de 'Juan', tambien podemos obtener nombre, apellido o edad.
Para setear un valor, podemos hacer
*Main> p1 {nombre = "juanes"}
Persona {ci = 1212, nombre = "juanes", apellido = "Block", edad = 35}
Y listo, mision cumplida, aunque un poco tedioso.
Bueno, esto no termina aqui, resulta que Haskell provee una forma diferente de definir los datatypes, esto es nombrando los elementos de cada constructor de datos. Llamado tambien records de Haskell.
Veamos como nos ayuda esto, en nuestra definicion de setters y getters, y como cambia a lo anterior ya hecho.
data Persona = Per { ci :: CI
, nombre :: Name
, apellido :: LastName
, edad :: Edad
} deriving Show
type CI = Int
type Name = String
type LastName = String
type Edad = Int
Bueno, eso es todo lo que tenemos que hacer, hagamos algunas pruebas para ver algo de teoria.
p3 = Per 2525 "Teo" "Flores" 43 -- creamos un instancia
* Main> ci p3
2525
* Main> p3{nombre = "Maria"}
Persona {ci = 2525, nombre = "Maria", apellido = "Flores", edad = 43}
Como veras, hicimos las operaciones de set y get.
Algo de teoria, el nombramiento de campos en los datatypes no afecta al anterior version, por ejemplo el tipo contructor de datos es el mismo. Pero hay funcionalidades que se aumentan. Entre ellos tenemos la seleccion de campos usando labels, construccion usando labels y actualizacion de campos usando labels.
La seleccion de campos usando labels, es practicamente la operacion seter de un objeto. Y lo que Haskell hace es definir una funcion con el nombre del label, el cual esta disponible para su uso. Ejemplo "ci p3".
Tambien podemos contruir instancias usando labels (p4 = Per {edad=12, ci=3434, apellido="Perez", nombre="Pedro"} ), y no solo de la forma comun (p4 = Per 3434 12 "Pedro" "Perez"). Intensionalmente he cambiado las posiciones de los labels, pues esto no afecta. Se debe cuidar de que ningun label se repita mas de una ves, pero si no especificamos algun label, este deberia inicializar como indefinido o infito (GHC lo muestra como un warning).
Para la actualizacion de campos usando labels, se tiene una sintaxis: instancia_obj {label=value, ...}, asi como en el ejemplo p3{ci=3454}. Otra ves, no se debe mencionar mas de una ves una label, y los labels deben pertenecer al tipo contructor.
Al actualizar un valor de la instancia, se genera una nueva instancia modificando asi en la nueva instancia los valores enviados. Es una caracteristica de Persistencia de Haskell. Veamos un ejemplo:
*Main> p1 {edad = 0}
Persona {ci = 1212, nombre = "Juan", apellido = "Block", edad = 0}
*Main> p1
Persona {ci = 1212, nombre = "Juan", apellido = "Block", edad = 35}
Tambien podemos mesclar los distintos contructores de datos con esta sintxis o sin ella. Y respecto a los nombres de los labels, podemos repetirlas entre las funciones contructoras de datos, siempre y cuando se tenga un tipo consistente, pero no podemos repetirnas entre los datatypes, porque generaria una incosistencia de tipos. Veamos un ejemplo sacado del reporte de Haskell 98:
data S = S1 {x :: Int}
| S2 {x :: Int} -- ejemplo buenodata T = T1 {y :: Int}
| T2 {y :: Bool} -- ejemplo malo, tipo inconsistente
En conclusion, esta forma de creacion de datatypes, añade funcionalidad y sintaxis extra para manipular los elementos del datatype.
Algo interesante seria averiguar como definir mucha mas similitud de funcionalidad a OOP. Me refiero a definir solo funciones set o get para algunos elementos, o declarar elementos como publicos, protegidos o privados.
Hay otras extenciones de GHC que nos facilitan la manipulacion de records en Haskell. Pero los que hemos visto aqui pertenece al Haskell 98.
Cabal (Common Architecture for Building Applications and Libraries)
July 29, 2009 por Carlos Gomez
Comentarios (2)
Hoy revizaremos una forma de instalar Cabal, una herramienta muy comoda para instalar y construir aplicaciones y librerias de haskell.
Para una informacion mas detallada puedes ver Biliotecas adicionales con Cabal.
Pero hagamos lo nuestro:
La forma que abordaremos es instalar cabal atraves de un bootstrap, el cual se encargara de descargar las fuentes, configurarlas e instalarlas.
Antes de continuar debemos preveer que disponemos de 3 cosas basicas (Doy por supuesto que tienen instalado ghc 8 o superior):
Nota.- Los siguientes comandos son para un sis ope basado en Debian (esto incluye a ubuntu).
1.- parsec library of ghc.
Si no tienes instalado, puedes instalarlo con:
apt-get install libghc6-parsec-dev libghc6-parsec-doc
2.- network library of ghc.
Si no tienes instalado, puedes instalarlo con:
apt-get install libghc6-network-dev libghc6-network-doc libghc6-network-prof
3.- zlib.h header of C.
Podemos encontrar el header zlib.h en la libreria zlib1g-dev.
Comandos para instalarlo:
apt-get install zlib1g-dev
Despues de preever las anteriores cosas podemos descargar el Cabal Install Tool de la pagina http:/
Descargar Cabal Install Tool 0.6.2.tar.gz, y ejecutamos el bootstrap.sh
Ejecutando ./bootstrap.sh se descargara las fuentes de cabal de la web, luego se configuran y finalmente se instalaran en tu sistema (Debes notar que necesitaras una coneccion a internet cuando estes ejecutando el bootstrap).
Ahora que ya esta instalado cabal, debemos publicar el comando cabal ubicado en /root_or_user_/.cabal/bin. Podriamos crear un enlace a este comando en /usr/bin con
ln -s /root/.cabal/cabal cabal
Antes de usarlo debemos actualizar la lista de paquetes con
cabal update
Ahora podremos disfrutar de Cabal, e instalar otras aplicaciones.
IRC Channel Haskell
June 19, 2009 por Carlos Gomez
Comentarios (0)
Navegando por la Web encontre un Canal IRC.
No sabia que existia un lugar online en donde se puede chatear con otros haskelleros.
Segun ellos, este IRC puede ser usado para aprender mas acerca de haskell, enterarse de nuevas cosas de haskell, porque muchas nuevas cosas primero dice que aparecen en el irc.
Bueno, no quise esperar mucho para unirme.
Para unirte puedes usar cualquier chat que te permita unirte al irc, en lo particular yo use irssi, pero puedes usar pidgin u otro.
apt-get install irssi
luego, > irssi -c chat.freenode.net -n tunickname
puedes usar cualquier nick que no este repetido actualmente, pero si despues dela primera ves quieres mantenerte con ese nick deberas registrarte, como ?, puedes ver frenode-register
una ves adentro seleccionar el salon al que quieres ingresar, en nuestro caso
/join #haskell
y listo, a chatear con los cuates.
Para mas informacion puedes ver este enlace irc-haskell, en el cual encontraras otros salones de chat relacionados a haskell.
|