% Práctico Haskell 6: Clases de Tipos

Preparación

Bajá el archivo Poly.hs y completá las definiciones según el enunciado.

Es conveniente tener Hoogle a mano para buscar funciones, tipos y clases de tipos.

En esta guía de ejercicios, vamos a trabajar con un tipo de datos algebraicos que sirve para representar polinomios. Vamos a definir instancias de este tipo para distintas clases de tipos.

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^2 + 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^2 + 5x + 3$ se escribe P [3, 5, 1].

Ejercicio 1

En este ejercicio, vamos a escribir una instancia de la clase Eq para el Poly a. Podríamos implementarla de manera simple, comparando las listas dentro del constructor P, pero esto no alcanza. ¿Cuándo es el caso que dos Poly son equivalentes (siempre devuelven el mismo valor), 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 (==).

La función (==) tiene que cumplir con los ejemplos siguientes:

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

Algunas funciones útiles para definirla 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^2 - 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)…

Consejo: Tratá de implementar los puntos anteriores desde el primero, pero no dediques más de 15 minutos a este ejercicio durante esta clase, se vienen más cosas interesantes.

¿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 nuestro tipo de polinomios.

Ejercicio 3

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^2 + 5) + (2x^2 + x + 1) = 3x^2 + 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

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).

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 a

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

A esta altura, con todo lo que hiciste, el polinomio $x^2 + 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”.

Ejercicio 7

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