Polinomios

Preparación

Bajá el archivo pre-llenado: Poly.hs.

¿Qué es un número?

Parece una pregunta profunda y filosófica, pero el sistema de tipos de Haskell nos da una respuesta simple: un número es cualquier tipo que tiene una instancia de la clase de tipos Num. Veamos la definición de Num:

class Num a where
    (+), (-), (*)  :: a -> a -> a
    negate         :: a -> a
    abs            :: a -> a
    signum         :: a -> a
    fromInteger    :: Integer -> a

Entonces, para Haskell, un número es simplemente algo que puede ser sumado, restado, multiplicado, negado, etc. (La división no es parte de la clase Num a propósito, dado que es definida de manera distinta para los enteros y los flotantes.) El Prelude de Haskell viene con varias instancias de Num que ya conocemos. Incluyen los sospechosos de siempre: Int, Integer, Float y Double. Pero la diversión no termina acá. Podemos definir nuestros propios números, del momento que podemos proveer definiciones sensatas para las operaciones numéricas básicas.

¿Un polinomio puede ser un número?

¡Cómo no! Los polinomios pueden sumarse, restarse y multiplicarse como cualquier otro número. En estos ejercicios, vamos a escribir una instancia de Num para un tipo de polinomios que definimos nosotros.

Pensemos en como definir ese tipo. Un polinomio es simplemente una secuencia de términos, y cada término tiene un coeficiente y un grado. Por ejemplo, el polinomio x² + 5x + 3 tiene tres términos, uno de grado 2 con coeficiente 1, uno de grado 1 con coeficiente 5, y uno de grado 0 con coeficiente 3.

Vamos a evitar de especificar explicitamente los grados, y vamos a representar un polinomio como una lista de coeficientes, cada uno teniendo un grado igual a su posición en la lista. Vamos a permitir que el tipo de los coeficientes sea polimórfico, así podemos tener coeficientes que sean de tipo Int, Double, etc.

data Poly a = P [a]

En esta representación, el polinomio x² + 5x + 3 se escribe P [3, 5, 1].

Ejercicio 1

Observamos que nuestro tipo Poly a no deriva las clases Eq y Show. ¡Hay una excelente razón para eso! Las instancias por defecto de esas clases de tipo no funcionarían tal como quisieramos.

En este ejercicio, vamos a escribir una instancia de la clase Eq para el Poly a. Si hubieramos derivado esa instancia, Haskell simplemente compararía las listas dentro del constructor P. Pensemos en porqué esto no alcanza. ¿Cuándo es el caso que dos Poly son equivalentes, pero sus representaciones en lista no lo son?

Implementá la función (==). Acordate que no es necesario implementar explicitamente la función (/=); tiene una implementation por defecto en términos de (==). Ejemplos:

P [1, 2, 3] == P [1, 2, 3]
P [1, 2] /= P [1, 2, 3]

Algunas funciones útiles pueden ser takeWhile, dropWhile, reverse …

Ejercicio 2

La instancia por defecto de Show muestra simplemente valores tal como están escritos en Haskell. Sería mucho mejor si un Poly a como P [1, 2, 3] pudiera ser mostrado de manera más legible por un humano, como 3x^2 + 2x + 1.

Una instancia completa del tipo Show tendrá las características siguientes:

• los términos son mostrados como cx^e donde c es el coeficiente y e es el exponente. Si e es 0, entonces se muestra solo el coeficiente. Si e es 1, entonces el formato es simplemente cx.
• los términos son separados por el símbolo + con un solo espacio de cada lado
• los términos son listados en orden decreciente de grado
• los términos que tienen coeficiente 0 no se muestran, salvo si el polinomio es igual a 0
• ningún coeficiente se muestra para un término cuyo coeficiente es 1, (o sea x en lugar de 1x), salvo si su grado es 0
• ningún tratamiento especial es necesario para los términos con coeficiente negativo. Por ejemplo, 2x^2 + -3 es la representación correcta de 2x² − 3.

Implementá la función show según esta especificación. Ejemplos:

show (P [1, 0, 0, 2]) == "2x^3 + 1"
show (P [0, -1, 2]) == "2x^2 + -x"

Algunas funciones útiles pueden ser: zip, reverse, intercalate (del módulo Data.List)…

Ejercicio 3

Ahora vamos a definir la suma para el tipo Poly a.

La suma para polinomios es bastante simple, todo lo que tenemos que hacer es sumar los pares de coeficientes para cada grado de los dos polinomios. Por ejemplo, (x² + 5) + (2x² + x + 1) = 3x² + x + 6.

Se considera como buen estilo Haskell definir las funciones importantes fuera de la instancia de clase de tipo. Por esa razón, vamos a escribir la función plus que suma dos valores de tipo Poly a:

