Hacé un programa que lee un archivo de texto, e imprime su contenido en la salida estándar.
Modificalo para que haga lo mismo pero pasando todos los carácteres a mayúsculas (usando la función toUpper del módulo Data.Char.
Vamos a hacer un programa que hace un poco más de procesamiento de datos.
La idea es hacer un programa que lee un archivo de texto y muestre las 10 palabras más frecuentes.
Como archivos de texto pueden bajar libros desde proyecto Gutenberg (https://www.gutenberg.org/) en formato .txt. Por ejemplo Guerra y Paz de Leo Tolstoy tiene suficiente contenido para que tengamos resultados interesantes.
Se puede dividir el trabajo en 3 partes:
leer el contenido del archivo como una lista de palabras
contar cuantas veces aparecen cada palabra
ordenar las palabras de más frecuente a menos frecuente, y mostrar las 10 más frecuentes
Para implementar el paso 2, vamos a usar la estructura de datos Map (diccionario) de Data.Map.Strict, porque es una estructura optimizada que puede soportar grandes cantidades de datos. Más precisamente, la idea es guardar las palabras y su número de ocurrencias en un diccionario de tipo Map String Int.
Pasos:
Importá los módulos Data.Map.Strict y Data.List dándoles un prefijo para cada uno para evitar colisiones de nombres (ver “import qualified” en Aprende Haskell). Definí una función main que lee el contenido de un “input.txt” y define las palabras como una lista de Strings.
Definí una función agregar :: Map String Int -> String -> Map String Int que agrega una palabra a un diccionario (posiblemente el diccionario ya tiene la palabra!). Fijate (en Hoogle) en la documentación de Data.Map.Strict qué función(es) te puede(n) ayudar para definir agregar.
Modificá el main para agregar a un diccionario vacío (buscar en Data.Map.Strict) todas las palabras del archivo (¿qué función de orden superior permite hacer eso?).
Definí la función top10 :: Map String Int -> [(Int, String)] tal que top 10 m sean las 10 palabras más frecuentes del diccionario m. Definir top10 requiere (entre otras cosas) ordenar una lista. Fijate en el módulo Data.List qué función(es) puede(n) ser útil(es) para eso.
Imprimí el top 10 de las palabras del archivo en la salida estándar.
Después de terminar cada paso podés mostrar en la salida estándar lo que llegaste a definir, por ejemplo usando la función show en combinación con putStrLn.
Podés mejorar el programa implementando tu propia función que corta una String en lista de palabras, tomando en cuenta la puntuación, para mejorar la precisión del programa. Por ejemplo, no te sirve que tu programa cree que “Hola,” (con la coma) es una palabra; tampoco te sirve que “Hola” y “hola” sean consideradas como dos palabras distintas.
Hackeo en el Banco Haskell
Instalación
Vas a necesitar 2 bibliotecas que no son parte de la libreria estándar de Haskell para este proyecto. Son aeson y text. Se pueden instalar con cabal update ; cabal install aeson text, o si no tenés cabal pero stack, con stack update ; stack install aeson text.
Este proyecto involucra analisar (“parsear”) y luego buscar información dentro de un archivo JSON. JSON es un formato de intercambio de datos internacionalmente estandardizado que es fácil de leer y de escribir. Ve <json.org> para más detalles, pero no hace falta que sepas mucho para este proyecto. ¡La biblioteca aeson te va a hacer todo el trabajo!
Lo que sí hay que hacer, es asegurarnos que nuesto programa Haskell pueda encontrar los archivos JSON. Poner los archivos en la misma capeta que tu módulo Haskell es un buen principio, pero a veces no basta. Si tenés problemas para hacer que tu código encuentre tu archivo y que estás usando GHCi, podés probar :!pwd. Esto va a mostrar la carpeta actual donde GHCi piensa que está. (El prefijo :! sirve para ejecutar comandos arbitrarios en GHCi).
Si los archivos JSON no están en la carpeta indicada, hay dos opciones. O los podés mover ahí, o podés usar :cd para que GHCi cambie de carpeta actual. (:cd es un comando de GHCi, la falta de ! es a propósito).
Teórico sobre las String
El tipo String que provee Haskell es un poco… tonto. Por supuesto, es práctico al nivel programación de pensar las Strings como listas de carácteres, pero es una manera pésima de almacenar pedazos de texto en la memoria de una computadora. Existen otras representaciones de pedazos de texto disponibles. En este proyecto vamos a usar una representación que se llama ByteString.
La biblioteca ByteString usa muchos nombres de funciones iguales a los del Prelude y de Data.List. Si hacés un simple import de Data.ByteString, vas a tener un montón de conflictos de nombres en tu código. Entonces vamos a usar la sintaxis import qualified ... as BS, que significa que cada uso de una función o tipo sobre ByteString (incluso los operadores) debe ser prefijado con BS. Por ejemplo, para tener el tamaño de una ByteString, hay que escribir BS.length.
Las ByteStrings vienen en distintons “modelos”, según si son perezosas o estrictas, o qué tipo de codificación usan internamente. Para este proyecto, vamos a usar ByteStrings perezosas (lazy).
Cuando trabajamos con cadenas de carácteres que no son String, es muy práctico seguir usando la sintaxis " ... " (entre comillas) para escribir valores. Por lo cual GHC provee la extensión OverloadedStrings. Esto funciona como los números sobrecargados, en el sentido que cada uso de "blah" es convertido en una llamada a fromString "blah", donde fromString es una función de la clase de tipos IsString (es un poco el equivalente de Num pero para cadenas de carácteres).
Se puede entonces crear valores de cualquier tipo que tiene una instancia de IsString con la sintaxis " ... ". Por supuesto, ByteString está en la clase IsString, tal como String.
Una consecuencia de OverloadedStrings es que a veces GHC no sabe qué tipo de cadena de carácteres queremos, entonces necesitamos escribir una anotación de tipo. En general, no tenemos que preocuparnos acerca de OverloadedStrings cuando escribimos código para este proyecto, pero esta explicación sirve para ayudarles si se encuentran con mensajes de error extraños. Para usar OverloadedStrings en GHCi basta escribir :set -XOverloadedStrings.
Finalmente, no como las Strings, que son secuencias de carácteres Unicode, las ByteStrings son secuencias de carácteres 8-bits tradicionales. El tipo de un carácter 8-bit en Haskell es Word8, que es básicamente un entero sin signo de 8 bits. Esto es a doble hilo. Por un lado, no podemos usar constantes como 'a' cuando manejamos ByteStrings (aunque, podemos usar la sintaxis "..." como visto más arriba). Por otro lado, los Word8 son instancias de Num e Integral, entonces podemos usar nuestras funciones numéricas favoritas sobre ellos.
¡Pánico en el Banco Haskell!
¡El Banco Haskell está en alerta! ¡Alguien hackeó el sistema explotando un uso descuidado de head! El Banco Haskell, desde ese momento, ha resforzado su sistema. Sin embargo, el delincuente pudo iniciar una serie de transacciones entre clientes. Te contrataron para encontrar quién hackeó el Banco Haskell y qué transacciones tienen que ser revertidas para que todos los clientes recuperen su dinero.
Por suerte, pudiste recuperar ciertos archivos que contienen pistas sobre quién hackeó el banco. Estos archivos se encuentran en clues.zip. En los ejercicios siguientes, vas a extraer los datos de esos archivos y usar las pistas para agarrar al perpetrador.
Ejercicio 1
El delincuente guardó una lista de los identificadores de transacción que inició. Lamentablemente, esa lista es encriptada, y el delincuente escondió la clave de encripción en una adorable foto de perro, dog.jpg. Algunos de los bytes de la imagen fuero XOR-eados con un mensaje secreto. Para extraer el mensaje, necesitás hacer un XOR de los bytes de la imagen alterada con la imagen original, y quitar todos los bytes que valen 0 después de esa operación. Después de una búsqueda Google, pudiste encontrar la imagen original, dog-original.jpg.
Ahora, tenés que implementar la función:
getSecret ::FilePath->FilePath->IOByteString
Vas a tener que usar la función xor del módulo Data.Bits. Recordá que FilePath es simplemente un sinónimo de String.
(Indicación: buscá la documentación del módulo Data.Bytestring.Lazy y Data.Bits.)
Ejercicio 2
Ahora que tenés la clave de encripción, podés decifrar la lista de identificadores de transacciones falsas. Esta lista es contenida en victims.json.enc.
Los datos son cifrados usando un esquema similar al Cifrado de Vigenère. Para descifrarlos, simplemente hay que XOR-ear el texto cifrado con la clave. Vas a tener que repetir la clave porque es mucho más corta que el texto cifrado.
Implementá la función:
decryptWithKey ::ByteString->FilePath->IO ()
Esta función debe leer el archivo cifrado, y decifrarlo usando la clave, luego escribirlo en otro archivo. El parámetro ByteString es la clave y el FilePath es el camino al archivo que debe ser escrito (no tiene que existir). El archivo cifrado tiene el mismo camino pero con “.enc” agregado al final.
Ejercicio 3
Ahora tenemos una lista de identificadores de transacciones falsas, pero eso no te dice quién es el delincuente ni cuánta plata robó. Por suerte, el Banco Haskell nos proveyó una lista de todas las transacciones que ocurrieron mientras el hacker estaba en el sistema.
Esta lista en formato JSON se encuentra en el archivo transactions.json (este archivo no está cifrado). El Banco Haskell también nos proveyó el módulo de parseo que usa para convertir datos entre los tipos Haskell y ByteStrings JSON. Este módulo usa la biblioteca aeson, se encuentra en Parser.hs y exporta dos funciones:
encode ::ToJSON a => a ->ByteStringdecode ::FromJSON a =>ByteString->Maybe a
También define instancias FromJSON y ToJSON para el tipo de datos Transaction. Las instancias para [Transaction] son proveidas automáticamente por aeson.
Esto significa que podés usar decode para parsear la lista de transacciones en transactions.json. Los datos en victims.json son solo una lista de cadenas de carácteres. aeson sabe como parsear eso sin usar una instancia especial. Podés entonces usar una función polimórfica para parsear estos dos archivos.
Definí la función:
parseFile ::FromJSON a =>FilePath->IO (Maybe a)
Esta función debe tomar el camino a un archivo e intentar parsearlo como formato JSON, en un valor de tipo a.
Observación: para probar en GHCi, necesitás indicar qué debe ser el tipo de salida. Por ejemplo, parseFile "victims.json" va a devolver Nothing, pero parseFile "victims.json" :: IO (Maybe [TId]) te va a devolver lo que buscás.
Ejercicio 4
Ahora sos capaz de parsear tus archivos JSON, entonces podés empezar a buscar pistas. El primer paso consiste en aislar las transacciones malas.
Esta función toma el camino a la lista de víctimas, luego el camino a los datos de transacciones, y devuelve solo las transacciones que ocurren en la lista de víctimas.
Ejercicio 5
Ahora que has decifrado y parseado todo los datos, es hora de hacer un trabajo de investigación. Para encontrar quién es el delincuente, tenés que seguir la ruta del dinero formada por esas transacciones.
Hay una forma muy simple de hacer eso. Para cada nombre, mantener un registro de cuánto dinero esa persona ganó (o perdió) como resultado de esas transacciones. Vas a necesitar alguna forma de asociar gente (String) con cantidad de dinero (Integer). Para hacerlo eficientemente, implentá la función:
getFlow :: [Transaction] ->MapStringInteger
Por ejemplo:
let ts = [ Transaction { from = "Haskell Curry"
, to = "Simon Peyton Jones"
, amount = 10
, tid = "534a8de8-5a7e-4285-9801-8585734ed3dc"
} ]
in getFlow ts == fromList [ ("Haskell Curry", -10)
, ("Simon Peyton Jones", 10)
]
Observación: el módulo Data.Map.Strict es importado de manera “qualified”, por lo cual tenés que prefijar todo con Map. Por ejempo, el diccionario vacío es Map.empty.
Ejercicio 6
Con un Map conteniendo información sobre el flujo de dinero, podés fácilmente encontrar quién es el delincuente; es la persona que colectó más dinero. Definí la función:
getCriminal ::MapStringInteger->String
Esta funcion debe tomar el diccionario del flujo de dinero y devolver el nombre de la persona que recibió más dinero.
Ejercicio 7
Para devolver su dinero a todo el mundo, el Banco Haskell te pidió que uses los datos de los flujos de dinero para generar una nueva lista de transacciones que revertirá las transferencias hechas por el hacker.
Para cubrir sur huellas, el hacker movió dinero a través de cuentas intermedias, no lo virtió simplemente todo en su cuenta. Revertir todas esas transacciones va a resultar en mucho más transacciones que necesarias. En lugar de hacer eso, vas a implementar el algoritmo siguiente:
separar a la gente entre deudores y perjudicados; es decir, entre la gente que terminó con plata de más y la que perdió plata.
ordernar los dos grupos en orden descendiente. Los deudores que deben más, y los perjudicados a quiénes les deben más deben llegar primeros. Probablemente vas a beneficiar de la función sortBy del módulo Data.List…
iterar sobre los deudores y los perjudicados en paralelo. Para cada par, generar una nueva Transaction donde el deudor paga al perjudicado el min entre lo que debe el deudor y lo que se debe al perjudicado. Deducir este monto de los dos, y sacar a quien pagó completamente su deuda o fue completamente compensado, y repetir.
(Este algoritmo no es óptimo en cantidad de transacciones producidas, pero produce solo O(n) transacciones para n personas.)
El primer argumento es el diccionario de flujo del dinero, y el segundo argumento es una lista de nuevos identificadores de transacciones que deberiamos usar para crear nuevas Transactions.
El Banco Haskell te proveyó generosamente una lista de nuevos identificadores de transacciones que podemos usar. Podés cargar esta lista, pero para probar la función es suficiente usar (repeat "") como lista de TId.
Ejercicio 8
Para entregar tus hallazgos al Banco Haskell, necesitás escribir los datos en formato JSON. Implementá la función:
writeJSON ::ToJSON a =>FilePath-> a ->IO ()
Ejercicio 9
¡Llegó la hora de juntar todo! La función main ya es definida para que puedas compilar el archivo en un ejecutable que va a automatizar todo el proceso.
Recordá que en Haskell, el tipo de main es:
main ::IO ()
Esto difiere de otros lenguajes donde la función main toma como parámetros argc y argv. En Haskell, cuando queremos conseguir los argumentos en línea de comando, tenemos que usar la función getArgs del módulo System.Environment. El ejecutable tomara los caminos de la foto de perro original, la foto alterada, el archivo de transacciones, la lista de víctimas (incluso si todavía no fue creada), la lista de nuevos identificadores de transacciones, y el camino de archivo de salida, en este orden como argumentos.
Si estos argumentos no son proveidos, por defecto toman los valores de los archivos del archivo clues.zip. La salida por defecto es new-transactions.json.
El programa debe extraer la clave de encripción de la imagen de perro, decodificar la lista de víctimas y escribirla en un archivo nuevo, escribir las transacciones nuevas a un archivo JSON, e imprimir el nombre del hacker.
Como este proyecto va a ser escrito en un módulo que no se llama Main, tenés que usar un flag para decirle a GHC que debe generar un ejecutable. Compilá con:
ghc Banco.hs -main-is Banco
¡Finalmente, ejecutá ./Banco para descubrir quién hackeó el Banco Haskell!
Monad
Preparación
Archivo para bajar y agregar definiciones de funciones:
Instalá los paquetes HUnit y QuickCheck usando cabal update ; cabal install hunit quickcheck, o stack update ; stack install hunit quickcheck.
Mónadas Maybe y listas
Acabamos de aprender sobre mónadas y comprensiones de listas. Los ejercicios que siguien son una oportunidad para ver que hemos aprendido. Son relativamente simples.
Ejercicio 1
Escribí una función que detecta si una String tiene cierto formato. El formato requerido es el siguiente:
La string empieza con un dígito.
Llamemos n el valor de ese dígito. La string contiene luego n caracteres 'a'.
Después de las 'a', o la string se termina, o la secuencia se repite, empezando con un dígito (puede ser distinto).
Ejemplos:
Buenas strings
Malas strings
3aaa2aa
3aaa2a
9aaaaaaaaa
10aaaaaaaaaa
0
1
001a
100a
2aa2aa
2bb2bb
Tu función debe usar la mónada Maybe. Debería parecerse a esto:
stringFitsFormat ::String->BoolstringFitsFormat = isJust . gowhere go ::String->MaybeString-- go evalua a Just "" si es exitosa, sino a Nothing...
Ayuda: usá readMaybe :: Read a => String -> Maybe a de Text.Read y stripPrefix :: Eq a => [a] -> [a] -> Maybe [a] de Data.List.
