Difference between revisions of "Es/Guía de Haskell para autoestopistas"
(→Chapter 2: Parsing the input: Casi hasta la mitad.) |
|||
(39 intermediate revisions by 6 users not shown) | |||
Line 1: | Line 1: | ||
+ | {{Es/Traducción en progreso|titulo=Guía de Haskell para autoestopistas|original=Hitchhikers guide to Haskell}} |
||
+ | |||
== Preámbulo: ¡NO CORRER! == |
== Preámbulo: ¡NO CORRER! == |
||
− | Experiencias recientes de algunos compañeros programadores de C++/Java indican que leyeron varios tutoriales sobre Haskell con |
+ | 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 |
+ | 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 |
+ | '''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 [http://www.haskell.org/haskellwiki/User:Adept Adept] para la información de contacto) o propón cambios al tutorial mediante darcs ([http://adept.linux.kiev.ua/repos/hhgtth/ el repositorio está aquí]) o directamente a este Wiki. |
Ah, casi me olvido: el autor está muy interesado en CUALQUIER opinión. Escríbele algunas líneas o palabras (mira [http://www.haskell.org/haskellwiki/User:Adept Adept] para la información de contacto) o propón cambios al tutorial mediante darcs ([http://adept.linux.kiev.ua/repos/hhgtth/ el repositorio está aquí]) o directamente a este Wiki. |
||
Line 18: | Line 20: | ||
Oh. Espera. Hagamos el usual programa “hola mundo”, antes de que nos |
Oh. Espera. Hagamos el usual programa “hola mundo”, antes de que nos |
||
− | olvidemos, y después sigamos con cosas más |
+ | olvidemos, y después sigamos con cosas más interesantes: |
<haskell> |
<haskell> |
||
Line 45: | Line 47: | ||
<haskell> |
<haskell> |
||
− | main = |
+ | main = Leer lista de directorio y sus tamaños. |
− | + | Decidir como ajustarlos a los CD-Rs. |
|
− | + | Imprimir la solución. |
|
</haskell> |
</haskell> |
||
− | ¿Parece |
+ | ¿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: |
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: |
||
Line 63: | Line 65: | ||
</haskell> |
</haskell> |
||
− | No funciona en realidad, pero bastante parecido al |
+ | 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: |
Empecemos desde arriba: |
||
Line 72: | Line 74: | ||
</haskell> |
</haskell> |
||
− | 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 |
+ | 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 con su nombre, tiende a decir mucho sobre lo que hace la función. |
+ | ¿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: |
Lanza un entorno interactivo de Haskell y examinemos esta función de cerca: |
||
Line 107: | Line 109: | ||
Haskell te permite hacerlo mejor. |
Haskell te permite hacerlo mejor. |
||
− | La librería estandard del lenguaje (llamada “Prelude”) nos da acceso a muchas |
+ | 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”: |
<haskell> |
<haskell> |
||
Line 124: | Line 126: | ||
* después, imprime la palabra “hecho” |
* 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”): |
<haskell> |
<haskell> |
||
Line 132: | Line 134: | ||
</haskell> |
</haskell> |
||
− | 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 |
+ | 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: |
¿Cuándo se ejececutará/evaluará/forzará “main”? Tan rápido como ejecutemos el programa. Lee esto dos veces y trata de comprenderlo: |
||
Line 160: | Line 162: | ||
</haskell> |
</haskell> |
||
− | ¿Te das cuenta de como |
+ | ¿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 |
+ | 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 |
+ | 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: |
<haskell> |
<haskell> |
||
Line 178: | Line 180: | ||
</haskell> |
</haskell> |
||
− | De vuelta al ejercicio - ¿ |
+ | 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? |
---- |
---- |
||
Line 199: | Line 201: | ||
*Main> |
*Main> |
||
− | Ah, por cierto: ¿ |
+ | 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: |
Vamos a probar a ejecutarlo: |
||
Line 244: | Line 246: | ||
A diferencia de otras herramientas en esta área (lex/yacc o JavaCC, |
A diferencia de otras herramientas en esta área (lex/yacc o JavaCC, |
||
para nombrar algunas), los parsers de [[Parsec]] no requieren una |
para nombrar algunas), los parsers de [[Parsec]] no requieren una |
||
− | etapa de prepocesamiento previo. Dado que Haskell |
+ | etapa de prepocesamiento previo. Dado que en Haskell podemos devolver |
− | funciones como resultado de funciones y de esta manera construir |
+ | funciones como resultado de funciones y de esta manera, construir |
funciones a partir de "mero aire", no hay necesidad de una sintáxis |
funciones a partir de "mero aire", no hay necesidad de una sintáxis |
||
separada para la descripción de parsers. Pero ya hicimos suficiente |
separada para la descripción de parsers. Pero ya hicimos suficiente |
||
Line 258: | Line 260: | ||
parseInput = |
parseInput = |
||
do dirs <- many dirAndSize |
do dirs <- many dirAndSize |
||
− | eof |
+ | eof :: Parser () |
return dirs |
return dirs |
||
Line 292: | Line 294: | ||
que operen funcionalidades complejas. |
que operen funcionalidades complejas. |
||
− | Como habrás oido, Haskell no tiene ninguna noción de " |
+ | Como habrás oido, Haskell no tiene ninguna noción de "asignación", |
"estado mutable" ni "variables", y es un "lenguaje funcional puro", |
"estado mutable" ni "variables", y es un "lenguaje funcional puro", |
||
que significa que toda función invocada con los mismos parámetros |
que significa que toda función invocada con los mismos parámetros |
||
Line 313: | Line 315: | ||
evaluada por los profesionales ("en la mónada") lo que te dará el |
evaluada por los profesionales ("en la mónada") lo que te dará el |
||
resultado final, ocultandote toda la complejidad subyacente (cómo |
resultado final, ocultandote toda la complejidad subyacente (cómo |
||
− | preparar la |
+ | preparar la pintura, qué clavos elegir, etc). |
Usemos el entorno interactivo de Haskell para descifrar todas las |
Usemos el entorno interactivo de Haskell para descifrar todas las |
||
Line 327: | Line 329: | ||
*Main> |
*Main> |
||
− | Assuming (well, take my word for it) that "GenParser Char st" is our |
||
− | parsing monad, we could see that "parseInput", when evaluated, will |
||
− | produce a list of "Dir", and "dirAndSize", when evaluated, will |
||
− | produce "Dir". Assuming that "Dir" somehow represents information |
||
− | about single directory, that is pretty much what we wanted, isn't it? |
||
+ | Asumiendo (bueno, confía en mi palabra) que "GenParser Char st" es |
||
− | Let's see what a "Dir" means. We defined ''data[[type]]'' Dir as a record, |
||
+ | nuestra mónada de parseo, podríamos ver que "parseInput", cuando sea |
||
− | which holds an Int and a String: |
||
+ | evaluada, producirá una lista de "Dir", y que "dirAndSize", cuando sea |
||
+ | evaluada, producirá "Dir". Asumiendo que "Dir" representa de alguna |
||
+ | forma la información sobre un solo directorio, es casi lo que queríamos, |
||
+ | o no? |
||
+ | |||
+ | Veamos que significa un "Dir". Nosotros hemos definido el |
||
+ | ''[[type|tipo]] de datos'' Dir como un registro, que contiene un Int y |
||
+ | un String: |
||
<haskell> |
<haskell> |
||
Line 341: | Line 346: | ||
</haskell> |
</haskell> |
||
− | + | Para construir esos registros, debemos usar el ''[[constructor]] de |
|
− | Dir: |
+ | datos'' Dir: |
*Main> :t Dir 1 "foo" |
*Main> :t Dir 1 "foo" |
||
Dir 1 "foo" :: Dir |
Dir 1 "foo" :: Dir |
||
+ | Para evitar la confusión para los novatos, podriamos haber escrito: |
||
− | In order to reduce confusion for newbies, we could have written: |
||
+ | |||
<haskell> |
<haskell> |
||
data Dir = D Int String deriving Show |
data Dir = D Int String deriving Show |
||
</haskell> |
</haskell> |
||
− | , |
+ | , que define el ''[[type|tipo]] de datos'' "Dir" con el |
+ | ''[[constructor]] de datos'' "D". Sin embargo, tradicionalmente el |
||
− | However, traditionally name of the data[[type]] and its [[constructor]] are |
||
+ | nombre del [[type|tipo]] de datos y de su [[constructor]] son el mismo. |
||
− | chosen to be the same. |
||
− | + | La cláusula "[[deriving]] Show" le ordena al compilador hacer "tras |
|
+ | bambalinas" todo el código necesario para que este ''tipo de datos'' |
||
− | the curtains" to make this ''datatype'' conform to the interface of |
||
− | + | cumpla con la interfaz de la ''[[class|clase]] de tipo'' |
|
+ | Show. Explicaremos ''[[class|clases]] de tipo'' más adelante, por |
||
− | now let's just say that this will allow us to "print" instances of |
||
+ | ahora digamos que esto nos permitirá "imprimir" instancias de "Dir". |
||
− | "Dir". |
||
− | |||
− | '''Exercises:''' |
||
− | * examine types of "digit", "anyChar", "many", "many1" and "manyTill" to see how they are used to build more complex parsers from single ones. |
||
− | |||
− | * compare types of "manyTill", "manyTill anyChar" and "manyTill anyChar newline". Note that "anyChar `manyTill` newline" is just another syntax sugar. Note that when function is supplied with less arguments that it actually needs, we get not a value, but a new function, which is called ''partial application''. |
||
+ | '''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''. |
||
− | OK. So, we combined a lot of primitive parsing actions to get ourselves a |
||
+ | Bien, hasta aquí combinamos varias acciones primitivas de "parseo" |
||
− | parser for output of "du -sb". How can we actually parse something? the [[Parsec]] library supplies us with function "parse": |
||
+ | 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 |
*Main> :t parse |
||
Line 380: | Line 385: | ||
*Main> |
*Main> |
||
+ | Al principio el [[type|tipo]] puede parecer un poco críptico, pero una |
||
− | At first the [[type]] might be a bit cryptic, but once we supply "parse" with the parser we made, the compiler gets more information and presents us with a more concise [[type]]. |
||
+ | vez que aplicamos el parser que nosotros hicimos, el compilador tiene más |
||
+ | información y nos muestra un [[type|tipo]] más particular. |
||
+ | Detente aquí y considera lo siguiente por un momento: el compilador se |
||
− | Stop and consider this for a moment. The compiler figured out type of the function without a single type annotation supplied by us! Imagine if a Java compiler deduced types for you, and you wouldn't have to specify types of arguments and return values of methods, ever. |
||
+ | 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 |
||
− | OK, back to the code. We can observe that the "parser" is a function, which, |
||
+ | función, que cuando recibe un parser, un nombre de un fichero o un |
||
− | given a parser, a name of the source file or channel (f.e. "stdin"), and |
||
+ | canal (p.e. "stdin") y datos de entrada (String, que es una lista de |
||
− | source data (String, which is a list of "Char"s, which is written "[Char]"), |
||
+ | "Char"s, que se escribe "[Char]"), producirá o bien un error de "parseo" o |
||
− | will either produce parse error, or parse us a list of "Dir". |
||
+ | una lista de "Dir". |
||
+ | El tipo de datos "Either" es un ejemplo de un tipo de datos cuyo |
||
− | Datatype "Either" is an example of datatype whose constructor has name, different |
||
+ | constructor tiene un nombre diferente del nombre del tipo de datos. De |
||
− | from the name of the datatype. In fact, "Either" has two constructors: |
||
+ | hecho, "Either" tiene dos constructores: |
||
<haskell> |
<haskell> |
||
− | data |
+ | data either a b = Left a | Right b |
</haskell> |
</haskell> |
||
+ | Para entender mejor qué significa, considera el siguiente ejemplo: |
||
− | In order to understand better what does this mean consider the following |
||
− | example: |
||
*Main> :t Left 'a' |
*Main> :t Left 'a' |
||
Line 405: | Line 417: | ||
*Main> |
*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 |
||
− | hold value of one of the two distinct types. However, unlike C/C++ "union", |
||
+ | de datos. Sin embargo, a diferencia de la "union" en C/C++, si |
||
− | when presented with value of type "Either Int Char" we could immediately see |
||
+ | tuvieramos un valor de tipo "Either Int Char" podríamos decir |
||
− | whether its an Int or a Char - by looking at the constructor which was used to |
||
+ | inmediatamente si es un Int o un Char - mirando el constructor usado |
||
− | produce the value. Such datatypes are called "tagged unions", and they are |
||
+ | para producir el valor. Estos tipo de datos se llaman "uniones |
||
− | another [[:Category:Idioms|power tool]] in the Haskell toolset. |
||
+ | disjuntas" y son una [[:Category:Idioms|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 |
||
− | value, but receive not a new monadic value, but a parsing result? That is |
||
+ | resultado de "parseo"? Esto es así porque "parse" es un evaludador |
||
− | because "parse" is an evaluator for "Parser" monad, much like the [[GHC]] or [[Hugs]] runtime is an evaluator for the IO monad. The function "parser" implements all monadic machinery: it tracks errors and positions in input, implements backtracking and lookahead, etc. |
||
+ | 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. |
||
+ | |||
− | let's extend our "main" function to use "parse" and actually parse the input |
||
+ | Extendamos nuestra función "main" para que use "parse", parseé realmente |
||
− | and show us the parsed data structures: |
||
+ | la entrada y nos muestra las estructuras parseadas: |
||
<haskell> |
<haskell> |
||
Line 430: | Line 449: | ||
</haskell> |
</haskell> |
||
− | ''' |
+ | '''Ejercicios:''' |
− | * |
+ | * Para entender mejor el siguiente pedazo de código, 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 ($). |
− | * Try putStrLn "aaa" and print "aaa" and see the difference, examine their types. |
||
− | * Try print (Dir 1 "foo") and putStrLn (Dir 1 "foo"). Examine types of print and putStrLn to understand the behavior in both cases. |
||
+ | * Intenta hacer 'putStrLn "aaa"' y 'print "aaa"' y mira la la diferencia, examina sus tipos. |
||
− | Let's try to run what we have so far: |
||
+ | |||
+ | * 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 |
$ du -sb * | runhaskell ./cd-fit.hs |
||
Line 449: | Line 470: | ||
[Dir 22325 "Article.txt",Dir 18928 "Article.txt~",Dir 1706 "cd-fit.hs",Dir 964 "cd-fit.hs~",Dir 61609 "_darcs"] |
[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 |
||
− | Seems to be doing exactly as planned. Now let's try some erroneous |
||
+ | entrada errónea: |
||
− | input: |
||
$ echo "foo" | runhaskell cd-fit.hs |
$ echo "foo" | runhaskell cd-fit.hs |
||
Line 463: | Line 484: | ||
expecting digit or end of input |
expecting digit or end of input |
||
+ | Parece que se comporta bien. |
||
− | Seems to be doing fine. |
||
− | + | 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 |
||
− | an exercise, first record the changes "outside" of function "main" and |
||
+ | cambios que no están dentro de la función "main" y luego |
||
− | then record the changes in "main". Do "darcs changes" to examine a |
||
+ | registra los que están en "main". Usa "darcs changes" para examinar |
||
− | list of changes you've recorded so far. |
||
+ | 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. |
||
− | Enough preliminaries already. let's go pack some CDs. |
||
+ | Como debes haberte dado cuenta, nuestro problema es clásico. Se llama |
||
− | As you might already have recognized, our problem is a classical one. It is |
||
+ | el "problema de la mochila" |
||
− | called a "knapsack problem" ([http://www.google.com/search?q=knapsack+problem google it up], if you don't know already what it |
||
+ | ([http://www.google.com/search?hl=es&q=problema+mochila búscalo en google], si no lo conoces. Hay más de un millón de resultados.) |
||
− | is. There are more than 100000 links). |
||
+ | Empecemos con la solución voraz, pero primero modifiquemos levemente |
||
− | let's start from the greedy solution, but first let's slightly modify our "Dir" |
||
+ | nuestro tipo de datos "Dir" para facilitar la extracción de sus |
||
− | datatype to allow easy extraction of its components: |
||
+ | componentes: |
||
<haskell> |
<haskell> |
||
Line 489: | Line 512: | ||
---- |
---- |
||
− | ''' |
+ | '''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 |
|
− | "dir_name d" |
+ | 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 |
||
− | The Greedy algorithm sorts directories from the biggest down, and tries to puts |
||
− | + | 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 |
||
− | which directories we added to CD, so let's add another datatype, and code this |
||
+ | ello agreguemos otro tipo de datos y programemos este simple algoritmo de |
||
− | simple packing algorithm: |
||
+ | empaque: |
||
<haskell> |
<haskell> |
||
Line 526: | Line 551: | ||
---- |
---- |
||
+ | Yo resaltaré las áreas que podrías explorar vos mismo (usando otros |
||
− | I'll highlight the areas which you could explore on your own (using other nice |
||
− | + | tutoriales bonitos, especialmente te recomiento "Yet Another Haskell |
|
− | Tutorial" |
+ | 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. |
+ | |||
− | * Instead of coding case-by-case recursive definition of "greedy_pack", we go with higher-order approach, choosing "foldl" as a vehicle for list traversal. Examine its type. Other useful function from the same category are "map", "foldr", "scanl" and "scanr". Look them up! |
||
+ | * 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! |
||
− | * To sort list of "Dir" by size only, we use custom sort function and parameterized sort - "sortBy". This sort of setup where the user may provide a custom "modifier" for a generic library function is quite common: look up "deleteBy", "deleteFirstsBy", "groupBy", "insertBy", "intersectBy", "maximumBy", "minimumBy", "sortBy", "unionBy". |
||
+ | |||
− | * To code the quite complex function "maybe_add_dir", we introduced several '''local definitions''' in the "let" clause, which we can reuse within the function body. We used a "where" clause in the "greedy_pack" function to achieve the same effect. Read about "let" and "where" clauses and the differences between them. |
||
+ | * 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". |
||
− | * Note that in order to construct a new value of type "DirPack" (in function "maybe_add_dir") we haven't used the helper accessor functions "pack_size" and "dirs" |
||
+ | |||
+ | * 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 |
||
− | In order to actually use our greedy packer we must call it from our "main" |
||
+ | "main", así que agreguemos algunas líneas: |
||
− | function, so let's add a lines: |
||
<haskell> |
<haskell> |
||
Line 546: | Line 575: | ||
</haskell> |
</haskell> |
||
+ | 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. |
||
− | Verify integrity of our definitions by (re)loading our code in ghci. Compiles? |
||
− | Thought so :) Now, do "darcs record" and add some sensible commit message. |
||
+ | Es el momento de probar nuestra creación. Podemos hacerlo ejecutando directamente de la siguiente forma: |
||
− | Now it is time to test our creation. We could do it by actually running it in |
||
− | the wild like this: |
||
$ du -sb ~/DOWNLOADS/* | runhaskell ./cd-fit.hs |
$ du -sb ~/DOWNLOADS/* | runhaskell ./cd-fit.hs |
||
+ | Esto demostrará que nuestro código parece funcionar. Por lo menos esta vez. ¿Qué tal estaría |
||
− | This will prove that our code seems to be working. At least, this once. How |
||
+ | 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 |
||
− | about establishing with reasonable degree of certainty that our code, parts |
||
+ | algunas pruebas? |
||
− | and the whole, works properly, and doing so in re-usable manner? In other |
||
− | words, how about writing some test? |
||
+ | 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 :) |
||
− | Java programmers used to JUnit probably thought about screens of boiler-plate |
||
− | code and hand-coded method invocations. Never fear, we will not do anything as |
||
− | silly :) |
||
− | + | 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. |
||
− | [[QuickCheck]] is a tool to do automated testing of your functions using |
||
− | (semi)random input data. In the spirit of "100b of code examples is worth 1kb of |
||
− | praise" let's show the code for testing the following ''property'': An attempt to pack directories returned by "greedy_pack" should return "DirPack" of exactly the same pack: |
||
<haskell> |
<haskell> |
||
-- Taken from 'cd-fit-3-2.hs' |
-- Taken from 'cd-fit-3-2.hs' |
||
import Test.QuickCheck |
import Test.QuickCheck |
||
− | import Control.Monad (liftM2) |
+ | import Control.Monad (liftM2, replicateM) |
-- We must teach QuickCheck how to generate arbitrary "Dir"s |
-- We must teach QuickCheck how to generate arbitrary "Dir"s |
||
Line 587: | Line 609: | ||
-- Generate random name 1 to 300 chars long, consisting of symbols "fubar/" |
-- Generate random name 1 to 300 chars long, consisting of symbols "fubar/" |
||
gen_name = do n <- choose (1,300) |
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_". |
-- For convenience and by tradition, all QuickCheck tests begin with prefix "prop_". |
||
Line 596: | Line 618: | ||
</haskell> |
</haskell> |
||
+ | ejecutemos la prueba, tras lo cual explicaré cómo funciona: |
||
− | let's run the test, after which I'll explain how it all works: |
||
Prelude> :r |
Prelude> :r |
||
Line 606: | Line 628: | ||
*Main> |
*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. |
||
− | We've just seen our "greedy_pack" run on a 100 completely (well, almost |
||
− | completely) random lists of "Dir"s, and it seems that property indeed holds. |
||
+ | Disequemos el código. La parte más intrigante es "instance Arbitrary Dir where", que declara que "Dir" es una instancia ('''[[instance]]''') de '''type[[class]]''') "Arbitrary". Whoa, ¡es un montón de palabras desconocidas! :) Veamos con más calma. |
||
− | let's dissect the code. The most intriguing part is "instance Arbitrary Dir |
||
− | where", which declares that "Dir" is an '''[[instance]]''' of '''type[[class]]''' "Arbitrary". Whoa, that's a whole lot of unknown words! :) Let's slow down a |
||
− | bit. |
||
+ | ¿Qué es una clase de tipos ('''type[[class]]''')? 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. |
||
− | What is a '''type[[class]]'''? A typeclass is a Haskell way of dealing with the |
||
− | following situation: suppose that you are writing a library of usefull |
||
− | functions and you dont know in advance how exactly they will be used, so you |
||
− | want to make them generic. Now, on one hand you dont want to restrict your |
||
− | users to certain type (e.g. String). On the other hand, you want to enforce |
||
− | the convention that arguments for your function must satisfy a certain set of |
||
− | constraints. That is where '''typeclass''' comes in handy. |
||
− | + | 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. |
|
− | your type must fulfill in order to be admitted as an argument to certain |
||
− | functions. |
||
− | + | Examinemos la clase de tipos "Arbitrary": |
|
*Main> :i Arbitrary |
*Main> :i Arbitrary |
||
Line 641: | Line 652: | ||
-- rest skipped -- |
-- rest skipped -- |
||
− | + | Se puede leer así: "Cualquier [[type|tipo]] (llamémosle 'a') puede ser miembro de la [[class|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"! |
||
− | Now, if you write a function which operates on its arguments solely by means |
||
− | of "arbitrary" and "coarbitrary", you can be sure that this function will work |
||
− | on any type which is an instance of "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. |
||
− | let's say it again. Someone (maybe even you) writes the code (API or library), |
||
− | which requires that input values implement certain ''interfaces'', which is |
||
− | described in terms of functions. Once you show how your type implements this |
||
− | ''interface'' you are free to use API or library. |
||
+ | Considera la función "sort" ("ordenar") de la biblioteca estándar: |
||
− | Consider the function "sort" from standard library: |
||
*Main> :t Data.List.sort |
*Main> :t Data.List.sort |
||
Data.List.sort :: (Ord a) => [a] -> [a] |
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: |
||
− | We see that it sorts lists of any values which are instance of typeclass |
||
− | "Ord". Let's examine that class: |
||
*Main> :i Ord |
*Main> :i Ord |
||
Line 679: | Line 684: | ||
*Main> |
*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? |
||
− | We see a couple of interesting things: first, there is an additional |
||
− | requirement listed: in order to be an instance of "Ord", type must first be an |
||
− | instance of typeclass "Eq". Then, we see that there is an awful lot of |
||
− | functions to define in order to be an instance of "Ord". Wait a second, isn't |
||
− | it silly to define both (<) and (>) when one could be expressed via another? |
||
+ | ¡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. |
||
− | Right you are! Usually, typeclass contains several "default" implementation |
||
− | for its functions, when it is possible to express them through each other (as |
||
− | it is with "Ord"). In this case it is possible to supply only a minimal |
||
− | definition (which in case of "Ord" consists of any single function) and others |
||
− | will be automatically derived. If you supplied fewer functions than are required |
||
− | for minimal implementation, the compiler/interpreter will say so and |
||
− | explain which functions you still have to define. |
||
− | + | Una vez más, vemos que muchos de los [[type|tipo]]s son ya instancia de la clase de tipos Ord, y por eso es posible ordenarlos. |
|
+ | Veamos de nuevo la definición de "Dir": |
||
− | Now, let's take a look back to the definition of "Dir": |
||
<haskell> |
<haskell> |
||
Line 702: | Line 697: | ||
</haskell> |
</haskell> |
||
− | + | ¿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. |
|
− | that type! |
||
+ | Un comentario para programadores Java: imaginen un compilador java que derive automáticamente código para "implements Storable"... |
||
− | Side note for Java programmers: just imagine java compiler which derives code |
||
− | for "implements Storable" for you... |
||
+ | Un comentario para programadores C++: imaginen que los constructores de copia son escritos por el compilador... |
||
− | Side note for C++ programmers: just imagine that deep copy constructors are |
||
− | being written for you by compiler.... |
||
---- |
---- |
||
Line 718: | Line 710: | ||
---- |
---- |
||
+ | 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: |
||
− | OK, back to our tests. So, what we have had to do in order to make "Dir" an |
||
+ | |||
− | instance of "Arbitrary"? Minimal definition consists of "arbitrary". Let's |
||
− | examine it up close: |
||
*Main> :t arbitrary |
*Main> :t arbitrary |
||
arbitrary :: (Arbitrary a) => Gen a |
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 :) ) |
||
− | See that "Gen a"? Reminds you of something? Right! Think of "IO a" and "Parser |
||
− | a" which we've seen already. This is yet another example of action-returning |
||
− | function, which could be used inside "do"-notation. (You might ask yourself, |
||
− | wouldn't it be useful to generalize that convenient concept of actions and |
||
− | "do"? Of course! It is already done, the concept is called "[[Monad]]" and we will talk about it in Chapter 400 :) ) |
||
− | + | Como aquí 'a' es una [[type variable|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: |
||
− | Let's look at the code: |
||
<haskell> |
<haskell> |
||
Line 743: | Line 730: | ||
-- Generate random name 1 to 300 chars long, consisting of symbols "fubar/" |
-- Generate random name 1 to 300 chars long, consisting of symbols "fubar/" |
||
gen_name = do n <- choose (1,300) |
gen_name = do n <- choose (1,300) |
||
− | + | replicateM (n*10+1) (elements "fubar/") |
|
</haskell> |
</haskell> |
||
+ | 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". |
||
− | We have used the library-provided functions "choose" and "elements" to build up |
||
− | "gen_size :: Gen Int" and "gen_name :: Gen String" (exercise: don't take my |
||
− | word on that. Find a way to check types of "gen_name" and "gen_size"). Since |
||
− | "Int" and "String" are components of "Dir", we sure must be able to use "Gen |
||
− | Int" and "Gen String" to build "Gen Dir". But where is the "do" block for |
||
− | that? There is none, and there is only single call to "liftM2". |
||
+ | Examinémoslo: |
||
− | Let's examine it: |
||
*Main> :t liftM2 |
*Main> :t liftM2 |
||
liftM2 :: (Monad m) => (a1 -> a2 -> r) -> m a1 -> m a2 -> m r |
liftM2 :: (Monad m) => (a1 -> a2 -> r) -> m a1 -> m a2 -> m r |
||
+ | ¿Espanta, no? Démosle al verificador de tipos un poco de contexto: |
||
− | Kind of scary, right? Let's provide typechecker with more context: |
||
*Main> :t liftM2 Dir |
*Main> :t liftM2 Dir |
||
liftM2 Dir :: (Monad m) => m Int -> m String -> m 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". |
+ | 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: |
|
− | later) and just note for now that: |
||
− | * "2" is a number of arguments for data constructor "Dir" and we have used "liftM2" to construct "Gen Dir" out of "Dir" |
||
− | * There are also "liftM", "liftM3", "liftM4", "liftM5" |
||
− | * "liftM2" is defined as "liftM2 f a1 a2 = do x<-a1; y<-a2; return (f x y)" |
||
+ | * "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" |
||
− | Hopefully, this will all make sense after you read it for the third |
||
+ | * También hay "liftM", "liftM3", "liftM4", "liftM5" |
||
− | time ;) |
||
+ | * "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 ;) |
||
− | Oh, by the way - dont forget to "darcs record" your changes! |
||
+ | Ah, y de paso - ¡no olvides hacer "darcs record" para guardar tus cambios! |
||
− | == Chapter 4: REALLY packing the knapsack this time == |
||
+ | == Capítulo 4: Empacando DE VERDAD la mochila, ahora sí == |
||
− | In this chapter we are going to write another not-so-trivial packing |
||
− | method, compare packing methods efficiency, and learn something new |
||
− | about debugging and profiling of the Haskell programs along the way. |
||
+ | 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. |
||
− | It might not be immediately obvious whether our packing algorithm is |
||
− | effective, and if yes - in which particular way? Whether it's runtime, |
||
− | memory consumption or result are of sufficient quality, are there any |
||
− | alternative algorithms, and how do they compare to each other? |
||
+ | 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? |
||
− | Let's code another solution to the knapsack packing problem, called the "dynamic programming method" and put both variants to the test. |
||
+ | |||
+ | 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: |
||
− | This time, I'll not dissect the listing and explain it bit by bit. Instead, comments are provided in the code: |
||
<haskell> |
<haskell> |
||
-- Taken from 'cd-fit-4-1.hs' |
-- Taken from 'cd-fit-4-1.hs' |
||
---------------------------------------------------------------------------------- |
---------------------------------------------------------------------------------- |
||
+ | -- Solución por programación dinámica al problema de empacar |
||
− | -- Dynamic programming solution to the knapsack (or, rather, disk) packing problem |
||
+ | -- 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 :: [Dir] -> [DirPack] |
||
precomputeDisksFor dirs = |
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..] |
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 [] |
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 = |
bestDisk limit = |
||
− | -- 1. |
+ | -- 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 |
case [ DirPack (dir_size d + s) (d:ds) | d <- filter ( (inRange (1,limit)).dir_size ) dirs |
||
, dir_size d > 0 |
, dir_size d > 0 |
||
Line 822: | Line 802: | ||
, d `notElem` ds |
, d `notElem` ds |
||
] of |
] 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 [] |
[] -> DirPack 0 [] |
||
− | -- |
+ | -- O generemos otro empaque diferente. Seleccionemos el mejor de todos: |
packs -> maximumBy cmpSize packs |
packs -> maximumBy cmpSize packs |
||
Line 832: | Line 813: | ||
in precomp |
in precomp |
||
+ | -- Cuando precalculamos discos de todos los posibles tamaños para el conjunto de |
||
− | -- When we precomputed disk of all possible sizes for the given set of dirs, solution to |
||
+ | -- directorios dado, la solución a un problema en particular es simple: sólo toma la |
||
− | -- particular problem is simple: just take the solution for the required 'media_size' and |
||
+ | -- solución para el 'media_size' requerido, y eso es todo. |
||
− | -- that's it! |
||
+ | |||
− | dynamic_pack dirs = (precomputeDisksFor dirs)!!media_size |
||
+ | dynamic_pack dirs = (precomputeDisksFor dirs) !! media_size |
||
</haskell> |
</haskell> |
||
+ | Nota que se usó casi la misma cantidad de texto para describir el algoritmo y para implementarlo. ¿Bien, no? |
||
− | Notice that it took almost the same amount of text to describe algorithm and to write implementation for it. Nice, eh? |
||
---- |
---- |
||
Line 851: | Line 833: | ||
---- |
---- |
||
+ | 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 <hask>Bounded</hask>, que permite definir y examinar esos límites: |
||
− | Before we move any further, let's do a small cosmetic change to our |
||
− | code. Right now our solution uses 'Int' to store directory size. In |
||
− | Haskell, 'Int' is a platform-dependent integer, which imposes certain |
||
− | limitations on the values of this type. Attempt to compute the value |
||
− | of type 'Int' that exceeds the bounds will result in overflow error. |
||
− | Standard Haskell libraries have special typeclass |
||
− | <hask>Bounded</hask>, which allows to define and examine such bounds: |
||
Prelude> :i Bounded |
Prelude> :i Bounded |
||
Line 866: | Line 842: | ||
instance Bounded Int -- Imported from GHC.Enum |
instance Bounded Int -- Imported from GHC.Enum |
||
+ | Vemos que 'Int' efectivamente tiene límites. Examinemos dichos límites: |
||
− | We see that 'Int' is indeed bounded. Let's examine the bounds: |
||
Prelude> minBound :: Int |
Prelude> minBound :: Int |
||
Line 874: | Line 850: | ||
Prelude> |
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. |
||
− | Those of you who are C-literate, will spot at once that in this case |
||
− | the 'Int' is so-called "signed 32-bit integer", which means that we |
||
− | would run into errors trying to operate on directories/directory packs |
||
− | which are bigger than 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': |
||
− | Luckily for us, Haskell has integers of arbitrary precision (limited |
||
− | only by the amount of available memory). The appropriate type is |
||
− | called 'Integer': |
||
Prelude> (2^50) :: Int |
Prelude> (2^50) :: Int |
||
Line 888: | Line 859: | ||
1125899906842624 -- no overflow |
1125899906842624 -- no overflow |
||
Prelude> |
Prelude> |
||
+ | |||
+ | Cambiemos las definiciones de 'Dir' y de 'DirPack' para permitir directorios de tamaños mayores: |
||
− | Lets change definitions of 'Dir' and 'DirPack' to allow for bigger |
||
− | directory sizes: |
||
<haskell> |
<haskell> |
||
-- Taken from 'cd-fit-4-2.hs' |
-- Taken from 'cd-fit-4-2.hs' |
||
Line 897: | Line 868: | ||
</haskell> |
</haskell> |
||
+ | Intenta compilar el código o cargarlo en ghci. Obtendrás los siguientes errores: |
||
− | Try to compile the code or load it into ghci. You will get the |
||
− | following errors: |
||
cd-fit-4-2.hs:73:79: |
cd-fit-4-2.hs:73:79: |
||
Line 915: | Line 885: | ||
dynamic_pack dirs = (precomputeDisksFor dirs) !! media_size |
dynamic_pack dirs = (precomputeDisksFor dirs) !! media_size |
||
+ | Parece que Haskell tiene algunos problemas usando 'Integer' con '(!!)'. Veamos por qué: |
||
− | |||
− | It seems like Haskell have some troubles using 'Integer' with '(!!)'. |
||
− | Let's see why: |
||
Prelude> :t (!!) |
Prelude> :t (!!) |
||
(!!) :: [a] -> Int -> a |
(!!) :: [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: |
||
− | Seems like definition of '(!!)' demands that index will be 'Int', not |
||
− | 'Integer'. Haskell never converts any type to some other type |
||
− | automatically - programmer have to explicitly ask for that. |
||
− | + | No voy a repetir la sección "Standard Haskell Classes" de |
|
− | [http://haskell.org/onlinereport/basic.html the Haskell Report] |
+ | [http://haskell.org/onlinereport/basic.html 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 <hask>Num</hask> requiere que los tipos numéricos implementen el método <hask>fromInteger</hask>: |
− | explain, why typeclasses for various numbers organized the way they |
||
− | are organized. I will just say that standard typeclass |
||
− | <hask>Num</hask> demands that numeric types implement method |
||
− | <hask>fromInteger</hask>: |
||
Prelude> :i Num |
Prelude> :i Num |
||
Line 948: | Line 910: | ||
instance Num Int -- Imported from GHC.Num |
instance Num Int -- Imported from GHC.Num |
||
+ | Vemos que <hask>Integer</hask> es miembro de la clase de tipos <hask>Num</hask>, y por lo tanto podemos utilizar <hask>fromInteger</hask> para hacer que desaparezcan los errores de tipo: |
||
− | We see that <hask>Integer</hask> is a member of typeclass |
||
− | <hask>Num</hask>, thus we could use <hask>fromInteger</hask> to make |
||
− | the type errors go away: |
||
<haskell> |
<haskell> |
||
Line 965: | Line 925: | ||
</haskell> |
</haskell> |
||
+ | Los errores de tipo desaparecieron, pero el lector atento se dará cuenta de que cuando la expresión <hask>(limit - dir_size d)</hask> exceda los límites de <hask>Int</hask>, ocurrirá un sobreflujo, y no podremos acceder al elemento correcto en la lista. No te preocupes, resolveremos esto en un momento. |
||
− | Type errors went away, but careful reader will spot at once that when |
||
− | expression <hask>(limit - dir_size d)</hask> will exceed the bounds |
||
− | for <hask>Int</hask>, overflow will occur, and we will not access the |
||
− | correct list element. Dont worry, we will deal with this in a short while. |
||
− | + | Ahora, escribamos la prueba QuickCheck para esta función de la misma forma que la prueba para <tt>greedy_pack</tt>: |
|
<haskell> |
<haskell> |
||
Line 979: | Line 936: | ||
</haskell> |
</haskell> |
||
+ | Ahora, intentemos ejecutar (¡NO ENTRAR EN PÁNICO y guarda primero lo que estés haciendo en otras aplicaciones!): |
||
− | Now, lets try to run (DONT PANIC and save all you work in other applications first!): |
||
*Main> quickCheck prop_dynamic_pack_is_fixpoint |
*Main> quickCheck prop_dynamic_pack_is_fixpoint |
||
− | Now, you took my advice seriously, don't you? And you did have your '''Ctrl-C''' handy, didn't you? Most probably, the attempt to run the test resulted in all your memory being taken by <tt>ghci</tt> process, which you hopefully interrupted soon enough by pressing '''Ctrl-C'''. |
||
+ | ¿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 <tt>ghci</tt>, que, si fuiste suficientemente rápido, pudiste interrumpir presionando '''Ctrl-C'''. |
||
− | What happened? Who ate all the memory? How to debug this problem? GHC comes with profiling abilities, but we could not use them - they produce report after program terminates, and our doesn't seem to do so without consuming several terabytes of memory first. Still, there is a lot of room for maneuver. |
||
+ | ¿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. |
||
− | Let's see. Since the have called <tt>dynamic_pack</tt> and it ate all the memory, let's not do this again. Instead, let's see what this function does and tweak it a bit to explore it's behavior. |
||
+ | Veamos. Como llamamos a <tt>dynamic_pack</tt> 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. |
||
− | Since we already know that random lists of "Dir"s generated for our QuickCheck tests are of modest size (after all, <tt>greedy_pack</tt> munches them without significant memory consumption), the size of the input most probably is not the issue. However, <tt>dynamic_pack_is_fixpoint</tt> is building quite a huge list internally (via <tt>precomputeDisksFor</tt>). Could this be a problem? |
||
+ | Como ya sabemos que las listas aleatorias de "Dir"s generadas para nuestras pruebas QuickCheck son de tamaño mediano (después de todo, <tt>greedy_pack</tt> las mastica sin consumir demasiada memoria), el problema más probablemente no es el tamaño de la entrada. Sin embargo, <tt>dynamic_pack_is_fixpoint</tt> está construyendo internamente una lista enorme (via <tt>precomputeDisksFor</tt>). ¿Podría ser ese el problema? |
||
− | Let's turn the timing/memory stats on (":set +s" on ghci prompt) and try to peek into various elements of list returned by <tt>precomputeDisksFor</tt>: |
||
+ | |||
+ | 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 <tt>precomputeDisksFor</tt>: |
||
Prelude> :l cd-fit.hs |
Prelude> :l cd-fit.hs |
||
Line 1,015: | Line 973: | ||
Interrupted. |
Interrupted. |
||
− | Aha! |
+ | ¡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 <tt>700*1024*1024</tt>... |
+ | Modifiquemos un poco el código, para permitir alterar el tamaño del disco: |
||
− | Lets modify our code a bit, to allow disk size to be tweaked: |
||
<haskell> |
<haskell> |
||
Line 1,035: | Line 993: | ||
</haskell> |
</haskell> |
||
− | + | Compila una versión con soporte para medir el desempeño con <tt>ghc -O --make -prof -auto-all -o cd-fit cd-fit.hs</tt> y ejecútala así: |
|
$ ./cd-fit +RTS -p |
$ ./cd-fit +RTS -p |
||
OK, passed 100 tests. |
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. |
||
− | First thing, note that our code satisfies at least one simple property. Good. Now let's examine profile. Look into file "cd-fit.prof", which was produced in your current directory. |
||
+ | |||
+ | Seguramente vas a ver algo parecido a esto: |
||
− | Most probably, you'll see something like this: |
||
cd-fit +RTS -p -RTS |
cd-fit +RTS -p -RTS |
||
Line 1,063: | Line 1,022: | ||
main Main 180 1 0.0 0.0 0.0 0.0 |
main Main 180 1 0.0 0.0 0.0 0.0 |
||
− | Examine column of "individual %alloc". As we thought, all memory was |
||
− | allocated within <tt>precomputeDisksFor</tt>. However, amount of |
||
− | memory allocated (more than 700 mb, according to the line "total |
||
− | alloc") seems to be a little too much for our simple task. We will dig |
||
− | deeper and find where we a wasting it. |
||
+ | Examina la columna "individual %alloc". Como lo pensamos, toda la memoria ha sido ubicada dentro de <tt>precomputeDisksFor</tt>. 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. |
||
− | Let's examine memory consumption a little closer via so-called "heap |
||
− | profiles". Run <tt>./cd-fit +RTS -hb</tt>. This produces "biographical |
||
− | heap profile", which tells us how various parts of the memory were |
||
− | used during the program run time. Heap profile was saved to |
||
− | "cd-fit.hp". It is next to impossible to read and comprehend it as is, |
||
− | so use "hp2ps cd-fit.hp" to produce a nice PostScript picture which |
||
− | is worth a thousand words. View it with "gv" or "ghostview" or "full |
||
− | Adobe Acrobat (not Reader)". (This and subsequent pictures are |
||
− | '''not''' attached here). |
||
+ | Examinemos el consumo de memoria más de cerca empleando "heap profiles". Ejecuta <tt>./cd-fit +RTS -hb</tt>. 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í) |
||
− | Notice that most of the graph is taken up by region marked as "VOID". |
||
− | This means that memory allocated was never used. Notice that there is |
||
− | '''no''' areas marked as "USE", "LAG" or "DRAG". Seems like our |
||
− | program hardly uses '''any''' of the allocated memory at all. Wait a |
||
− | minute! How could that be? Surely it must use something when it packs |
||
− | to the imaginary disks of 50000 bytes those random-generated |
||
− | directories which are 10 to 1400 Mb in size.... Oops. Severe size |
||
− | mismatch. We should have spotted it earlier, when we were timing |
||
− | <tt>precomputeDisksFor</tt>. Scroll back and observe how each run |
||
− | returned the very same result - empty directory set. |
||
+ | 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 <tt>precomputeDisksFor</tt>. Regresa y observa cómo es que todas las ejecuciones regresan exactamente el mismo resultado - el conjunto vacío de directorios. |
||
− | Our random directories are too big, but nevertheless code spends time |
||
− | and memory trying to "pack" them. Obviously, |
||
− | <tt>precomputeDisksFor</tt> (which is responsible for 90% of total |
||
− | memory consumption and run time) is flawed in some way. |
||
+ | Nuestros directorios al azar son demasiado grandes, pero de todas formas el código consume tiempo y memoria intentando "empacarlos". Obviamente, <tt>precomputeDisksFor</tt> (que es responsable del 90% del consumo de tiempo y memoria) tiene algún error. |
||
− | Let's take a closer look at what takes up so much memory. Run |
||
− | <tt>./cd-fit +RTS -h -hbvoid</tt> and produce PostScript picture for |
||
− | this memory profile. This will give us detailed breakdown of all |
||
− | memory whose "biography" shows that it's been "VOID" (unused). My |
||
− | picture (and I presume that yours as well) shows that VOID memory |
||
− | comprises of "thunks" labeled "precomputeDisksFor/pre...". We could |
||
− | safely assume that second word would be "precomp" (You wonder why? |
||
− | Look again at the code and try to find function named "pre.*" which is |
||
− | called from inside <tt>precomputeDisksFor</tt>) |
||
+ | Miremos más de cerca qué consume tanta memoria. Ejecuta <tt>./cd-fit +RTS -h -hbvoid</tt> 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 <tt>precomputeDisksFor</tt>) |
||
− | This means that memory has been taken by the list generated inside |
||
− | "precomp". Rumor has it that memory leaks with Haskell are caused by |
||
− | either too little laziness or too much laziness. It seems like we have |
||
− | too little laziness here: we evaluate more elements of the list that |
||
− | we actually need and keep them from being garbage-collected. |
||
+ | 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. |
||
− | Note how we look up element from "precomp" in this piece of code: |
||
+ | |||
+ | Nota cómo buscamos elementos de "precomp" en esta porción de código: |
||
<haskell> |
<haskell> |
||
Line 1,121: | Line 1,045: | ||
+ | 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. |
||
− | Obviously, the whole list generated by "precomp" must be kept in |
||
− | memory for such lookups, since we can't be sure that some element |
||
− | could be garbage collected and will not be needed again. |
||
+ | Escribamos el código de nuevo para eliminar la lista: |
||
− | Let's rewrite the code to eliminate the list: |
||
<haskell> |
<haskell> |
||
-- Taken from 'cd-fit-4-4.hs' |
-- 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 |
||
− | -- Recursion base: best packed disk of size 0 is empty and best-packed |
||
+ | -- es vacío y el disco mejor empacado para una lista vacía de directorios |
||
− | -- disk for empty list of directories on it is also empty. |
||
+ | -- también es el vacío |
||
bestDisk 0 _ = DirPack 0 [] |
bestDisk 0 _ = DirPack 0 [] |
||
bestDisk _ [] = 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: |
||
− | -- comptued as follows: |
||
+ | |||
bestDisk limit dirs = |
bestDisk limit dirs = |
||
+ | -- Toma todos los directorios no vacíos que quepan por sí mismos en ese disco, |
||
− | -- Take all non-empty dirs that could possibly fit to that disk by itself. |
||
− | -- |
+ | -- 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: |
||
− | -- are not yet on our disk: |
||
case [ DirPack (dir_size d + s) (d:ds) | d <- filter ( (inRange (1,limit)).dir_size ) dirs |
case [ DirPack (dir_size d + s) (d:ds) | d <- filter ( (inRange (1,limit)).dir_size ) dirs |
||
, dir_size d > 0 |
, dir_size d > 0 |
||
Line 1,149: | Line 1,073: | ||
, d `notElem` ds |
, d `notElem` ds |
||
] of |
] 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 [] |
[] -> DirPack 0 [] |
||
− | -- |
+ | -- O creamos otros empacamientos diferentes, y seleccionamos el mejor de todos: |
packs -> maximumBy cmpSize packs |
packs -> maximumBy cmpSize packs |
||
Line 1,160: | Line 1,084: | ||
</haskell> |
</haskell> |
||
+ | 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: |
||
− | |||
− | Compile the profiling version of this code and obtain the overall |
||
− | execution profile (with "+RTS -p"). You'll get something like this: |
||
cd-fit +RTS -p -RTS |
cd-fit +RTS -p -RTS |
||
Line 1,182: | Line 1,104: | ||
bestDisk Main 183 200 0.0 0.1 0.0 0.1 |
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: |
||
− | We achieved the major improvement: memory consumption is reduced by factor |
||
− | of 700! Now we could test the code on the "real task" - change the |
||
− | code to run the test for packing the full-sized disk: |
||
<haskell> |
<haskell> |
||
Line 1,190: | Line 1,110: | ||
</haskell> |
</haskell> |
||
+ | 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. |
||
− | Compile with profiling and run (with "+RTS -p"). If you are not lucky |
||
− | and a considerably big test set would be randomly generated for your |
||
− | runs, you'll have to wait. And wait even more. And more. |
||
+ | 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). |
||
− | Go make some tea. Drink it. Read some Tolstoi (Do you have "War and |
||
− | peace" handy?). Chances are that by the time you are done with |
||
− | Tolstoi, program will still be running (just take my word on it, don't |
||
− | check). |
||
+ | 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 <tt>bestDisk</tt>. ¿Podemos mejorar de alguna forma el desempeño de <tt>bestDisk</tt>? |
||
− | If you are lucky, your program will finish fast enough and leave you |
||
+ | |||
− | with profile. According to a profile, program spends 99% of its time |
||
+ | Nota que <tt>bestDisk</tt> 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 <tt>bestDisk</tt> exactamente el mismo conjunto de directorios, aún cuando ya hemos "empacado" algunos. Arreglemos eso: |
||
− | inside <tt>bestDisk</tt>. Could we speed up <tt>bestDisk</tt> somehow? |
||
Note that <tt>bestDisk</tt> performs several simple calculation for |
Note that <tt>bestDisk</tt> performs several simple calculation for |
||
Line 1,218: | Line 1,133: | ||
</haskell> |
</haskell> |
||
+ | Recompila y ejecuta de nuevo. Los tiempos pueden ser prolongados, pero soportables, y el número de veces que llama a <tt>bestDisk</tt> (de acuerdo al perfil) debe disminuir significativamente. |
||
− | Recompile and run again. Runtimes could be lengthy, but bearable, and |
||
− | number of times <tt>bestDisk</tt> is called (according to the profile) |
||
− | should decrease significantly. |
||
+ | Finalmente, comparemos ambos algoritmos de empacado. Intuitivamente sentimos que el algoritmo voraz debe producir peores resultados, ¿o no?; hagamos pruebas para verificar: |
||
− | Finally, let's compare both packing algorithms. Intuitively, we feel |
||
− | that greedy algorithm should produce worse results, don't we? Lets put |
||
− | this feeling to the test: |
||
<haskell> |
<haskell> |
||
Line 1,232: | Line 1,143: | ||
</haskell> |
</haskell> |
||
+ | Ejecuta <tt>quickCheck</tt> con esta prueba varias veces para hacer la comparación. Yo siento que con esto concluyen nuestros ejercicios empacando la mochila. |
||
− | Verify that it is indeed so by running <tt>quickCheck</tt> for this |
||
− | test several time. I feel that this concludes our knapsacking |
||
− | exercises. |
||
+ | El lector con sed de aventura puede ir más lejos implementando "escalamiento" para <tt>dynamic_pack</tt>, 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). |
||
− | Adventurous readers could continue further by implementing so-called |
||
− | "scaling" for <tt>dynamic_pack</tt> where we divide all directory |
||
− | sizes and medium size by the size of the smallest directory to proceed |
||
− | with smaller numbers (which promises faster runtimes). |
||
− | == |
+ | == 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. |
||
− | We already mentioned monads quite a few times. They are described in |
||
− | numerous articles and tutorial (See Chapter 400). It's hard to read a |
||
− | daily dose of any Haskell mailing list and not to come across a word |
||
− | "monad" a dozen times. |
||
+ | 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. |
||
− | Since we already made quite a progress with Haskell, it's time we |
||
− | revisit the monads once again. I will let the other sources teach you |
||
− | theory behind the monads, overall usefulness of the concept, etc. |
||
− | Instead, I will focus on providing you with examples. |
||
+ | 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: |
||
− | Let's take a part of the real world program which involves XML |
||
− | processing. We will work with XML tag attributes, which are |
||
− | essentially named values: |
||
<haskell> |
<haskell> |
||
-- Taken from 'chapter5-1.hs' |
-- Taken from 'chapter5-1.hs' |
||
Line 1,261: | Line 1,159: | ||
</haskell> |
</haskell> |
||
+ | '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"): |
||
− | 'Name' is a plain string, and value could be '''either''' string or |
||
− | references (also strings) to another attributes which holds the actual |
||
− | value (now, this is not a valid XML thing, but for the sake of |
||
− | providing a nice example, let's accept this). Word "either" suggests |
||
− | that we use 'Either' datatype: |
||
<haskell> |
<haskell> |
||
type AttValue = Either Value [Reference] |
type AttValue = Either Value [Reference] |
||
Line 1,272: | Line 1,166: | ||
type Reference = String |
type Reference = String |
||
+ | -- Lista de atributos simples muestra: |
||
− | -- Sample list of simple attributes: |
||
simple_attrs = [ ( "xml:lang", Left "en" ) |
simple_attrs = [ ( "xml:lang", Left "en" ) |
||
, ( "xmlns", Left "jabber:client" ) |
, ( "xmlns", Left "jabber:client" ) |
||
, ( "xmlns:stream", Left "http://etherx.jabber.org/streams" ) ] |
, ( "xmlns:stream", Left "http://etherx.jabber.org/streams" ) ] |
||
+ | -- Lista de atributos muestra con referencias: |
||
− | -- Sample list of attributes with references: |
||
complex_attrs = [ ( "xml:lang", Right ["lang"] ) |
complex_attrs = [ ( "xml:lang", Right ["lang"] ) |
||
, ( "lang", Left "en" ) |
, ( "lang", Left "en" ) |
||
Line 1,286: | Line 1,180: | ||
</haskell> |
</haskell> |
||
+ | '''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. |
||
− | '''Our task is:''' to write a function that will look up a value of |
||
− | attribute by it's name from the given list of attributes. When |
||
− | attribute contains reference(s), we resolve them (looking for the |
||
− | referenced attribute in the same list) and concatenate their values, |
||
− | separated by semicolon. Thus, lookup of attribute "xmlns" form both |
||
− | sample sets of attributes should return the same value. |
||
+ | Siguiendo el ejemplo de <hask>Data.List.lookup</hask> de la biblioteca estándar, llamaremos a nuestra función <hask>lookupAttr</hask> que regresará <hask>Maybe Value</hask>, permitiendo manejar errores en la búsqueda: |
||
− | Following the example set by the <hask>Data.List.lookup</hask> from |
||
− | the standard libraries, we will call our function |
||
− | <hask>lookupAttr</hask> and it will return <hask>Maybe Value</hask>, |
||
− | allowing for lookup errors: |
||
<haskell> |
<haskell> |
||
-- Taken from 'chapter5-1.hs' |
-- Taken from 'chapter5-1.hs' |
||
lookupAttr :: Name -> [Attribute] -> Maybe Value |
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. |
||
− | -- provide default, "always-fail-with-runtime-error" function body. |
||
lookupAttr = undefined |
lookupAttr = undefined |
||
</haskell> |
</haskell> |
||
− | + | Intentemos escribir <hask>lookupAttr</hask> usando <hask>lookup</hask> de forma directa: |
|
− | a very straightforward way: |
||
<haskell> |
<haskell> |
||
Line 1,316: | Line 1,201: | ||
lookupAttr :: Name -> [Attribute] -> Maybe Value |
lookupAttr :: Name -> [Attribute] -> Maybe Value |
||
lookupAttr nm attrs = |
lookupAttr nm attrs = |
||
− | -- |
+ | -- Primero, buscamos 'Maybe AttValue' por nombre y |
− | -- |
+ | -- vemos si hemos tenido éxito: |
case (lookup nm attrs) of |
case (lookup nm attrs) of |
||
− | -- |
+ | -- Simplemente propaga el error. |
Nothing -> Nothing |
Nothing -> Nothing |
||
− | -- |
+ | -- Si el nombre existe, ver si es valor o referencia: |
Just attv -> case attv of |
Just attv -> case attv of |
||
− | -- |
+ | -- Es un valor; regrésalo. |
Left val -> Just val |
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 ] |
Right refs -> let vals = [ lookupAttr ref attrs | ref <- refs ] |
||
− | -- .. |
+ | -- ...luego, excluimos los errores |
wo_failures = filter (/=Nothing) vals |
wo_failures = filter (/=Nothing) vals |
||
− | -- ... |
+ | -- ...buscamos forma de sacar los datos del contenedor 'Just' |
stripJust (Just v) = v |
stripJust (Just v) = v |
||
− | -- ... |
+ | -- ...la usamos para extraer los resultados como cadenas |
strings = map stripJust wo_failures |
strings = map stripJust wo_failures |
||
in |
in |
||
− | -- ... |
+ | -- ...finalmente los combinamos en una sola cadena. |
− | -- |
+ | -- Si todas las búsquedas fallaron, debemos propagar un error. |
case null strings of |
case null strings of |
||
True -> Nothing |
True -> Nothing |
||
Line 1,344: | Line 1,229: | ||
</haskell> |
</haskell> |
||
+ | Probando: |
||
− | Testing: |
||
*Main> lookupAttr "xmlns" complex_attrs |
*Main> lookupAttr "xmlns" complex_attrs |
||
Line 1,352: | Line 1,237: | ||
*Main> |
*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: |
||
− | It works, but ... It seems strange that such a boatload of code |
||
− | required for quite simple task. If you examine the code closely, |
||
− | you'll see that the code bloat is caused by: |
||
+ | * el hecho de que verificamos si un error ocurrió después de cada paso |
||
− | * the fact that after each step we check whether the error occurred |
||
− | * |
+ | * sacar Strings de los constructores de datos <hask>Maybe</hask> y <hask>Either</hask> para 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? |
||
− | At this point C++/Java programmers would say that since we just pass |
||
− | errors upstream, all those cases could be replaced by the single "try |
||
− | ... catch ..." block, and they would be right. Does this mean that |
||
− | Haskell programmers are reduced to using "case"s, which were already |
||
− | obsolete 10 years ago? |
||
+ | ¡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 <hask>lookupAttr</hask> de forma que podamos tomar en cuenta posibles errores. |
||
− | Monads to the rescue! As you can read elsewhere (see section 400), |
||
− | monads are used in advanced ways to construct computations from other |
||
− | computations. Just what we need - we want to combine several simple |
||
− | steps (lookup value, lookup reference, ...) into function |
||
− | <hask>lookupAttr</hask> in a way that would take into account possible |
||
− | failures. |
||
+ | |||
− | Lets start from the code and dissect in afterwards: |
||
+ | Comencemos con el código y lo analizaremos luego: |
||
<haskell> |
<haskell> |
||
-- Taken from 'chapter5-2.hs' |
-- Taken from 'chapter5-2.hs' |
||
Line 1,379: | Line 1,254: | ||
lookupAttr' nm attrs = do |
lookupAttr' nm attrs = do |
||
− | -- |
+ | -- Buscamos 'AttValue' por nombre |
attv <- lookup nm attrs |
attv <- lookup nm attrs |
||
− | -- |
+ | -- Vemos si es valor o referencia |
case attv of |
case attv of |
||
− | -- |
+ | -- Es valor; lo regresamos |
Left val -> Just val |
Left val -> Just val |
||
− | -- |
+ | -- Es lista de referencias |
+ | -- Las buscamos, teniendo cuidado con los errores |
||
− | -- We have to look them up, accounting for |
||
− | -- |
+ | -- Buscamos todas las referencias... |
− | -- First, we will perform lookup of all references ... |
||
Right refs -> do vals <- sequence $ map (flip lookupAttr' attrs) refs |
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)) |
guard (not (null vals)) |
||
return (concat (intersperse ":" vals)) |
return (concat (intersperse ":" vals)) |
||
</haskell> |
</haskell> |
||
+ | '''Ejercicio''': compila el código, y prueba que <hask>lookupAttr</hask> y <hask>lookupAttr'</hask> de verdad funcionan igual. Trata de hacerlo escribiendo un a prueba QuickCheck, definiendo <hask>instance Arbitrary Name</hask> para que los nombres arbitrarios los tome de los nombres disponibles en <hask>simple_attrs</hask>. |
||
− | '''Exercise''': compile the code, test that <hask>lookupAttr</hask> |
||
+ | |||
− | and <hask>lookupAttr'</hask> really behave in the same way. Try to |
||
+ | 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? |
||
− | write a QuickCheck test for that, defining the |
||
− | <hask>instance Arbitrary Name</hask> such that arbitrary names will be taken from |
||
− | names available in <hask>simple_attrs</hask>. |
||
+ | Primero, date cuenta de que nunca verificamos si algún cálculo regresa <hask>Nothing</hask>. Aún así, trata de buscar un nombre de atributo que no exista, y <hask>lookupAttr'</haskell> va a regresar Nothing. ¿Cómo puede ser? El secreto está en el hecho de que el constructor de tipo <hask>Maybe</hask> es una "mónada". |
||
− | Well, back to the story. Noticed the drastic reduction in code size? |
||
− | If you drop comments, the code will occupy mere 7 lines instead of 13 |
||
− | - almost two-fold reduction. How we achieved this? |
||
+ | Empleamos la palabra clave <hask>do</hask> 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. |
||
− | First, notice that we never ever check whether some computation |
||
− | returns <hask>Nothing</hask> anymore. Yet, try to lookup some |
||
− | non-existing attribute name, and <hask>lookupAttr'</hask> will return |
||
− | <hask>Nothing</hask>. How does this happen? Secret lies in the fact |
||
− | that type constructor <hask>Maybe</hask> is a "monad". |
||
+ | Diferentes mónadas tienen diferente '''magia'''. El código de biblioteca dice que el constructor de tipo <hask>Maybe</hask>es una mónada en la que podemos usar <hask><-</hask> para "extraer" valores del contenedor <hask>Just</hask> y usar <hask>return</hask> para volver a meterlos en forma de <hask>Just some_value</hask>. Cuando pasamos de una acción a otra en el bloque "do" ocurre una verificación. Si la acción regresa <hask>Nothing</hask>, todos los cálculos de ahí en adelante serán omitidos y todo el bloque "do" regresará <hask>Nothing</hask>. |
||
− | We use keyword <hask>do</hask> to indicate that following block of |
||
− | code is a sequence of '''monadic actions''', where '''monadic magic''' |
||
− | have to happen when we use '<-', 'return' or move from one action to |
||
− | another. |
||
+ | Intenta hacer esto para entenderlo mejor: |
||
− | Different monads have different '''magic'''. Library code says that |
||
− | type constructor <hask>Maybe</hask> is such a monad that we could use |
||
− | <hask><-</hask> to "extract" values from wrapper <hask>Just</hask> and |
||
− | use <hask>return</hask> to put them back in form of |
||
− | <hask>Just some_value</hask>. When we move from one action in the "do" block to |
||
− | another a check happens. If the action returned <hask>Nothing</hask>, |
||
− | all subsequent computations will be skipped and the whole "do" block |
||
− | will return <hask>Nothing</hask>. |
||
− | Try this to understand it all better: |
||
<haskell> |
<haskell> |
||
*Main> let foo x = do v <- x; return (v+1) in foo (Just 5) |
*Main> let foo x = do v <- x; return (v+1) in foo (Just 5) |
||
Line 1,441: | Line 1,296: | ||
</haskell> |
</haskell> |
||
− | + | Por ahora no te fijes en <hask>sequence</hask> y <hask>guard</hask>; más tarde veremos esa parte. |
|
− | - we will get to them in the little while. |
||
+ | Como ya retiramos una razón para el exceso de código, es momento de atacar la otra. Nota que henos tenido que usar <hask>case</hask> para '''deconstruir''' el valor de tipo <hask>Either Value |
||
− | Since we already removed one reason for code bloat, it is time to deal |
||
+ | [Reference]</hask>. Seguramente no somos los primeros que tenemos que hacer esto, y que ese caso de uso debe ser muy común. |
||
− | with the other one. Notice that we have to use <hask>case</hask> to |
||
− | '''deconstruct''' the value of type <hask>Either Value |
||
− | [Reference]</hask>. Surely we are not the first to do this, and such |
||
− | use case have to be quite a common one. |
||
− | + | En efecto, hay un remedio simple para nuestro caso, y se llama <hask>either</hask>: |
|
− | <hask>either</hask>: |
||
*Main> :t either |
*Main> :t either |
||
either :: (a -> c) -> (b -> c) -> Either a b -> c |
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: |
||
− | Scary type signature, but here are examples to help you grok it: |
||
*Main> :t either (+1) (length) |
*Main> :t either (+1) (length) |
||
Line 1,466: | Line 1,316: | ||
*Main> |
*Main> |
||
+ | Parece que este es exactamente el caso. Reemplacemos <hask>case</hask> con una invocación a <hask>either</hask>: |
||
− | Seems like this is exactly our case. Let's replace the |
||
− | <hask>case</hask> with invocation of <hask>either</hask>: |
||
<haskell> |
<haskell> |
||
Line 1,481: | Line 1,330: | ||
</haskell> |
</haskell> |
||
+ | Se va poniendo mejor :) |
||
− | It keeps getting better and better :) |
||
+ | Ahora, como semi-ejercicio, intenta entender el significado de "sequence", "guard" and "flip" a partir de la siguiente sesión en ghci: |
||
− | Now, as semi-exercise, try to understand the meaning of "sequence", |
||
− | "guard" and "flip" looking at the following ghci sessions: |
||
*Main> :t sequence |
*Main> :t sequence |
||
Line 1,516: | Line 1,364: | ||
*** Exception: user error (stop here) |
*** Exception: user error (stop here) |
||
+ | Nota que para la mónada <hask>Maybe</hask> sequence continúa la ejecución hasta el primer <hask>Nothing</hask>. Se puede observar el mismo comportamiento para la mónada IO. ¡Toma en cuenta que la definición de <hask>sequence</hask> no incluye ese comportamiento! |
||
− | Notice that for monad <hask>Maybe</hask> sequence continues execution |
||
− | until the first <hask>Nothing</hask>. The same behavior could be |
||
− | observed for IO monad. Take into account that different behaviors are |
||
− | not hardcoded into the definition of <hask>sequence</hask>! |
||
− | + | Ahora, examinemos <hask>guard</hask>: |
|
*Main> let foo x = do v <- x; guard (v/=5); return (v+1) in map foo [Just 4, Just 5, Just 6] |
*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] |
[Just 5,Nothing,Just 7] |
||
+ | Como puedes ver, es solamente una forma simple de "detener" la ejecución cuando se cumple alguna condición. |
||
− | As you can see, it's just a simple way to "stop" execution at some |
||
+ | |||
− | condition. |
||
If you have been hooked on monads, I urge you to read "All About |
If you have been hooked on monads, I urge you to read "All About |
||
Line 1,589: | Line 1,434: | ||
Without you I would have stopped after Chapter 1 :) |
Without you I would have stopped after Chapter 1 :) |
||
+ | |||
+ | {{traduccion|titulo=Hitchhikers guide to Haskell}} |
||
+ | [[Category:Es/Tutoriales|Guía de Haskell para autoestopistas]] |
Latest revision as of 18:28, 11 June 2012
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 "asignació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 pintura, 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 informació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 nuestra 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ódigo, 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
Maybe
yEither
para 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 Maybe
es 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