plus :: Num a => Poly a -> Poly a -> Poly a

Observamos que el protótipo de plus indica la restricción que a tiene una instancia Num. Esto significa que solo podemos sumar polinomios que tienen coeficientes numéricos.

Como a tiene que ser un Num, podemos usar todas las funciones Num usuales (i.e., (+)) sobre los coeficientes de los polinomios. Ejemplos:

P [5, 0, 1] + P [1, 1, 2] == P [6, 1, 3]
P [1, 0, 1] + P [1, 1] == P [2, 1, 1]

Definí la función plus.

Ejercicio 4

En este ejercicio vamos a implementar la multiplicación de polinomios. Para multiplicar dos polinomios, cada término del primer polinomio debe ser multiplicado por cada término del segundo. La manera más simple de lograr esto es de construir un [Poly a] donde cada elemento es el polinomio que resulta de la multiplicación de un solo coeficiente en el primer polinomio por cada coeficiente en el segundo.

Dado que los términos no dicen explicitamente sus exponentes, vamos a tener que desplazar la salida antes de multiplicarla por cada coeficiente consecutivo. Por ejemplo, P [1, 1, 1] * P [2, 2] va a producir la lista [P [2, 2], P [0, 2, 2], P [0, 0, 2, 2]].

Luego, podemos simplemente sumar esta lista. La función sum de Haskell es definida en términos de (+), pero también utiliza el literal numérico 0. Si queremos usar la función sum entonces tenemos que implementar la función fromInteger en la instancia de Num para Poly a primero (lo vamos a hacer en el próximo ejercicio de todos modos).

Sino, podemos también usar foldr (+) (P [0]) en lugar de sum hasta que implementemos fromInteger

Implementá la función:

times :: Num a => Poly a -> Poly a -> Poly a

Ejemplo:

P [1, 1, 1] * P [2, 2] == P [2, 4, 4, 2]

Ejercicio 5

Ya llegó la hora de completar nuestra definición de la instancia Num para los polinomios. Las funciones (+) y (*) ya fueron completadas en los ejercicios anteriores. Solo necesitamos implementar dos funciones más.

La primera función que vamos a implementar es negate. Esta función debe devolver la negación de un Poly a. En otros términos, el resultado de negar todos sus términos.

negate :: Num a => Poly a -> Poly a

Ejemplo:

negate (P [1, 2, 3]) == P [-1, -2, -3]

Definí negate.

De paso, la clase de tipo Num tiene una implementación por defecto de (-) en términos de (+) y negate, entonces no tenemos que implementarla.

Luego, implementá fromInteger. Esta función debe tomar un Integer y devolver un Poly a. Un entero (o cualquier número estándar) se puede ver como un polinomio de grado 0. Acordémonos que tenemos que convertir ese Integer a un valor de tipo a antes de poder usarlo como coeficiente en un polinomio.

fromInteger :: Num a => Integer -> Poly a

La clase de tipo Num tiene dos funciones más que no tienen realmente sentido para los polinomios (capaz que los polinomios no son números, después de todo…). Esas funciones son absy signum. Las vamos a dejar como undefined dado que el valor absoluto de un polinomio no es un polinomio, y los polinomios no tienen realmente un signo.

Ejercicio 6

Ahora queremos poder escribir expresiones como 3x^2 + x^2 + 8, y que sea interpretado como polinomio por Haskell, directamente.

Primero necesitamos hacer un truco para que x sea interpretado como esperamos. Considerá el protótipo siguiente:

x :: Num a => Poly

Agregá la definición correspondiente para que x sea el polinomio x.

A esta altura, con todo lo que hiciste, el polinomio x² + 5x + 3 se puede escribir x^2 + 5*x + 3 porque los valores x, 5 y 3 son todos valores válidos del tipo Poly Int, y definiste (+) y (*) como parte de la instancia Num para polinomios.

Podés ver que ahora se puede usar (^) para la exponenciación, por más que no lo hayas implementado. En Haskell, (^) es definido en términos de (*), por lo cual viene “gratis”.

Para terminar, definí la función applyP que aplica un Poly a a un valor de tipo a:

applyP (x^2 + 2*x + 1) 1 == 4
applyP (x^2 + 2*x + 1) 2 == 9

Analizador de Logs

¡Algo terrible pasó con nuestros servidores!

• Vas a necesitar los archivos: Log.hs, error.log, sample.log
• Tenés que editar tus respuestas en un archivo llamado LogAnalysis.hs

Parsear archivos de depuración

No sabemos bien lo que pasó, pero hemos logrado encontrar el archivo de depuración error.log. Parece que está constituido de un mensaje de depuración en cada línea. Cada línea empieza con un carácter que indica el tipo de mensaje que representa:

