Es/Guía de Haskell para autoestopistas
Aviso: Esta página está en proceso de traducción.
Preámbulo: ¡NO CORRER!
Experiencias recientes de algunos compañeros programadores de C++/Java indican que leyeron varios tutoriales sobre Haskell con "velocidad exponencial" (piensa en como las sesiones de TCP/IP aumentan). Al principio son pocas y prudentes, pero cuando ven que las primeras 3-5 páginas no contienen "nada interesante" en términos de código y ejemplos, empiezan a saltarse párrafos, después capítulos, después páginas enteras, tan sólo decelerando - a menudo hasta parar completamente - alrededor de la página 50, encontrándose con el grueso de conceptos como "clases de tipos", "constructores de tipos", "IO monádica", punto en el que normalmente les entra el pánico, piensan en una excusa perfectamente racional para no seguir leyendo, y se olvida alegremente de este triste y escalofriante encuentro con Haskell (ya que los seres humanos tendemos a olvidar las cosas tristes y escalofriantes).
Este texto pretende introducir al lector a los aspectos prácticos de Haskell desde el principio del todo (los planes para el primer capítulo incluyen: I/O, darcs, Parsec, QuickCheck, depurar y perfilar, por mencionar algunos). Se supone que el lector sabe (donde encontrar) por lo menos los primeros pasos de Haskell: como ejecutar "hugs” o “ghci", ese diseño es 2-dimensional, etc. Aparte de eso, no esperamos avanzar radicalmente, e iremos paso por paso para no perder a los lectores por el camino. Así que NO CORRER, coge la toalla contigo y continúa leyendo.
Si te has saltado el párrafo anterior, me gustaría destacar una vez más que Haskell es sensible al sangrado y espaciado, así que presta atención cuando hagas copias o alineación manual de código en el editor de texto con fuentes proporcionales.
Ah, casi me olvido: el autor está muy interesado en CUALQUIER opinión. Escríbele algunas líneas o palabras (mira Adept para la información de contacto) o propón cambios al tutorial mediante darcs (el repositorio está aquí) o directamente a este Wiki.
Capítulo 1: Omnipresente “¡Hola mundo!” y otras formas de hacer IO en Haskell
Cada capítulo será dedicado a una pequeña tarea real que completaremos desde el principio.
Así que aquí está la tarea para este capítulo: para liberar espacio en tu disco duro para todo el código de haskell que vas a escribir en un futuro cercano, vas a guardar algo de la vieja y polvorienta información en CDs y DVDs. Mientras que grabar CDs (o DVDs) es fácil hoy en día, normalmente ocupa algo (o mucho) tiempo decidir como grabar algunos GB de fotos digitales en CD-Rs, cuando los directorios con las imágenes varían desde 10 a 300 Mb de espacio, y no quieres grabar CDs medio llenos (o medio vacíos).
El ejercicio consiste en escribir un programa que nos ayude a poner un conjunto de directorios en la cantidad mínima posible de discos, al mismo tiempo que aprovechamos cada disco lo máximo posible. Llamemos a este programa “cd-fit”.
Oh. Espera. Hagamos el usual programa “hola mundo”, antes de que nos olvidemos, y después sigamos con cosas más interesantes:
-- Cogido de 'hola.hs'
-- A partir de ahora, un comentario al principio del trozo de código
-- especificará el archivo que contiene el programa entero del que fue cogido
-- el trozo. Puedes coger el código del repositorio de darcs
-- "http://adept.linux.kiev.ua/repos/hhgtth" introduciendo el comando
-- "darcs get http://adept.linux.kiev.ua/repos/hhgtth"
module Main where
main = putStrLn "¡Hola mundo!"
Ejecútalo:
$ runhaskell ./hola.hs ¡Hola mundo!
Vale, ya lo hicimos. Sigamos ahora, no hay nada interesante aquí :)
Cualquier desarrollo serio se debe hacer con un sistema de control de versiones, y no haremos una excepción. Usaremos el moderno sistema de control de versiones distribuido “darcs”. “Moderno” significa que está escrito en Haskell, “distribuido” significa que cada copia que funcione es un repositorio en si mismo.
Primero, creemos un directorio vacío para nuestro todo nuestro código, y ejecuta “darcs init” en él, que creará un subdirectorio “_darcs” para guardar todo lo relacionado con el control de versiones dentro de él.
Inicia tu editor favorito y crea un fichero nuevo llamado “cd-fits.hs” en nuestro directorio de trabajo. Ahora pensemos por un momento como funcionará nuestro programa y expresémoslo en pseudocódigo:
main = Leer lista de directorio y sus tamaños.
Decidir como ajustarlos a los CD-Rs.
Imprimir la solución.
¿Parece lógico? Creo que si.
Vamos a simplificar nuestra vida un poco y asumir por ahora que vamos calcular el espacio de los directorios de alguna forma fuera de nuestro programa (por ejemplo, con “du -sb *”) y leer esa información desde stdin. Convirtamos esto a Haskell:
-- Cogido de 'cd-fit-1-1.hs'
module Main where
main = do input <- getContents
putStrLn ("DEBUG: tengo entrada" ++ input)
-- calcular solución e imprimirla
No funciona en realidad, pero bastante parecido al español, ¿no? Paremos por un momento y miremos más de cerca qué hemos escrito línea por línea.
Empecemos desde arriba:
-- Cogido de 'cd-fit-1-1.hs'
input <- getContents
Esto es un ejemplo de la sintaxis de Haskell para hacer IO (en este caso, entrada de datos). Esta línea es una instrucción para leer toda la información disponible desde stdin, devolverla como una única cadena, y asociarla al símbolo “input”, de forma que podamos procesar esta cadena de la forma que queramos.
¿Cómo lo sabía? ¿Memoricé todas las funciones? ¡Claro que no! Cada función tiene un tipo, que junto con su nombre, tiende a decir mucho sobre lo que hace la función.
Lanza un entorno interactivo de Haskell y examinemos esta función de cerca:
$ ghci ___ ___ _ / _ \ /\ /\/ __(_) / /_\// /_/ / / | | GHC Interactive, version 6.4.1, for Haskell 98. / /_\\/ __ / /___| | http://www.haskell.org/ghc/ \____/\/ /_/\____/|_| Type :? for help. Loading package base-1.0 ... linking ... done. Prelude> :type getContents getContents :: IO String Prelude>
Vemos que “getContents” es una función sin argumentos, que devuelve un “IO String”. El prefijo “IO” significa que es una acción de IO. Devolverá un String, cuando se evalue. La acción será evaluada cuando usemos “<-” para enlazar su resultado a un símbolo.
Ten en cuenta que “<-” no es una forma bonita de asignar un valor a una variable. Es una forma de evaluar (ejecutar) acciones de IO, en otras palabras - para hacer alguna operación de I/O y devolver su resultado (si es que tiene).
Podemos escoger no evaluar la acción que obtenemos de “getContents”, y en vez de eso dejarla por ahí y evaluarla más tarde:
let x = getContents
-- 300 líneas de código
input <- x
Como puedes ver, las acciones de IO pueden ser usadas como valores ordinarios. Supón que hemos construído una lista de acciones IO y hemos encontrado una forma de ejecutarlas una por una. Sería una forma de simular programación imperativa con su notación de “orden de ejecución”.
Haskell te permite hacerlo mejor.
La librería estandard del lenguaje (llamada “Prelude”) nos da acceso a muchas funciones que devuelven primitivas de acciones de IO muy útiles. Para combinarlas entre ellas para producir acciones más complejas, usamos “do”:
c = do a <- algunaAcción
b <- algunaOtraAcción
print (bar b)
print (foo a)
putStrLn "hecho"
De esta forma asociamos “c” a una acción con el siguiente “escenario”:
- evalua la acción “algunaAcción” y asocia su resultado a “a”
- después, evalua “algunaOtraAcción” y asocia su resultado a “b”
- después, procesa “b” con la función “bar” e imprime su resultado
- después, procesa “a” con la función “foo” e imprime su resultado
- después, imprime la palabra “hecho”
¿Cuándo se ejecutará todo esto en realidad? Respuesta: tan rápido como evaluemos “c” usando “<-” (si devuelve un resultado, como hace “getContents”) o usándola como el nombre de una función (si no devuelve un resultado, como hace “print”):
process = do putStrLn "Procesará algo"
c
putStrLn "Hecho"
Date cuenta de que hemos cogido unas cuantas funciones (“algunaAcción”, “algunaOtraAcción”, “print”, “putStrLn”) y usando “do” creamos a partir de ellas una nueva función, que enlazamos al símbolo “c”. Ahora podemos usar “c” como una pieza de construcción para construir una función más compleja “proceso”, y podríamos continuar haciéndolo más y más. Finalmente, algunas de las funciones las mencionaremos en el código de la función “main”, función a la cual la última y más importante acción de IO en cualquier programa de Haskell está asociada.
¿Cuándo se ejececutará/evaluará/forzará “main”? Tan rápido como ejecutemos el programa. Lee esto dos veces y trata de comprenderlo:
La ejecución de un programa de Haskell es una evaluación del símbolo “main” a la que hemos asociado una acción de IO. Mediante esta evaluación obtenemos el resultado de la acción.
Los lectores que estén familiriazados con programación en C++ o Java avanzado y ese conjunto de conocimiento arcano llamado “OOP Patrones de Diseño” se darán cuenta de que “construir acciones a partir de acciones” y “evaluar acciones para obtener resultados” es esencialmente un “Patrón de comando” y “Patrón de composición” combinados. Buenas noticias: en Haskell las tienes para todo tu IO, y lo tienes gratis :)
Ejercicio: Fíjate en el siguiente código:
-- Cogido de 'exercise-1-1.hs'
module Main where
c = putStrLn "C!"
combine before after =
do before
putStrLn "En el medio"
after
main = do combine c c
let b = combine (putStrLn "¡Hola!") (putStrLn "¡Adios!")
let d = combine (b) (combine c c)
putStrLn "¡Tanto tiempo!"
¿Te das cuenta de como sangramos las líneas con cuidado para que el código parezca limpio? En realidad, el código de Haskell tiene que estar alineado de esta forma, o si no, no compilará. Si usas tabulados para sangrar tu código fuente, ten en cuenta que los compiladores de Haskell asumen que el tabstop tiene de ancho 8 caracteres.
A menudo las personas se quejan de que es una forma muy difícil de escribir en Haskell porque requiere que alinées el código. En realidad no es verdad. Si alineas tu código, el compilador adivinará cuál es el principio y final de los bloques sintácticos. Sin embargo, si no sangras tu código, puedes especificarlos explícitamente en cada una de las expresiones y usar una distribución arbitraria como en este ejemplo:
-- Cogido de 'exercise-1-2.hs'
combine before after =
do { before;
putStrLn "En el medio";
after; };
main =
do { combine c c; let { b = combine (putStrLn "¡Hola!") (putStrLn "¡Adios!")};
let {d = combine (b) (combine c c)};
putStrLn "¡Tanto tiempo!" };
De vuelta al ejercicio - ¿Ves cómo hacemos código desde la nada? Trata de imaginar qué hará este código, después ejecútalo y compruébalo por ti mismo.
¿Entiendes por qué “¡Hola!” y “¡Adiós!” no se imprimen?
Examinemos nuestra función “main” más de cerca:
Prelude> :load cd-fit.hs Compiling Main ( ./cd-fit.hs, interpreted ) Ok, modules loaded: Main. *Main> :type main main :: IO () *Main>
Vemos que “main” es en realidad una acción IO que no devuelve nada cuando la evaluamos. Cuando combinamos acciones con “do”, el tipo del resultado será el tipo de la última acción, y “putStrLn algo” tiene tipo “IO ()”:
*Main> :type putStrLn "¡Hola mundo!" putStrLn "¡Hola mundo!" :: IO () *Main>
Ah, por cierto: ¿Te has dado cuenta que hemos compilado nuestro primer programa de Haskell para examinar “main”? :)
Celebrémoslo poniéndolo bajo control de versión: ejecuta “darcs add cd-fit.hs” y “darcs record”, responder “y” a todas las preguntas y dale un comentario al añadido “Esqueleto de cd-fit.hs”
Vamos a probar a ejecutarlo:
$ echo "foo" | runhaskell cd-fit.hs DEBUG: tengo entrada foo
Ejercicios:
- Trata de escribir un programa que coja tu nombre de stdin y te felicite (palabras clave: getLine, putStrLn);
- Trata de escribir un programa que pregunte por tu nombre, lo lea, te felicite, pregunte por tu color favotiro, y lo devuelva (palabras clave: getLine, putStrLn).
Capítulo 2: procesando la entrada
Bien, ahora que tenemos un entendimiento cabal de los poderes de ES en Haskell (y estamos deslumbrados por ellos, espero), nos olvidemos un poco de ES y hagamos algún trabajo útil.
Como tu recordarás, nos habíamos propuesto poner datos tomados de varios directorios en tan pocos discos CD-Rs como sea posible. Asumimos que "du -sb" calculará el tamaño de los directorios de entrada y nos dará como salida algo como lo siguiente:
65572 /home/adept/photos/raw-to-burn/dir1 68268 /home/adept/photos/raw-to-burn/dir2 53372 /home/adept/photos/raw-to-burn/dir3 713124 /home/adept/photos/raw-to-burn/dir4 437952 /home/adept/photos/raw-to-burn/dir5
Nuestra siguiente tarea es procesar esa entrada y convertirla en alguna representación interna más cómoda.
Para ello usaremos la poderosa librería de combinadores de parsers llamada "Parsec", que está presente en la mayoría de las implementaciones de Haskell.
Como muchas de las facilidades para ES que hemos visto en el capítulo anterior, esta libreria provee un conjunto de parsers básicos y medios de combinarlos para obtener construcciones de parseo más complejas.
A diferencia de otras herramientas en esta área (lex/yacc o JavaCC, para nombrar algunas), los parsers de Parsec no requieren una etapa de prepocesamiento previo. Dado que en Haskell podemos devolver funciones como resultado de funciones y de esta manera, construir funciones a partir de "mero aire", no hay necesidad de una sintáxis separada para la descripción de parsers. Pero ya hicimos suficiente propaganda, hagamos algún parseo:
-- Tomado de 'cd-fit-2-1.hs'
import Text.ParserCombinators.Parsec
-- parseInput parsea la entrada de "du -sb", que consiste de muchas líneas,
-- cada una de ellas describe un solo directorio
parseInput =
do dirs <- many dirAndSize
eof :: Parser ()
return dirs
-- El tipo de dato Dir tiene información sobre un solo directorio:
-- su tamaño y su nombre
data Dir = Dir Int String deriving Show
-- `dirAndSize` parsea la información de un solo directorio, que es:
-- un tamaño en bytes (número), algunos espacios, y luego el nombre del
-- directorio que llega hasta el fin de la línea
dirAndSize =
do size <- many1 digit
spaces
dir_name <- anyChar `manyTill` newline
return (Dir (read size) dir_name)
Simplemente agrega esas líneas al inicio de "cd-fit.hs". Aquí vemos muchas cosas nuevas, y muchas que ya conocíamos.
Primero que nada, notemos la conocida construcción "do", que, como sabemos, se usa para combinar acciones de ES para producir nuevas acciones de ES. Aquí la usamos para combinar acciones de "parseo" en nuevas acciones de "parseo". Significa eso que "parseo" implica "hacer ES"? Absolutamente no. Es decir, tengo que admitir que te mentí - "do" no sólo se usa para combinar acciones de ES. "do" se usa para combinar cualquier tipo de las así llamadas acciones monádicas o valores monádicos.
Piensa en las mónadas como un "patrón de diseño" en el mundo funcional. Las mónadas son una forma de ocultar al usuario (programador) toda la maquinaria necesaria para que operen funcionalidades complejas.
Como habrás oido, Haskell no tiene ninguna noción de "assignación", "estado mutable" ni "variables", y es un "lenguaje funcional puro", que significa que toda función invocada con los mismos parámetros devolverá exactamente los mismos resultados. A la vez, "hacer ES" requiere acarrear descriptores de ficheros y sus estados y lidiar con errores de ES. El "parseo" requiere llevar registro de la posición en la entrada y lidiar con errores de parseo.
En ambos casos Hombres Sabios que Escribieron Librerías tomaron las precauciones por nosotros y nos ocultaron toda la complejidad, exponiendo la API de sus librerías (ES y parseo) en la forma de "acciones monádicas", que nosotros podemos combinar libremente como nos parezca.
Piensa en la programación con mónadas como hacer un remodelamiento con ayuda de un grupo de profesionales de remodelamiento. Tu describes secuencias de acciones en el papel (eso somos nosotros escribiendo con la notación "do"), y después, cuando es necesario, esa secuencia será evaluada por los profesionales ("en la mónada") lo que te dará el resultado final, ocultandote toda la complejidad subyacente (cómo preparar la pintuea, qué clavos elegir, etc).
Usemos el entorno interactivo de Haskell para descifrar todas las instrucciones que hemos escritos para la librería de parseo. Como es usual, iremos de arriba hacia abajo:
*Main> :reload Ok, modules loaded: Main. *Main> :t parseInput parseInput :: GenParser Char st [Dir] *Main> :t dirAndSize dirAndSize :: GenParser Char st Dir *Main>
Asumiendo (bueno, confía en mi palabra) que "GenParser Char st" es
nuestra mónada de parseo, podríamos ver que "parseInput", cuando sea
evaluada, producirá una lista de "Dir", y que "dirAndSize", cuando sea
evaluada, producirá "Dir". Asumiendo que "Dir" representa de alguna
forma la iformación sobre un solo directorio, es casi lo que queríamos,
o no?
Veamos que significa un "Dir". Nosotros hemos definido el tipo de datos Dir como un registro, que contiene un Int y un String:
-- Taken from 'cd-fit-2-1.hs'
data Dir = Dir Int String deriving Show
Para construir esos registros, debemos usar el constructor de datos Dir:
*Main> :t Dir 1 "foo" Dir 1 "foo" :: Dir
Para evitar la confusión para los novatos, podriamos haber escrito:
data Dir = D Int String deriving Show
, que define el tipo de datos "Dir" con el constructor de datos "D". Sin embargo, tradicionalmente el nombre del tipo de datos y de su constructor son el mismo.
La cláusula "deriving Show" le ordena al compilador hacer "tras bambalinas" todo el código necesario para que este tipo de datos cumpla con la interfaz de la clase de tipo Show. Explicaremos clases de tipo más adelante, por ahora digamos que esto nos permitirá "imprimir" instancias de "Dir".
Ejercicios:
- examina los tipos de "digit", "anyChar", "many", "many1" y "manyTill" para ver como són usados para construir parser complejos a partir de parsers simples.
- compara los tipos de "manyTill", "manyTill anyChar" y "manyTill anyChar newline". Nota que "anyChar `manyTill` newline" es simplemente azucar sintácticto para el anterior. Nota que cuando no le aplicamos todos los argumentos necesarios a una función, entonces no obtenemos un valor, sino una nueva función, esto se llama aplicación parcial.
Bien, hasta aquí combinamos varias acciones primitivas de "parseo" para obtener nosotros un parser para la salida de "du -sb". Ahora, cómo podemos parsear algo? La librería Parsec nos brinda la función "parse":
*Main> :t parse parse :: GenParser tok () a -> SourceName -> [tok] -> Either ParseError a *Main> :t parse parseInput parse parseInput :: SourceName -> [Char] -> Either ParseError [Dir] *Main>
Al principio el tipo puede parecer un poco críptico, pero una vez que aplicamos el parser que nosotros hicimos, el compilador tiene más información y nos muestra un tipo más particular.
Detente aquí y considera lo siguiente por un momento: el compilador se dió cuenta del tipo sin que nosotros hayamos hecho una sola anotación de tipos! Imagínate si un compilador de Java dedujera los tipos por nosotros, y no tuvieramos que especificar los tipos de los argumentos y de los valores de retorno nunca.
Ahora volvamos al código. Podemos observar que "parser" es una función, que cuando recibe un parser, un nombre de un fichero o un canal (p.e. "stdin") y datos de entrada (String, que es una lista de "Char"s, que se escribe "[Char]"), producirá o bien un error de "parseo" o una lista de "Dir".
El tipo de datos "Either" es un ejemplo de un tipo de datos cuyo constructor tiene un nombre diferente del nombre del tipo de datos. De hecho, "Either" tiene dos constructores:
data either a b = Left a | Right b
Para entender mejor qué significa, considera el siguiente ejemplo:
*Main> :t Left 'a' Left 'a' :: Either Char b *Main> :t Right "aaa" Right "aaa" :: Either a [Char] *Main>
Puedes ver que "Either" es una unión disjunta (bastante parecida a la "union" en C/C++), que puede tener un valor de uno de los dos tipos de datos. Sin embargo, a diferencia de la "union" en C/C++, si tuvieramos un valor de tipo "Either Int Char" podríamos decir inmediatamente si es un Int o un Char - mirando el constructor usado para producir el valor. Estos tipo de datos se llaman "uniones disjuntas" y son una herramienta poderosa de la caja de herramientas de Haskell.
¿Has notado que le hemos dado a "parse" un parser que es un valor monádico, pero no hemos recibido un nuevo valor monádico, sino un resultado de "parseo"? Esto es así porque "parse" es un evaludador para la mónada "Parser", así como el runtime de GHC o el de Hugs es un evaluador para la mónada de E/S. La función "parser" implementa toda la maquinaria monádica: tiene un registro de los errores y posiciones en la entrada, implementa backtracking y lookahead, etc.
Extendamos nuestr función "main" para que use "parse", parseé realmente
la entrada y nos muestra las estructuras parseadas:
-- Taken from 'cd-fit-2-1.hs'
main = do input <- getContents
putStrLn ("DEBUG: got input " ++ input)
let dirs = case parse parseInput "stdin" input of
Left err -> error $ "Input:\n" ++ show input ++
"\nError:\n" ++ show err
Right result -> result
putStrLn "DEBUG: parsed:"; print dirs
Ejercicios:
- Para entender mejor el siguiente pedazo de cógigo, examina (con ghci
o hugs) las diferencias entre 'drop 1 ( drop 1 ( drop 1 ( drop 1 ( drop 1 "foobar" ))))' y 'drop 1 $ drop 1 $ drop 1 $ drop 1 $ drop 1 "foobar"'. Examina el tipo de ($).
- Intenta hacer 'putStrLn "aaa"' y 'print "aaa"' y mira la la diferencia, examina sus tipos.
- Intenta 'print (Dir 1 "foo")' y 'putStrLn (Dir 1 "foo")'. Examina los tipos de print y de putStrLn para entender el comportamiento en cada caso.
Intentemos ejecutar lo que tenemos hasta aquí:
$ du -sb * | runhaskell ./cd-fit.hs DEBUG: got input 22325 Article.txt 18928 Article.txt~ 1706 cd-fit.hs 964 cd-fit.hs~ 61609 _darcs DEBUG: parsed: [Dir 22325 "Article.txt",Dir 18928 "Article.txt~",Dir 1706 "cd-fit.hs",Dir 964 "cd-fit.hs~",Dir 61609 "_darcs"]
Parece que está haciendo exactamente lo planeado. Ahora probemos con alguna entrada errónea:
$ echo "foo" | runhaskell cd-fit.hs DEBUG: got input foo DEBUG: parsed: *** Exception: Input: "foo\n" Error: "stdin" (line 1, column 1): unexpected "f" expecting digit or end of input
Parece que se comporta bien.
Si tú has seguido el consejo de poner tu código bajo control de versiones, tú puedes usar "darcs whatsnew" o "darc diff -u" para examinar los cambios respecto a la versión anterior. Usando "darcs record" creas una nueva versión con los cambios. Como ejercicio, primero registra los cambios que no están dentro de la función "main" y luego registra los que están en "main". Usa "darcs changes" para examinar una lista de los cambios registrados hasta ahora.
Capítulo 3: Empacando la mochila y controlándola con clase también (¡y no te olvides tu toalla!)
Ya tuvimos bastante preámbulo. Hagamos algunos CDs.
Como debes haberte dado cuenta, nuestro problema es clásico. Se llama el "problema de la mochila" (búscalo en google, si no lo conoces. Hay más de un millón de resultados.)
Empecemos con la solución voraz, pero primero modifiquemos levemente nuestro tipo de datos "Dir" para facilitar la extracción de sus componentes:
-- Taken from 'cd-fit-3-1.hs'
data Dir = Dir {dir_size::Int, dir_name::String} deriving Show
Ejercicio: examina los tipos de "Dir", "dir_size" y "dir_name".
A partir de ahora, podríamos usar "dir_size d" para obtener un tamaño de directorio y "dir_name d" para obtener su nombre, si "d" es de tipo "Dir".
El algoritmo voraz ordena los directorios de mayor a menor e intenta ponerlos en el CD uno a uno, hasta que no haya más espacio. Vamos a tener que llevar registro de los directorios que agregamos al CD, para ello agreguemos otro tipo de datos y programemos este simple algoritmo de empaque:
-- Taken from 'cd-fit-3-1.hs'
import Data.List (sortBy)
-- DirPack holds a set of directories which are to be stored on single CD.
-- 'pack_size' could be calculated, but we will store it separately to reduce
-- amount of calculation
data DirPack = DirPack {pack_size::Int, dirs::[Dir]} deriving Show
-- For simplicity, let's assume that we deal with standard 700 Mb CDs for now
media_size = 700*1024*1024
-- Greedy packer tries to add directories one by one to initially empty 'DirPack'
greedy_pack dirs = foldl maybe_add_dir (DirPack 0 []) $ sortBy cmpSize dirs
where
cmpSize d1 d2 = compare (dir_size d1) (dir_size d2)
-- Helper function, which only adds directory "d" to the pack "p" when new
-- total size does not exceed media_size
maybe_add_dir p d =
let new_size = pack_size p + dir_size d
new_dirs = d:(dirs p)
in if new_size > media_size then p else DirPack new_size new_dirs
Yo resaltaré las áreas que podrías explorar vos mismo (usando otros tutoriales bonitos, especialmente te recomiento "Yet Another Haskell Tutorial" ("Otro tutorial para Haskell") por Hal Daume):
- Elegimos importar una sola función "sortBy" de un módulo Data.List, no el módulo entero.
- En vez de programar caso por caso la definición recursiva de "greedy_pack", usamos un enfoque de alto orden, y elegimos "foldl" como una forma para recorrido de listas. Examina su tipo. Otras funciones útiles de esa categoría son "map", "foldr", "scanl" y "scanr". Búscalas!
- Para ordenar una lista de "Dir" por tamaño usamos una función particular de orden con el ordenamiento parametrizable - "sortBy". Este tipo de funciones donde uno provee un modificador particular para una función de librería genérica es bastante común: busca "deleteBy", "deleteFirstBy", "groupBy", "insertBy", "intersectBy", "maximumBy", "minimumBy", "sortBy", "unionBy".
- Para programar la compleja función "maybe_add_dir" hemos introducido definiciones locales con la cláusula "let"; estas definiciones pueden ser usadas nuevamente en el cuerpo de la función. Usamos una cláusula "where" en la función "greedy_pack" para lo mismo. Lee acerca de las cláusulas "let" y "where" y sobre las diferencias entre ellas.
- Nota que para poder construir un nuevo valor de tipo "DirPack" (en la función "maybe_add_dir") no hemos usado las funciones auxiliares "pack_size" y "dirs".
Para poder utilizar nuestro empacador voraz debemos invocarlo desde nuestra función "main", así que agreguemos algunas líneas:
-- Taken from 'cd-fit-3-1.hs'
main = do ...
-- compute solution and print it
putStrLn "Solution:" ; print (greedy_pack dirs)
Verifica la integridad de las definiciones (re)cargando el código en ghci. ¿Compila? Claro que sí :) Ahora, haz "darcs record" y agrega algún mensaje razonable para documentar los cambios.
Es el momento de probar nuestra creación. Podemos hacerlo ejecutando directamente de la siguiente forma:
$ du -sb ~/DOWNLOADS/* | runhaskell ./cd-fit.hs
Esto demostrará que nuestro código parece funcionar. Por lo menos esta vez. ¿Qué tal estaría establecer con algún grado de certeza que nuestro código funciona correctamente, parcial y completamente, y hacerlo de una forma re-usable? ¿En otras palabras, qué tal si escribimos algunas pruebas?
Los programadores de Java, acostumbrados a JUnit, probablemente pensaron en pantallas y pantallas de plantillas e invocaciones de métodos escritas a mano. No temáis, no haremos nada tan tonto :)
Presentando QuickCheck.
QuickCheck es una herramienta que hace pruebas automatizadas de tus funciones utilizando datos de entrada (semi) aleatorios. Siguiendo la idea de "100b de ejemplos de código valen lo que 1k de elogios" mostremos el código para verificar la siguiente "propiedad": un intento de empacar directorios devueltos por "greedy_pack" debe regresar "DirPack" de exactamente el mismo paquete.
-- Taken from 'cd-fit-3-2.hs'
import Test.QuickCheck
import Control.Monad (liftM2, replicateM)
-- We must teach QuickCheck how to generate arbitrary "Dir"s
instance Arbitrary Dir where
-- Let's just skip "coarbitrary" for now, ok?
-- I promise, we will get back to it later :)
coarbitrary = undefined
-- We generate arbitrary "Dir" by generating random size and random name
-- and stuffing them inside "Dir"
arbitrary = liftM2 Dir gen_size gen_name
-- Generate random size between 10 and 1400 Mb
where gen_size = do s <- choose (10,1400)
return (s*1024*1024)
-- Generate random name 1 to 300 chars long, consisting of symbols "fubar/"
gen_name = do n <- choose (1,300)
replicateM (n*10+1) (elements "fubar/")
-- For convenience and by tradition, all QuickCheck tests begin with prefix "prop_".
-- Assume that "ds" will be a random list of "Dir"s and code your test.
prop_greedy_pack_is_fixpoint ds =
let pack = greedy_pack ds
in pack_size pack == pack_size (greedy_pack (dirs pack))
ejecutemos la prueba, tras lo cual explicaré cómo funciona:
Prelude> :r Compiling Main ( ./cd-fit.hs, interpreted ) Ok, modules loaded: Main. *Main> quickCheck prop_greedy_pack_is_fixpoint [numbers spinning] OK, passed 100 tests. *Main>
Hemos visto que nuestro "greedy_pack" corre en 100 listas completamente (bueno, casi completamente) aleatorias de "Dir"s, y parece que esa propiedad efectivamente se cumple.
Disequemos el código. La parte más intrigante es "instance Arbitrary Dir where", que declara que "Dir" es una instancia (instance) de typeclass) "Arbitrary". Whoa, ¡es un montón de palabras desconocidas! :) Veamos con más calma.
¿Qué es una clase de tipos (typeclass)? Una clase de tipos es la forma de Haskell de lidiar con la siguiente situación: supón que estás escribiendo una biblioteca de funciones útiles y no sabes por anticipado exactamente cómo van a ser utilizadas, así que quieres hacerlas genéricas. Por un lado no quieres restringir a tus usuarios a cierto tipo (e.g. String). Por otro lado, quieres que se cumpla que los argumentos para tu función deban satisfacer un cierto conjunto de restricciones. Aquí es donde typeclass es útil.
Piensa en typeclass como en un contrato (o "interface", en términos Java) que el tipo debe cumplir para ser aceptado como argumento a ciertas funciones.
Examinemos la clase de tipos "Arbitrary":
*Main> :i Arbitrary class Arbitrary a where arbitrary :: Gen a coarbitrary :: a -> Gen b -> Gen b -- Imported from Test.QuickCheck instance Arbitrary Dir -- Defined at ./cd-fit.hs:61:0 instance Arbitrary Bool -- Imported from Test.QuickCheck instance Arbitrary Double -- Imported from Test.QuickCheck instance Arbitrary Float -- Imported from Test.QuickCheck instance Arbitrary Int -- Imported from Test.QuickCheck instance Arbitrary Integer -- Imported from Test.QuickCheck -- rest skipped --
Se puede leer así: "Cualquier tipo (llamémosle 'a') puede ser miembro de la clase Arbitrary siempre que le definamos dos funciones: "arbitrary" y "coarbitrary", con las definiciones de tipos mostradas. Para los tipos Dir, Bool, Double, Float, Int e Integer exiten tales definiciones, por lo tanto, todos esos tipos son instancia de la clase Arbitrary".
¡Ahora, si escribes una función que opere en sus argumentos solamente por medio de "arbitrary" y "coarbitrary", puedes estar seguro de que esa función funcionará en cualquier tipo que sea instancia de "Arbitrary"!
Vamos a decirlo otra vez. Alguien (tal vez tú mismo) escribe código (API o biblioteca) que requiere que los valores de entrada implementen ciertas "interfaces" que están descritas en términos de funciones. Una vez que muestras cómo implementa tu tipo esta "interfaz", eres libre de emplear el API o las bibliotecas.
Considera la función "sort" ("ordenar") de la biblioteca estándar:
*Main> :t Data.List.sort Data.List.sort :: (Ord a) => [a] -> [a]
Vemos que ordena listas de valores cualesquiera que sean instancia de la clase de tipos "Ord". Examinemos esa clase:
*Main> :i Ord class Eq a => Ord a where compare :: a -> a -> Ordering (<) :: a -> a -> Bool (>=) :: a -> a -> Bool (>) :: a -> a -> Bool (<=) :: a -> a -> Bool max :: a -> a -> a min :: a -> a -> a -- skip instance Ord Double -- Imported from GHC.Float instance Ord Float -- Imported from GHC.Float instance Ord Bool -- Imported from GHC.Base instance Ord Char -- Imported from GHC.Base instance Ord Integer -- Imported from GHC.Num instance Ord Int -- Imported from GHC.Base -- skip *Main>
Vemos un par de cosas interesantes: primero, hay un requisito adicional: para que sea instancia de "Ord", el tipo debe primero ser una instancia de la clase de tipos "Eq". Luego, vemos que hay una gran cantidad de funciones que deben ser definidas para ser una instancia de "Ord". Un momento, ¿no es algo tonto tener que definir (<) y (>) cuando se puede expresar uno en términos del otro?
¡Claro que sí! Usualmente, las clases de tipo contienen varias implementaciones por "default" para sus funciones, cuando es posible expresarlas una a través de otra (como es el caso de "Ord"). En este caso es posible proveer solamente una definición mínima (que, en el caso de "Ord", consiste en cualquier función de comparación) y las demás serán automáticamente derivadas. Si provees menos funciones de las que se requieren para una implementación mínima, el compilador/intérprete lo indicará y explicará qué funciones faltan por definir.
Una vez más, vemos que muchos de los tipos son ya instancia de la clase de tipos Ord, y por eso es posible ordenarlos.
Veamos de nuevo la definición de "Dir":
-- Taken from 'cd-fit-3-2.hs'
data Dir = Dir {dir_size::Int, dir_name::String} deriving Show
¿Notas la presencia de la cláusula deriving? Esto le dice al compilador que derive automáticamente código para hacer que "Dir" sea una instancia de la clase de tipos Show. El compilador conoce unas cuantas clases de tipos estándar (Eq, Ord, Show, Enum, Bound, Typeable para mencionar algunas) y sabe cómo convertir un tipo en una instancia "suficientemente buena" de cualquiera de ellas. Si quieres derivar instancias de más de una clase de tipos, dilo de esta forma: "deriving (Eq,Ord,Show)". Voila! Ahora podemos comparar, ordenar e imprimir datos de ese tipo.
Un comentario para programadores Java: imaginen un compilador java que derive automáticamente código para "implements Storable"...
Un comentario para programadores C++: imaginen que los constructores de copia son escritos por el compilador...
Exercises:
- Examine typeclasses Eq and Show
- Examine types of (==) and "print"
- Try to make "Dir" instance of "Eq"
Ok, de regreso a las pruebas. Así que, ¿qué hemos tenido que hacer para que "Dir" sea instancia de "Arbitrary"? La definición mínima consiste en "arbitrary". Examinémosla de cerca:
*Main> :t arbitrary arbitrary :: (Arbitrary a) => Gen a
¿Notas ese "Gen a"? ¿Te recuerda algo? ¡Correcto! Piensa en "IO a" y "Parser a", que ya hemos visto. Este es otro ejemplo más de función que regresa acciones, que cuede ser utilizada dentro de la notación "do". (Puedes preguntarte, ¿no sería útil generalizar ese concepto tan conveniente de acciones y "do"? ¡Por supuesto! Ya está hecho, el concepto se llama "Monad" y lo mencionaremos en el capítulo 400 :) )
Como aquí 'a' es una variable de tipo que es una instancia de "Arbitrary", podemos sustituirla con "Dir". Así que, ¿cómo creamos y regresamos una acción de tipo "Gen Dir"?
Veamos el código:
-- Taken from 'cd-fit-3-2.hs'
arbitrary = liftM2 Dir gen_size gen_name
-- Generate random size between 10 and 1400 Mb
where gen_size = do s <- choose (10,1400)
return (s*1024*1024)
-- Generate random name 1 to 300 chars long, consisting of symbols "fubar/"
gen_name = do n <- choose (1,300)
replicateM (n*10+1) (elements "fubar/")
Hemos empleado las funciones de biblioteca "choose" y "elements" para construir "gen_size :: Gen Int" y "gen_name :: Gen String" (ejercicio: no me creas. Busca una forma de verificar los tipos de "gen_name" y "gen_size"). Como "Int" y "String" son los componentes de "Dir", seguramente debemos poder usar "Gen Int" y "Gen String" para construir "Gen Dir". ¿Pero donde está el bloque "do" para esto? No hay ninguno; solamente hay una sola llamada a "liftM2".
Examinémoslo:
*Main> :t liftM2 liftM2 :: (Monad m) => (a1 -> a2 -> r) -> m a1 -> m a2 -> m r
¿Espanta, no? Démosle al verificador de tipos un poco de contexto:
*Main> :t liftM2 Dir liftM2 Dir :: (Monad m) => m Int -> m String -> m Dir
Como ya has oído que "Gen" es una "Monad", puedes sustituir "Gen" en lugar de "m" aquí, obteniendo "liftM2 Dir :: (Monad Gen) => Gen Int -> Gen String -> Gen Dir". ¡Exactamente lo que queríamos!
Considera que "liftM2" es un "tópico avanzado" de este capítulo (lo veremos después) y por ahora nota que:
- "2" es un número de argumentos para el constructor de datos "Dir" y hemos utilizado "liftM2" para construir "Gen Dir" a partir de "Dir"
- También hay "liftM", "liftM3", "liftM4", "liftM5"
- "liftM2" está definido como "liftM2 f a1 a2 = do x<-a1; y<-a2; return (f x y)"
Esperemos que todo esto tenga sentido tras leerlo por tercera vez ;)
Ah, y de paso - ¡no olvides hacer "darcs record" para guardar tus cambios!
Capítulo 4: Empacando DE VERDAD la mochila, ahora sí
En este capítulo vamos a escribir otro método de empaque no tan trivial, comparar la eficiencia de los métodos de empaque y, de paso, aprender cosas nuevas sobre depuración y medición de desempeño de programas en Haskell.
Puede no ser inmediatamente obvio si nuestro algoritmo de empaque es eficiente, y, si lo es, ¿en qué forma en particular? ¿Cuánto tarda en completar, cuanta memoria consume, el resultado obtenido es de suficiente calidad? ¿Hay otros algoritmos, y cómo se comparan uno al otro?
Escribamos otra solución al problema de empacar la mochila, llamado el "método de programación dinámico", y pongamos ambas variantes a prueba.
Esta vez no separaré el listado para explicarlo parte por parte. En lugar de ello he incluído comentarios en el código:
-- Taken from 'cd-fit-4-1.hs'
----------------------------------------------------------------------------------
-- Solución por programación dinámica al problema de empacar
-- una mochila (o más bien un disco)
--
-- Sea `bestDisk x' el disco "más compactamente empacado" de
-- tamaño total no mayor a `x'.
precomputeDisksFor :: [Dir] -> [DirPack]
precomputeDisksFor dirs =
-- Calculando `bestDisk' para todos los posibles tamaños de un
-- disco podemos obtener una solución para un caso en particular
-- simplemente buscando en la lista de soluciones :)
let precomp = map bestDisk [0..]
-- ¿Cómo calcular `bestDisk'? Optemos por una definición recursiva:
-- Caso base de la recursión: el disco de tamaño 0
-- mejor empacado es el vacío
bestDisk 0 = DirPack 0 []
-- Paso recursivo: para el tamaño `limit', mayor que 0, el disco mejor
-- empacado se calcula de la siguiente forma:
bestDisk limit =
-- 1. Toma todos los directorios no vacíos que pudieran posiblemente caber
-- en ese disco por sí mismos. Considéralos uno por uno. Que el tamaño de
-- un directorio en particular sea `dir_size d'. Agreguémoslo al disco mejor
-- empacado de tamaño <= (limit - dir_size d), produciendo el disco de
-- tamaño <= limit. Hagamos esto para todos los directorios "candidato" que
-- aún no están en nuestro disco:
case [ DirPack (dir_size d + s) (d:ds) | d <- filter ( (inRange (1,limit)).dir_size ) dirs
, dir_size d > 0
, let (DirPack s ds)=precomp!!(limit - dir_size d)
, d `notElem` ds
] of
-- O no podemos agregar ningún directorio (probablemente porque todos
-- son demasiado grandes); bueno, informemos que el disco se debe
-- quedar vacío:
[] -> DirPack 0 []
-- O generemos otro empaque diferente. Seleccionemos el mejor de todos:
packs -> maximumBy cmpSize packs
cmpSize a b = compare (pack_size a) (pack_size b)
in precomp
-- Cuando precalculamos discos de todos los posibles tamaños para el conjunto de
-- directorios dado, la solución a un problema en particular es simple: sólo toma la
-- solución para el 'media_size' requerido, y eso es todo.
dynamic_pack dirs = (precomputeDisksFor dirs) !! media_size
Nota que se usó casi la misma cantidad de texto para describir el algoritmo y para implementarlo. ¿Bien, no?
Exercises:
- Make all necessary amendments to the previously written code to make this example compile. Hints: browse modules Data.List and Data.Ix for functions that are "missing" - maybe you will find them there (use ":browse Module.Name" at ghci prompt). Have you had to define some new instances of some classes? How did you do that?
- [ other_function local_binding | x <- some_list, x > 0, let local_binding = some_function x ] is called a "list comprehension". This is another example of "syntactic sugar", which could lead to nicely readable code, but, when abused, could lead to syntactic caries :) Do you understand what does this sample do: let solve x = [ y | x <- [0..], y<-[0..], y == x * x ]? Could write (with help of decent tutorial) write de-sugared version of this? (Yes, I know that finding a square root does not require list traversals, but for the sake of self-education try and do it)
- Notice that in order to code quite complex implementation of precomputeDisksFor we split it up in several smaller pieces and put them as a local bindings inside let clause.
- Notice that we use pattern matching to both define bestKnap on case-by-case basis and to "peer into" (de-construct) DirPack in the let (DirPack s ds)=precomp!!(limit - dir_size d) line
- Notice how we use function composition to compose complex condition to filter the list of dirs
Antes de avanzar más, hagamos un pequeño cambio cosmético en nuestro código. Actualmente nuestra solución utiliza 'Int' para almacenar el tamaño del directorio. En Haskell, 'Int' es un entero dependiente de la plataforma, lo que impone ciertas limitaciones en los valores de este tipo. Intentar calcular valores de tipo 'Int' que excedan los límites resultará en un error de sobreflujo. Las bibliotecas estándar Haskell tienen la clase de tipos especial Bounded, que permite definir y examinar esos límites:
Prelude> :i Bounded class Bounded a where minBound :: a maxBound :: a -- skip -- instance Bounded Int -- Imported from GHC.Enum
Vemos que 'Int' efectivamente tiene límites. Examinemos dichos límites:
Prelude> minBound :: Int -2147483648 Prelude> maxBound :: Int 2147483647 Prelude>
Para los que entienden de C, diremos que en este caso el 'Int' es un "entero de 32 bit con signo", lo que significa que produciremos errores si intentamos operar en paquetes de directorio o directorios que sean mayores a 2 Gb.
Afortunadamente para nosotros, Haskell tiene enteros de precisión arbitraria (limitados solamente por la cantidad de memoria disponible). El tipo apropiado se llama 'Integer':
Prelude> (2^50) :: Int 0 -- overflow Prelude> (2^50) :: Integer 1125899906842624 -- no overflow Prelude>
Cambiemos las definiciones de 'Dir' y de 'DirPack' para permitir directorios de tamaños mayores:
-- Taken from 'cd-fit-4-2.hs'
data Dir = Dir {dir_size::Integer, dir_name::String} deriving (Eq,Show)
data DirPack = DirPack {pack_size::Integer, dirs::[Dir]} deriving Show
Intenta compilar el código o cargarlo en ghci. Obtendrás los siguientes errores:
cd-fit-4-2.hs:73:79:
Couldn't match `Int' against `Integer'
Expected type: Int
Inferred type: Integer
In the expression: limit - (dir_size d)
In the second argument of `(!!)', namely `(limit - (dir_size d))'
cd-fit-4-2.hs:89:47:
Couldn't match `Int' against `Integer'
Expected type: Int
Inferred type: Integer
In the second argument of `(!!)', namely `media_size'
In the definition of `dynamic_pack':
dynamic_pack dirs = (precomputeDisksFor dirs) !! media_size
Parece que Haskell tiene algunos problemas usando 'Integer' con '(!!)'. Veamos por qué:
Prelude> :t (!!) (!!) :: [a] -> Int -> a
Parece que la definición de '(!!)' exige que el índice sea un 'Int', no un 'Integer'. Haskell nunca convierte un tipo en otro automáticamente - el programador debe solicitarlo de forma explícita:
No voy a repetir la sección "Standard Haskell Classes" de
the Haskell Report y explicar por qué los tipos de clases para varios tipos numéricos están organizados como están. Solamente diré que el tipos de clases estándar Num requiere que los tipos numéricos implementen el método fromInteger:
Prelude> :i Num
class (Eq a, Show a) => Num a where
(+) :: a -> a -> a
(*) :: a -> a -> a
(-) :: a -> a -> a
negate :: a -> a
abs :: a -> a
signum :: a -> a
fromInteger :: Integer -> a
-- Imported from GHC.Num
instance Num Float -- Imported from GHC.Float
instance Num Double -- Imported from GHC.Float
instance Num Integer -- Imported from GHC.Num
instance Num Int -- Imported from GHC.Num
Vemos que Integer es miembro de la clase de tipos Num, y por lo tanto podemos utilizar fromInteger para hacer que desaparezcan los errores de tipo:
-- Taken from 'cd-fit-4-2.hs'
-- snip
case [ DirPack (dir_size d + s) (d:ds) | d <- filter ( (inRange (1,limit)).dir_size ) dirs
, dir_size d > 0
, let (DirPack s ds)=precomp!!(fromInteger (limit - dir_size d))
, d `notElem` ds
] of
-- snip
dynamic_pack dirs = (precomputeDisksFor dirs)!!(fromInteger media_size)
-- snip
Los errores de tipo desaparecieron, pero el lector atento se dará cuenta de que cuando la expresión (limit - dir_size d) exceda los límites de Int, ocurrirá un sobreflujo, y no podremos acceder al elemento correcto en la lista. No te preocupes, resolveremos esto en un momento.
Ahora, escribamos la prueba QuickCheck para esta función de la misma forma que la prueba para greedy_pack:
-- Taken from 'cd-fit-4-2.hs'
prop_dynamic_pack_is_fixpoint ds =
let pack = dynamic_pack ds
in pack_size pack == pack_size (dynamic_pack (dirs pack))
Ahora, intentemos ejecutar (¡NO ENTRAR EN PÁNICO y guarda primero lo que estés haciendo en otras aplicaciones!):
*Main> quickCheck prop_dynamic_pack_is_fixpoint
¿Tomaste en serio mi consejo, verdad? ¿Y tenías Ctrl-C listo, no? Lo más probable es que el intento de ejecutar la prueba haya causado que toda tu memoria haya sido saturada por el proceso ghci, que, si fuiste suficientemente rápido, pudiste interrumpir presionando Ctrl-C.
¿Qué sucedió? ¿Quién se comió toda la memoria? ¿Cómo depuramos este problema? GHC puede medir el desempeño y decir donde se ocupó la memoria, pero no podemos hacerlo ahora - el reporte se produce después de que el programa finaliza, y el nuestro no parece querer finalizar sin antes consumir varios terabytes de memoria. Aún así, hay mucho terreno donde maniobrar.
Veamos. Como llamamos a dynamic_pack y se comió toda la memoria, no lo hagamos de nuevo. En lugar de eso, veamos qué hace esa función y alterémosla un poco para modificar su comportamiento.
Como ya sabemos que las listas aleatorias de "Dir"s generadas para nuestras pruebas QuickCheck son de tamaño mediano (después de todo, greedy_pack las mastica sin consumir demasiada memoria), el problema más probablemente no es el tamaño de la entrada. Sin embargo, dynamic_pack_is_fixpoint está construyendo internamente una lista enorme (via precomputeDisksFor). ¿Podría ser ese el problema?
Activemos las estadísticas de medición de tiempo y memoria (":set +s" dentro de ghci) e intentemos espiar dentro de varios elementos de la lista devuelta por precomputeDisksFor:
Prelude> :l cd-fit.hs
Compiling Main ( cd-fit.hs, interpreted )
Ok, modules loaded: Main.
*Main> :set +s
*Main> (precomputeDisksFor [Dir 1 "aaa"]) !! 0
DirPack {pack_size = 0, dirs = []}
(0.06 secs, 1277972 bytes)
*Main> (precomputeDisksFor [Dir 1 "aaa"]) !! 10
DirPack {pack_size = 0, dirs = []}
(0.00 secs, 0 bytes)
*Main> (precomputeDisksFor [Dir 1 "aaa"]) !! 100
DirPack {pack_size = 0, dirs = []}
(0.01 secs, 1519064 bytes)
*Main> (precomputeDisksFor [Dir 1 "aaa"]) !! 1000
DirPack {pack_size = 0, dirs = []}
(0.03 secs, 1081808 bytes)
*Main> (precomputeDisksFor [Dir 1 "aaa"]) !! 10000
DirPack {pack_size = 0, dirs = []}
(1.39 secs, 12714088 bytes)
*Main> (precomputeDisksFor [Dir 1 "aaa"]) !! 100000
Interrupted.
¡Aha! Parece que aquí hay un problema, porque el cálculo de 100000 no finaliza en un tiempo "razonable". Y pensar que hemos tratado de calcular el elemento número 700*1024*1024...
Modifiquemos un poco el código, para permitir alterar el tamaño del disco:
-- Taken from 'cd-fit-4-3.hs'
dynamic_pack limit dirs = (precomputeDisksFor dirs)!!(fromInteger limit)
prop_dynamic_pack_is_fixpoint ds =
let pack = dynamic_pack media_size ds
in pack_size pack == pack_size (dynamic_pack media_size (dirs pack))
prop_dynamic_pack_small_disk ds =
let pack = dynamic_pack 50000 ds
in pack_size pack == pack_size (dynamic_pack 50000 (dirs pack))
-- rename "old" main to "moin"
main = quickCheck prop_dynamic_pack_small_disk
Compila una versión con soporte para medir el desempeño con ghc -O --make -prof -auto-all -o cd-fit cd-fit.hs y ejecútala así:
$ ./cd-fit +RTS -p OK, passed 100 tests.
Primero, notemos que nuestro código satisface al menos una propiedad simple. Bien. Ahora examinemos el reporte de desempeño. Mira en el archivo "cd-fig.prof", que ha sido generado en el directorio actual.
Seguramente vas a ver algo parecido a esto:
cd-fit +RTS -p -RTS
total time = 2.18 secs (109 ticks @ 20 ms)
total alloc = 721,433,008 bytes (excludes profiling overheads)
COST CENTRE MODULE %time %alloc
precomputeDisksFor Main 88.1 99.8
dynamic_pack Main 11.0 0.0
individual inherited
COST CENTRE MODULE no. entries %time %alloc %time %alloc
MAIN MAIN 1 0 0.0 0.0 100.0 100.0
CAF Main 174 11 0.9 0.2 100.0 100.0
prop_dynamic_pack_small_disk Main 181 100 0.0 0.0 99.1 99.8
dynamic_pack Main 182 200 11.0 0.0 99.1 99.8
precomputeDisksFor Main 183 200 88.1 99.8 88.1 99.8
main Main 180 1 0.0 0.0 0.0 0.0
Examina la columna "individual %alloc". Como lo pensamos, toda la memoria ha sido ubicada dentro de precomputeDisksFor. Sin embargo, la cantidad de memoria ubicada (más de 700 Mb, de acuerdo a la línea "total alloc") parece ser demasiado para resolver nuestro problema simple. Investiguemos más profundo para averiguar en donde estamos desperdiciando.
Examinemos el consumo de memoria más de cerca empleando "heap profiles". Ejecuta ./cd-fit +RTS -hb. Eso produce "perfiles de memoria biográficos", que nos dicen cómo fueron utilizadas las varias partes de la memoria durante la ejecución del programa. El perfil ha sido almacenado en "cd-fit.hp". Es casi imposible de leer e interpretar tal como está; emplearemos "hp2ps cd-fit.hp" para producir una imagen en PostScript que vale más que mil palabras. Visualízala con "gv" o "ghostview" o "Adobe Acrobat" completo (no el "Reader"). (Esta y las siguientes imágenes no están incluídas aquí)
Nota que la mayor parte de la gráfica está ocupada por la región marcada "VOID" (vacío). Eso significa que la memoria ubicada nunca fué usada. Nota que no hay áreas marcadas como "USE", "LAG o "DRAG". Parece que nuestro programa no usa casi nada de la memoria que ha reservado. ¡Un momento! ¿Cómo es posible? Tiene que estar usando algo cuando empaca en los discos imaginarios de 50000 bytes esos directorios generados al azar que miden de 10 a 1400 Mb... Oops. Es una enorme diferencia de tamaños. Debimos habernos dado cuenta antes, cuando estábamos midiendo precomputeDisksFor. Regresa y observa cómo es que todas las ejecuciones regresan exactamente el mismo resultado - el conjunto vacío de directorios.
Nuestros directorios al azar son demasiado grandes, pero de todas formas el código consume tiempo y memoria intentando "empacarlos". Obviamente, precomputeDisksFor (que es responsable del 90% del consumo de tiempo y memoria) tiene algún error.
Miremos más de cerca qué consume tanta memoria. Ejecuta ./cd-fit +RTS -h -hbvoid y genera el PostScript para este perfil de memoria. Esto nos dará un informe detallado de toda la memoria cuya "biografía" muestra que ha sido "VOID" (no utilizada). Mi imagen (y me imagino que la tuya también) muestra que la memoria VOID consiste en pedazos etiquetados "precomputeDisksFor/pre...". Podemos asumir que la segunda palabra debe ser "precomp" (¿quieres saber por qué? Mira el código y trata de encontrar funciones con nombres que empiecen con "pre" que sean llamados desde dentro de precomputeDisksFor)
Esto significa que la memoria ha sido ocupada por la lista generada dentro de "precomp". Los rumores dicen que las fugas de memoria en Haskell se producen por falta de flojera o por demasiada flojera. Parece que aquí tenemos muy poca flojera: estamos evaluando más elementos de la lista de los que realmente necesitamos y eso impide que sean liberados por el recolector de basura.
Nota cómo buscamos elementos de "precomp" en esta porción de código:
case [ DirPack (dir_size d + s) (d:ds) | d <- filter ( (inRange (1,limit)).dir_size ) dirs
, dir_size d > 0
, let (DirPack s ds)=precomp!!(fromInteger (limit - dir_size d))
, d `notElem` ds
Está claro que la lista completa generada por "precomp" debe ser mantenida en memoria para hacer esas búsquedas, dado que no podemos estar seguros de si algún elemento ya no va a ser necesario y puede ser retirado de la memoria.
Escribamos el código de nuevo para eliminar la lista:
-- Taken from 'cd-fit-4-4.hs'
-- Sea `bestDisk x' el disco "más compactamente empacado" de
-- tamaño total no mayor a `x'.
-- ¿Cómo calcular `bestDisk'? Optemos por una definición recursiva:
-- Caso base de la recursión: el disco mejor empacado para tamaño 0
-- es vacío y el disco mejor empacado para una lista vacía de directorios
-- también es el vacío
bestDisk 0 _ = DirPack 0 []
bestDisk _ [] = DirPack 0 []
-- Paso recursivo: para el tamaño `limit' mayor que cero, el disco mejor
-- empacado se calcula de la manera siguiente:
bestDisk limit dirs =
-- Toma todos los directorios no vacíos que quepan por sí mismos en ese disco,
-- uno por uno. Sea el tamaño de un directorio d en particular `dir_size d'.
-- Agreguémoslo al disco mejor empacado de tamaño <= (limit - dir_size d),
-- produciendo un disco de tamaño <= limit. Hagamos esto para todos los
--directorios "candidato" que no están aún en el disco:
case [ DirPack (dir_size d + s) (d:ds) | d <- filter ( (inRange (1,limit)).dir_size ) dirs
, dir_size d > 0
, let (DirPack s ds)= bestDisk (limit - dir_size d) dirs
, d `notElem` ds
] of
-- O no podemos agregar ningún directorio (probablemente porque todos
-- son muy grandes); bueno, reportemos que ese disco se debe quedar vacío:
[] -> DirPack 0 []
-- O creamos otros empacamientos diferentes, y seleccionamos el mejor de todos:
packs -> maximumBy cmpSize packs
cmpSize a b = compare (pack_size a) (pack_size b)
dynamic_pack limit dirs = bestDisk limit dirs
Compila la versión con evaluación de desempeño de este código y obtén el perfil de ejecución general (con "+RTS -p"). Vas a conseguir algo parecido a esto:
cd-fit +RTS -p -RTS
total time = 0.00 secs (0 ticks @ 20 ms)
total alloc = 1,129,520 bytes (excludes profiling overheads)
COST CENTRE MODULE %time %alloc
CAF GHC.Float 0.0 4.4
main Main 0.0 93.9
individual inherited
COST CENTRE MODULE no. entries %time %alloc %time %alloc
MAIN MAIN 1 0 0.0 0.0 0.0 100.0
main Main 180 1 0.0 93.9 0.0 94.2
prop_dynamic_pack_small_disk Main 181 100 0.0 0.0 0.0 0.3
dynamic_pack Main 182 200 0.0 0.2 0.0 0.3
bestDisk Main 183 200 0.0 0.1 0.0 0.1
Obtuvimos una gran mejora: ¡el consumo de memoria se reduce por un factor de 700! Ya podemos probar el código en el problema real - modifica el código para ejecutar la prueba para empacar el disco de tamaño completo:
main = quickCheck prop_dynamic_pack_is_fixpoint
Compila con evaluación de desempeño y ejecuta (con "+RTS -p"). Si no tienes suerte y se produce al azar un conjunto de pruebas considerablemente grande, tendrás que esperar. Y esperar aún más. Y más.
Ve a preparar té. Tómate el té. Lee algo de Tolstoi (¿tienes "La Guerra y La Paz" a la mano?). Lo más probable es que para cuando termines con Tolstoi el programa siga corriendo (mejor créeme, no hagas la prueba).
Si tienes suerte, tu programa finalizará suficientemente rápido y te producirá un perfil. De acuerdo con un perfil, el programa pasa el 99% del tiempo dentro de bestDisk. ¿Podemos mejorar de alguna forma el desempeño de bestDisk?
Nota que bestDisk realiza varios cálculos simples para los que se debe llamar a sí mismo. Sin embargo, lo hace de forma ineficiente - cada vez le pasamos a bestDisk exactamente el mismo conjunto de directorios, aún cuando ya hemos "empacado" algunos. Arreglemos eso:
Note that bestDisk performs several simple calculation for which it must call itself. However, it is done rather inefficiently - each time we pass to bestDisk the exact same set of directories as it was called with, even if we have already "packed" some of them. Let's amend this:
-- Taken from 'cd-fit-4-5.hs'
case [ DirPack (dir_size d + s) (d:ds) | let small_enough = filter ( (inRange (0,limit)).dir_size ) dirs
, d <- small_enough
, dir_size d > 0
, let (DirPack s ds)= bestDisk (limit - dir_size d) (delete d small_enough)
] of
Recompila y ejecuta de nuevo. Los tiempos pueden ser prolongados, pero soportables, y el número de veces que llama a bestDisk (de acuerdo al perfil) debe disminuir significativamente.
Finalmente, comparemos ambos algoritmos de empacado. Intuitivamente sentimos que el algoritmo voraz debe producir peores resultados, ¿o no?; hagamos pruebas para verificar:
-- Taken from 'cd-fit-4-5.hs'
prop_greedy_pack_is_no_better_than_dynamic_pack ds =
pack_size (greedy_pack ds) <= pack_size (dynamic_pack media_size ds)
Ejecuta quickCheck con esta prueba varias veces para hacer la comparación. Yo siento que con esto concluyen nuestros ejercicios empacando la mochila.
El lector con sed de aventura puede ir más lejos implementando "escalamiento" para dynamic_pack, que es cuando se dividen los directorios y los discos por tamaño y se comienza empacando los más pequeños (lo que promete que corre más rápido).
Capítulo 5: (Ab)usando mónadas y destruyendo constructores por negocio y diversión
Ya hemos mencionado las mónadas varias veces. Están descritas en numerosos artículos y tutoriales (ver el Capítulo 400). Es difícil leer una lista de correos de Haskell y no cruzarse con la palabra "monad" una docena de veces.
Como ya hemos hecho avances con Haskell, es momento de revisitar las mónadas una vez más. Dejaré que otras fuentes te enseñen la teoría detrás de las mónadas, la utilidad del concepto, etc; en lugar de eso, me enfocaré en mostrar ejemplos.
Tomemos una parte de un programa de mundo real que involucra procesamiento XML. Trabajaremos con atributos de etiqueta XML, que son esencialmente valores con nombre:
-- Taken from 'chapter5-1.hs'
type Attribute = (Name, AttValue)
'Name' es una cadena, y AttValue puede ser una cadena o referencias (también cadenas) a otros atributos que guardan el valor real (esto no es algo válido en XML, pero, para el ejemplo, lo haremos así). Decir "o" sugiere que usemos el tipo de dato 'Either' ("uno de"):
type AttValue = Either Value [Reference]
type Name = String
type Value = String
type Reference = String
-- Lista de atributos simples muestra:
simple_attrs = [ ( "xml:lang", Left "en" )
, ( "xmlns", Left "jabber:client" )
, ( "xmlns:stream", Left "http://etherx.jabber.org/streams" ) ]
-- Lista de atributos muestra con referencias:
complex_attrs = [ ( "xml:lang", Right ["lang"] )
, ( "lang", Left "en" )
, ( "xmlns", Right ["ns","subns"] )
, ( "ns", Left "jabber" )
, ( "subns", Left "client" )
, ( "xmlns:stream", Left "http://etherx.jabber.org/streams" ) ]
Nuestro objetivo es: escribir una función que busque un valor del atributo por nombre en una lista dada de atributos. Cuando el atributo contenga referencias, las resolvemos (buscando el atributo referenciado en la misma lista) y concatenamos sus valores, separados por punto y coma. Entonces, la búsqueda del atributo "xmlns" desde ambos conjuntos muestra debe regresar el mismo valor.
Siguiendo el ejemplo de Data.List.lookup de la biblioteca estándar, llamaremos a nuestra función lookupAttr que regresará Maybe Value, permitiendo manejar errores en la búsqueda:
-- Taken from 'chapter5-1.hs'
lookupAttr :: Name -> [Attribute] -> Maybe Value
-- Como no tenemos código para 'lookupAttr', pero queremos
-- que compile, usamos la función 'undefined' para
-- indicar un cuerpo de función que siempre falla al ser ejecutado.
lookupAttr = undefined
Intentemos escribir lookupAttr usando lookup de forma directa:
-- Taken from 'chapter5-1.hs'
import Data.List
lookupAttr :: Name -> [Attribute] -> Maybe Value
lookupAttr nm attrs =
-- Primero, buscamos 'Maybe AttValue' por nombre y
-- vemos si hemos tenido éxito:
case (lookup nm attrs) of
-- Simplemente propaga el error.
Nothing -> Nothing
-- Si el nombre existe, ver si es valor o referencia:
Just attv -> case attv of
-- Es un valor; regrésalo.
Left val -> Just val
-- Es una lista de referencias :(
-- Tenemos que seguirlas, y tener cuidado con
-- los posibles errores.
-- Primero, hacemos búsqueda en todas las referencias...
Right refs -> let vals = [ lookupAttr ref attrs | ref <- refs ]
-- ...luego, excluimos los errores
wo_failures = filter (/=Nothing) vals
-- ...buscamos forma de sacar los datos del contenedor 'Just'
stripJust (Just v) = v
-- ...la usamos para extraer los resultados como cadenas
strings = map stripJust wo_failures
in
-- ...finalmente los combinamos en una sola cadena.
-- Si todas las búsquedas fallaron, debemos propagar un error.
case null strings of
True -> Nothing
False -> Just (concat (intersperse ":" strings))
Probando:
*Main> lookupAttr "xmlns" complex_attrs Just "jabber:client" *Main> lookupAttr "xmlns" simple_attrs Just "jabber:client" *Main>
Funciona, pero... parece extraño que haga falta tanto código para hacer algo tan sencillo. Si examinas el código de cerca, verás que el exceso de código es causado por:
- el hecho de que verificamos si un error ocurrió después de cada paso
- sacar Strings de los constructores de datos
MaybeyEitherpara volverlas a meter.
En este punto los programadores Java/C++ dirían que, como estamos pasando los errores hacia arriba, todos esos casos se pueden reemplazar con un bloque "try ... catch ...", y tendrían razón. ¿Significa eso que los programadores Haskell están limitados a usar "case", que lleva más de 10 años siendo obsoleto?
¡Mónadas al rescate! Como puedes leer en otras partes (vé en la sección 400), las mónadas se usan de formas avanzadas para construir cálculos a partir de otros cálculos. Exactamente lo que necesitamos - queremos combinar varios pasos simples (búsqueda de valores, búsqueda de referencias...) en la función lookupAttr de forma que podamos tomar en cuenta posibles errores.
Comencemos con el código y lo analizaremos luego:
-- Taken from 'chapter5-2.hs'
import Control.Monad
lookupAttr' nm attrs = do
-- Buscamos 'AttValue' por nombre
attv <- lookup nm attrs
-- Vemos si es valor o referencia
case attv of
-- Es valor; lo regresamos
Left val -> Just val
-- Es lista de referencias
-- Las buscamos, teniendo cuidado con los errores
-- Buscamos todas las referencias...
Right refs -> do vals <- sequence $ map (flip lookupAttr' attrs) refs
-- ...como todos los errores fueron filtrados por "Magia Monádica",
-- ...y todos los 'Just' fueron también retirados,
-- ...sólo combinamos los valores en una sola cadena
-- ...y regresamos un error si está vacía.
guard (not (null vals))
return (concat (intersperse ":" vals))
Ejercicio: compila el código, y prueba que lookupAttr y lookupAttr' de verdad funcionan igual. Trata de hacerlo escribiendo un a prueba QuickCheck, definiendo instance Arbitrary Name para que los nombres arbitrarios los tome de los nombres disponibles en simple_attrs.
Bueno, de regreso a la historia. ¿Notaste la drástica reducción en tamaño de código? Sin los comentarios, el código ocupa 7 líneas en lugar de 13 - poco más de la mitad. ¿Cómo conseguimos esto?
Primero, date cuenta de que nunca verificamos si algún cálculo regresa Nothing. Aún así, trata de buscar un nombre de atributo que no exista, y lookupAttr'</haskell> va a regresar Nothing. ¿Cómo puede ser? El secreto está en el hecho de que el constructor de tipo <hask>Maybe es una "mónada".
Empleamos la palabra clave do para indicar que el bloque de código a continuación es una secuencia de acciones monádicas, donde tiene que suceder magia monádica cuando usemos '<-', 'return' o pasemos de una acción a otra.
Diferentes mónadas tienen diferente magia. El código de biblioteca dice que el constructor de tipo Maybees una mónada en la que podemos usar <- para "extraer" valores del contenedor Just y usar return para volver a meterlos en forma de Just some_value. Cuando pasamos de una acción a otra en el bloque "do" ocurre una verificación. Si la acción regresa Nothing, todos los cálculos de ahí en adelante serán omitidos y todo el bloque "do" regresará Nothing.
Intenta hacer esto para entenderlo mejor:
*Main> let foo x = do v <- x; return (v+1) in foo (Just 5)
Just 6
*Main> let foo x = do v <- x; return (v+1) in foo Nothing
Nothing
*Main> let foo x = do v <- x; return (Data.Char.ord v) in foo (Just 'a')
Just 97
*Main> let foo x = do v <- x; return (Data.Char.ord v) in foo Nothing
Nothing
*Main>
Por ahora no te fijes en sequence y guard; más tarde veremos esa parte.
Como ya retiramos una razón para el exceso de código, es momento de atacar la otra. Nota que henos tenido que usar case para deconstruir el valor de tipo Either Value [Reference]. Seguramente no somos los primeros que tenemos que hacer esto, y que ese caso de uso debe ser muy común.
En efecto, hay un remedio simple para nuestro caso, y se llama either:
*Main> :t either either :: (a -> c) -> (b -> c) -> Either a b -> c
La declaración de tipo se ve complicada, pero aquí hay algunos ejemplos para ayudar a entenderla:
*Main> :t either (+1) (length) either (+1) (length) :: Either Int [a] -> Int *Main> either (+1) (length) (Left 5) 6 *Main> either (+1) (length) (Right "foo") 3 *Main>
Parece que este es exactamente el caso. Reemplacemos case con una invocación a either:
-- Taken from 'chapter5-3.hs'
lookupAttr'' nm attrs = do
attv <- lookup nm attrs
either Just (dereference attrs) attv
where
dereference attrs refs = do
vals <- sequence $ map (flip lookupAttr'' attrs) refs
guard (not (null vals))
return (concat (intersperse ":" vals))
Se va poniendo mejor :)
Ahora, como semi-ejercicio, intenta entender el significado de "sequence", "guard" and "flip" a partir de la siguiente sesión en ghci:
*Main> :t sequence sequence :: (Monad m) => [m a] -> m [a] *Main> :t [Just 'a', Just 'b', Nothing, Just 'c'] [Just 'a', Just 'b', Nothing, Just 'c'] :: [Maybe Char] *Main> :t sequence [Just 'a', Just 'b', Nothing, Just 'c'] sequence [Just 'a', Just 'b', Nothing, Just 'c'] :: Maybe [Char]
*Main> sequence [Just 'a', Just 'b', Nothing, Just 'c'] Nothing *Main> sequence [Just 'a', Just 'b', Nothing] Nothing *Main> sequence [Just 'a', Just 'b'] Just "ab"
*Main> :t [putStrLn "a", putStrLn "b"] [putStrLn "a", putStrLn "b"] :: [IO ()] *Main> :t sequence [putStrLn "a", putStrLn "b"] sequence [putStrLn "a", putStrLn "b"] :: IO [()] *Main> sequence [putStrLn "a", putStrLn "b"] a b
*Main> :t [putStrLn "a", fail "stop here", putStrLn "b"] [putStrLn "a", fail "stop here", putStrLn "b"] :: [IO ()] *Main> :t sequence [putStrLn "a", fail "stop here", putStrLn "b"] sequence [putStrLn "a", fail "stop here", putStrLn "b"] :: IO [()] *Main> sequence [putStrLn "a", fail "stop here", putStrLn "b"] a *** Exception: user error (stop here)
Nota que para la mónada Maybe sequence continúa la ejecución hasta el primer Nothing. Se puede observar el mismo comportamiento para la mónada IO. ¡Toma en cuenta que la definición de sequence no incluye ese comportamiento!
Ahora, examinemos guard:
*Main> let foo x = do v <- x; guard (v/=5); return (v+1) in map foo [Just 4, Just 5, Just 6] [Just 5,Nothing,Just 7]
Como puedes ver, es solamente una forma simple de "detener" la ejecución cuando se cumple alguna condición.
If you have been hooked on monads, I urge you to read "All About
Monads" right now (link in Chapter 400).
Chapter 6: Where do you want to go tomorrow?
As the name implies, the author is open for proposals - where should we go next? I had networking + xml/xmpp in mind, but it might be too heavy and too narrow for most of the readers.
What do you think? Drop me a line.
Chapter 400: Monads up close
Read this wikibook chapter. Then, read "All about monads". 'Nuff said :)
Chapter 500: IO up close
Shows that:
c = do a <- someAction
b <- someOtherAction
print (bar b)
print (foo a)
print "done"
really is just a syntax sugar for:
c = someAction >>= \a ->
someOtherAction >>= \b ->
print (bar b) >>
print (foo a) >>
print "done"
and explains about ">>=" and ">>". Oh wait. This was already explained in Chapter 400 :)
Chapter 9999: Installing Haskell Compiler/Interpreter and all necessary software
Plenty of material on this on the web and this wiki. Just go get yourself installation of GHC (6.4 or above) or Hugs (v200311 or above) and "darcs", which we will use for version control.
Chapter 10000: Thanks!
Thanks for comments, proofreading, good advice and kind words go to: Helge, alt, dottedmag, Paul Moore, Ben Rudiak-Gould, Jim Wilkinson, Andrew Zhdanov (avalez), Martin Percossi, SpellingNazi, Davor Cubranic, Brett Giles, Stdrange, Brian Chrisman, Nathan Collins, Anastasia Gornostaeva (ermine), Remi, Ptolomy, Zimbatm, HenkJanVanTuyl, Miguel, Mforbes, Kartik Agaram.
If I should have mentioned YOU and forgot - tell me so.
Without you I would have stopped after Chapter 1 :)
Nota: Esta es una traducción del artículo original en Inglés : Hitchhikers guide to Haskell