Haskell Hero

¿Qué es una calculadora? Es un aparato al que damos una expresión (por ejemplo 5 + 3 * 2) y nos imprime el resultado (en nuestro caso 11).

Vamos a programar una calculadora que sabe sumar, restar y multiplicar. Necesitamos dos cosas para poderlo hacer:

1. Definir expresiones que la calculadora sabrá evaluar. Vamos a definirlas como un tipo nuevo que llamamos por ejemplo Expresion.
2. Definir una función que evaluará las expresiones, es decir, convierte valores de tipo Expresion en valores de tipo Integer. La llamamos por ejemplo evalua y será de tipo evalua :: Expresion -> Integer.

En la calculadora normal ponemos expresiones en forma 5 + 3 * 2 (en una calculadora en la que ponemos primero toda la expresión y después pulsamos el signo igual). Sin embargo, en Haskell los números y los operadores (+), (-) y (*) ya están ocupados, por eso tenemos que definir nuestros propios.

Entonces vamos a crear un tipo nuevo que va a contener todos números enteros.

data Expresion = Numero Integer

Añadimos una expresión que representa la adición de expresiones:

data Expresion = Numero Integer | Mas Expresion Expresion

Mas (Numero 2) (Numero 5)
Mas (Numero 4) (Numero 8)
Mas (Numero 2) (Mas (Numero 2) (Numero 3))

De esta manera añadimos también expresiones que representan la resta y la multiplicación:

data Expresion = Numero Integer
               | Mas Expresion Expresion
               | Menos Expresion Expresion
	       | Multiplicado Expresion Expresion

Mas (Numero 5) (Multiplicado (Numero 3) (Numero 2))

Ahora ya tenemos definidas las expresiones y necesitamos una función que tome por ejemplo la expresión:

Mas (Numero 5) (Multiplicado (Numero 3) (Numero 2))

Empezamos evaluando la expresión Numero x. Quisiéramos que por ejemplo la expresión Numero 2 se evaluara al número 2. O que la expresión Numero 5 se evaluara al número 5. La definición será la siguiente:

evalua           :: Expresion -> Integer
evalua (Numero x) = x

Después tenemos que definir la evaluación de la expresión de adición. Queremos que por ejemplo la expresión Mas (Numero 2) (Numero 3) se evalúe a 2 + 3 y después a 5. ¿Cómo definir esta evaluación?

La expresión Mas x y la evaluamos de manera siguiente:

1. Evaluamos la expresión x por medio de la función evalua de manera recursiva.
2. De la misma manera evaluamos la expresión y.
3. Ya que sabemos que la función evalua nos devuelve un número entero, podemos sumar los resultados de evalua x y evalua y con el operador típico (+).

Entonces tenemos que añadir esta ecuación a la definición:

evalua (Mas x y) = (evalua x) + (evalua y)

evalua (Menos x y)        = (evalua x) - (evalua y)
evalua (Multiplicado x y) = (evalua x) * (evalua y)

La definición final será entonces la siguiente:

evalua                   :: Expresion -> Integer
evalua (Numero x)         = x
evalua (Mas x y)          = (evalua x) + (evalua y)
evalua (Menos x y)        = (evalua x) - (evalua y)
evalua (Multiplicado x y) = (evalua x) * (evalua y)

Vamos a evaluar la expresión 5 + 3 * 2 paso a paso:

    evalua (Mas (Numero 5) (Multiplicado (Numero 3) (Numero 2)))
~>  (evalua (Numero 5))  +  (evalua (Multiplicado (Numero 3) (Numero 2)))
~>          5            +  (evalua (Multiplicado (Numero 3) (Numero 2)))
~>  5  +  ((evalua (Numero 3))  *  (evalua (Numero 2)))
~>  5  +  (          3          *  (evalua (Numero 2)))
~>  5  +  (          3          *           2          )
~>  5  +  6
~>  11

Podéis preguntar - ¿porqué lo hacemos? Hugs sabe sumar y restar, pues ¿por qué hacer tanto trabajo definiendo un tipo nuevo y todas las funciones?

Imaginemos que la multiplicación de números grandes es mucho más compleja que la adición. Por ejemplo la expresión 3 * (5 + 6) se evaluaría de esta manera: Primero se suman el cinco y el seis y después se multiplica este resultado por tres. Ya que conocemos la ley distributiva, sabemos que 3 * (5 + 6) es lo mismo que (3 * 5) + (3 * 6).

Como hemos dicho al principio que la multiplicación de números grandes es mucho más complejo que la adición, podemos ver que la expresión (3 * 5) + (3 * 6) se evalúa más rápido que la expresión 3 * (5 + 6). Podríamos entonces convertir las expresiones en forma x * (y + z) en unas en forma (x * y) + (x * z) y solo después empezar a evaluar. ¿Qué será la función que realizará esta simplificación?

simplifica                            ::  Expresion -> Expresion
simplifica (Multiplicado x (Mas y z))  =
                Plus (Multiplicado (simplifica x) (simplifica y))
                     (Multiplicado (simplifica x) (simplifica z))
simplifica _                           =  _