• ’I’ para mensajes informativos,
• ’W’ para advertencias (warnings)
• ’E’ para errores.

Además, las líneas de mensajes de error tienen un valor entero que indica la gravedad del error, con 1 siendo el tipo de error que podés dejar para el próximo verano, y 100 siendo una falla épica y total. Luego, todos los tipos de mensajes de depuración tienen una marca de tiempo (bajo la forma de un número entero) seguida del contenido textual hasta el fin de la línea.

Este es un extracto del archivo de depuración, que incluye un mensaje informativo seguido de un mensaje de error de nivel 2:

I 147 mice in the air, I’m afraid, but you might catch a bat, and
E 2 148 #56k istereadeat lo d200ff] BOOTMEM

Está todo un poco confuso; claramente necesitamos un programa para ordenar este lío. Hemos encontrado algunos tipos de datos que capturan la estructura del formato de archivo de depuración:

data MessageType = Info
                 | Warning
                 | Error Int
  deriving (Show, Eq)

type TimeStamp = Int

data LogMessage = LogMessage MessageType TimeStamp String
  deriving (Show, Eq)

(Las anotaciones deriving (Show, Eq) permiten que estos tipos sean impresos en una sesión GHCi y permiten comparaciones de igualdad entre valores de esos tipos.)

Te proveemos un módulo Log.hs que contiene estas declaraciones de tipos de datos, con algunas funciones útiles. Descargá Log.hs y ponelo en la misma carpeta donde vas a poner tu propio módulo LogAnalysis.hs. Las primeras líneas de LogAnalysis.hs deberían ser las siguientes:

{-# OPTIONS_GHC -Wall #-}
module LogAnalysis where
import Log

Sirven para declarar que el archivo es un módulo llamado LogAnalysis, e importa el módulo almacenado en Log.hs para que puedas usar sus tipos y funciones.

Un consejo para lo que sigue: ¡no vuelvas a inventar la rueda! Usá funciones de Prelude para hacer que tu solución sea la más concisa, alto nivel y funcional posible. Entre las funciones que te pueden servir están lines, words, unwords, take, drop, (.), map y filter.

Ejercicio 1

El primer paso consiste en encontrar como analizar un mensaje individual. Puede ser que el archivo esté corrupto y que algunas líneas individuales estén inutilizables. Entonces, no podemos estar seguros que una línea de la entrada va a ser un LogMessage válido. Por lo cual vamos a definir un tipo (proveido en Log.hs) que permita la posibilidad de una falla:

data MaybeLogMessage = ValidLM LogMessage
                     | InvalidLM String
  deriving (Show, Eq)

Como podés ver, un MaybeLogMessage contiene o un LogMessage válido, o una string sin formato.

Ahora, podés definir una función:

parseMessage :: String -> MaybeLogMessage

que parsea una línea individual del archivo de depuración. Por ejemplo:

parseMessage "E 2 562 help help"
    == ValidLM (LogMessage (Error 2) 562 "help help")
parseMessage "I 29 la la la"
    == ValidLM (LogMessage Info 29 "la la la")
parseMessage "This is not in the right format"
    == InvalidLM "This is not in the right format"

Hay una función muy útil al final de Log.hs que vas a necesitar acá.

Ejercicio 2

No es muy difícil de hacer funcionar parseMessage sobre todas las líneas de un archivo. Pero, hacerlo produciría un [MaybeLogMessage], mientras en realidad queremos solo un [LogMessage] para seguir procesando más. Así que tiremos los mensajes inválidos. Definí una función:

validMessagesOnly :: [MaybeLogMessage] -> [LogMessage]

que descarta los mensajes inválidos.

Ejercicio 3

Ahora, podemos juntar los pedazos para definir

parse :: String -> [LogMessage]

que analiza un archivo de depuración entero de una sola vez, y devuelve los contenidos como una lista de LogMessages.

Para probar tu función, usá la función testParse proveida en el módulo Log, dándole como parámetro tu función parse, la cantidad de líneas que hay que parsear, y el archivo de depuración de donde hay que parsear (que debería también estar en la misma carpeta que tu propio módulo). Por ejemplo, después de cargar tu módulo en GHCi, tipeá algo como lo siguiente:

testParse parse 10 "error.log"

Poner los mensajes en orden

Lamentablemente, como los mensajes de error fueron generados por varias fallas de servidores en distintas ubicaciones del mundo (una tormenta eléctrica, un disco duro fallido, y un programador aburrido pero incompetente), los mensajes de error están horriblemente desordenados. Hasta que no ordenemos un poco, no habrá forma de entender qué pasó.

Ejercicio 4

Cualquier función de ordenamiento va a tener que comparar dos LogMessages para ver cuál debería venir primero. Pero, como acabamos de crear el tipo LogMessage, no hay forma para la computadora de saber como compararlos. ¡Tenemos que escribir una función de comparación! En general, comparar dos elementos para ordenamiento puede producir uno de los tres resultados siguientes: menor-a, igual-a o mayor-a. Haskell representa esta idea como un tipo de datos:

data Ordering = LT | EQ | GT

Ordering es parte de Prelude (el conjunto de cosas que se incluyen automáticamente), entonces su definición no aparece en Log.hs y tampoco tiene que aparecer en tu código.

Definí una función

compareMsgs :: LogMessage -> LogMessage -> Ordering

que compara dos LogMessages según su fecha.

Ahí van unos ejemplos:

compareMsgs (LogMessage Warning 153 "Not a speck of light is showing, so the danger must be growing...")
(LogMessage Info 208 "the Weighted Companion Cube cannot talk")
  == LT

compareMsgs (LogMessage (Error 101) 2001 "My God! It’s full of stars!")
(LogMessage Info 2001 "Daisy, Daisy, give me your answer do.")
  == EQ

Ejercicio 5

Ahora que expresaste cómo comparar mensajes, podés ordenar la lista. Definí una función

sortMessages :: [LogMessage] -> [LogMessage]

que ordena la lista de mensajes. ¡No implementes un algoritmo de ordenamiento! Mejor fijate en el módulo Data.List, hay una función muy práctica.

Autopsia del archivo de depuración

Ejercicio 6

Ahora que podemos ordenar los mensajes de depuración, la única cosa que queda para hacer es extraer la información relevante. Hemos decidido que “relevante” significa “errores con gravedad de al menos 50”.

Definí una función

whatWentWrong :: [LogMessage] -> [String]

que toma una lista no ordenada de LogMessages, y devuelve una lista de los mensajes correpondiendo a cualquier error con una gravedad de 50 o más, ordenados por fecha. (Por supuesto, podés usar tus funciones de los ejercicios anteriores para hacer el ordenamiento.)

Por ejemplo, suponé que nuestro archivo de depuración se parezca a esto:

I 6 Completed armadillo processing
I 1 Nothing to report
E 99 10 Flange failed!
I 4 Everything normal
I 11 Initiating self-destruct sequence
E 70 3 Way too many pickles
E 65 8 Bad pickle-flange interaction detected
W 5 Flange is due for a check-up
I 7 Out for lunch, back in two time steps
E 20 2 Too many pickles
I 9 Back from lunch

Este archivo es proveido como sample.log. Hay cuatro errores, tres de las cuales tienen una gravedad mayor a 50. La salida de whatWentWrong sobre sample.log debería ser:

[ "Way too many pickles"
, "Bad pickle-flange interaction detected"
, "Flange failed!"
]

Podés probar tu función whatWentWrong con testWhatWentWrong, que también se encuentra en el módulo Log. Debés proveer a testWhatWentWrong tu funciones parse, whatWentWrong y el nombre del archivo de depuración a parsear.

Ejercicio 7

Mirá la salida de una ejecución de testWhatWentWrong. Para los dos archivos de depuración proveidos, algún aderezo parece sobresalir (¡son distintos aderezos para distintos archivos!). Podría ser más informativo ver al mismo tiempo las advertencias y los errores que mencionan ese aderezo en particular.

Definí una función:

messagesAbout :: String -> [LogMessage] -> [LogMessage]

que filtra una lista de LogMessages para solo incluir los mensajes que contengan la string proveida. Hacé que tu función sea insensible a las mayúsculas, para que “relish” encuentre “Relishsign detected!!”.

Ejercicio 8

Ahora queremos ver una salida combinada, con al mismo tiempo todos los mensajes de alta severidad y todos los mensajes que contengan alguna palabra-clave. Escribí una función:

whatWentWrongEnhanced :: String -> [LogMessage] -> [String]

esto genera una lista que incluye al mismo tiempo todos los errores graves y todos los mensajes que contengan la string proveida. Observá que probablemente tendrás que editar (es decir, refactorizar) código que escribiste antes para poder hacerlo sin repetirte demasiado. Para probar tu función, ejecutá algo así en GHCi:

LogAnalysis> testWhatWentWrong parse (whatWentWrongEnhanced "relish") "error.log"

(¿Porqué funciona pasarle solo un parámetro a whatWentWrongEnhanced?)

Tendrás puntos bonuses si llegás a usar la función siguiente:

(|||) :: (LogMessage -> Bool) -> (LogMessage -> Bool) -> LogMessage -> Bool
(|||) f g x = f x || g x -- (||) es el operador "o logico" de Haskell