Una Introducción agradable a Haskell
anterior siguiente
inicio
Esta sección del tutorial es posiblemente menos `agradable' que las otras. Aquí trataremos no solo las características del lenguaje relacionadas con las mónadas sino que también intentaremos dar una visión más amplia: mostraremos porque son las mónadas una herramienta tan importante y como son usadas. No hay un módo único de explicar las mónadas que sea adecuado para todo el mundo; otras explicaciones encontrarse en haskell.org. Una buena introducción al uso práctico de las mónadas es el artículo Monads for Functional Programming [10] de Wadler.
Una mónada se construye sobre un tipo polimórfico como IO. La mónada propiamente queda definida mediante declaraciones de instancia que asocian el tipo con algunas o todas las clases monádicas, Functor, Monad, y MonadPlus. Ninguna de las clases monádicas puede ser derivada. Además de IO, otros dos tipos en el Prelude son miembros de las clases monádicas: las listas ([]) y el tipo Maybe.
Matemáticamente, las mónadas están caracterizadas por un conjunto de leyes (o propiedades) que deberían cumplir las operaciones monádicas. Este concepto de ley no es exclusivo de las mónadas: otras de las operaciones de Haskell están caracterizadas, al menos informalmente, por leyes. Por ejemplo, x /= y y not (x == y) deberían ser lo mismo para cualquier tipo de valor para el que tenga sentido dicha comparación. Sin embargo, no hay garantía de de que esto ocurra: tanto == como /= son métodos independientes en la la clase Eq y no hay modo de asegurar que == y =/ estén relacionados de este modo. Del mismo modo, las leyes monádicas que presentamos a continuación no son impuestas por Haskell, pero deberían cumplirse para cualquier instancia de una clase monádica. Las leyes de las mónadas proporcionan un mayor entendimiento de la estructura subyacente de las mónadas: esperamos que al examinar estas leyes proporcionemos al lector una primera impresión de cómo se usan las mónadas.
La clase Functor, ya discutida en la sección 5, define una única operación: fmap. La función fmap aplica una operación a los objetos pertenecientes a un contenedor (los tipos polimórficos pueden ser considerados como contenedores de valores de otro tipo), devolviendo un contenedor con la misma forma. Estas leyes caracterizan a fmap en la clase Functor:
| fmap id | = | id |
| fmap (f . g) | = | fmap f . fmap g |
Estas leyes aseguran que la forma del contenedor no es modificada por fmap y que el contenido de un contenedor no es reorganizado por la aplicación.
La clase Monad define dos operaciones básicas: >>= (bind) y return.
infixl 1 >>, >>=
class Monad m where
(>>=) :: m a -> (a -> m b) -> m b
(>>) :: m a -> m b -> m b
return :: a -> m a
fail :: String -> m a
m >> k = m >>= \_ -> k
Las operaciones >> y >>=, combinan dos
valores monádicos mientras que la función return sumerje un valor
en la mónada (el contenedor).
El tipo de >>=, Monad m => m a -> (a -> m b) -> m b, nos ayuda
a comprender esta operación: ma >>= \v -> mb
combina un valor monádico ma que contenga valores de tipo a y
una función que opera sobre sobre un valor v de tipo a
devolviendo el valor monádico mb. El resultado es combinar
ma y mb en un valor monádico que contenga b. El operador >>
es usado cuando la función no usa el valor producido por la primera operación monádica.
El significado de los operadores bind depende, por supesto, de la mónada. Por ejemplo, en la mónada IO (mónada de E/S), x >>= y lleva a cabo dos acciones secuencialmente, pasando el resultado de la primera a la segunda. Para las otras mónadas predefinidas, las listas y el tipo Maybe, estas operaciones monádicas pueden ser entendidas en términos de pasar cero o más valores desde una computación a la próxima. Veremos ejemplos de esto a continuación.
La notación do proporciona una abreviatura sintáctica simple
para encadenamientos de operaciones monádicas. La esencia de traducción
de las expresiones do está reflejada en las siguientes dos reglas:
do e1 ; e2 = e1 >> e2
do p <- e1; e2 = e1 >>= \p -> e2
Cuando el patrón en la segunda ecuación do es refutable, un fallo en
el encaje de patrones llama a la función fail. Esto puede elevar
un error (como ocurre en la mónada IO) o devolver un `cero' (como
ocurre en la mónada lista). Así, la traducción completa es
do p <- e1; e2 = e1 >>= (\v -> case v of p -> e2; _ -> fail "s")
donde "s" es una cadena de caracteres
identificando la localización de la sentencia do para un posible uso en
un mensaje de error. Por ejemplo, en la mónada IO,
una acción como 'a' <- getChar llamará a fail si
el caracter tecleado no es 'a'. Esto, a su vez, terminará el programa ya que en la
mónada IO fail llama a error.
Las leyes que caracterizan a >>= y return son:
| return a >>= k | = | k a |
| m >>= return | = | m |
| xs >>= return . f | = | fmap f xs |
| m >>= (\x -> k x >>= h) | = | (m >>= k) >>= h |
La clase MonadZero se usa para mónadas que definen un elemento cero
y una operación plus:
class (Monad m) => MonadZero m where
mzero :: m a
mplus :: m a -> m a -> m a
El elemento cero debe verificar las siguientes propiedades:
| m >>= \x -> mzero | = | mzero |
| mzero >>= m | = | mzero |
Para las listas, el valor cero es [], la lista vacía. La mónada IO no posee un cero por lo que no es un miembro de esta clase.
Las propiedades que caracterizan al operador mplus son las siguientes:
| m `mplus` mzero | = | m |
| mzero `mplus` m | = | m |
En el caso de las listas, el operador mplus es la concatenación habitual.
Para las listas, el operador de binding se corresponde con
agrupar un conjunto de computaciones para cada valor de la lista. Cuando se usa sobre listas,
el tipo de >>= es:
(>>=) :: [a] -> (a -> [b]) -> [b]
Esto se interpreta como, dada una lista cuyos elementos tienen tipo a
y una función que transforma un valor de tipo a en una lista de valores
de tipo b, el operador de binding aplica esta función
a cada uno de los valores de tipo a en la entrada y devuelve todos los valores
de tipo b generados como una lista. La función return
crea una lista unitaria. Estas operaciones deberían ser ya familiares: las listas por
comprensión pueden ser expresadas fácilmente usando las operaciones monádicas definidas
para las listas. Las siguientes tres expresiones corresponden a diferentes modos de
escribir lo mismo:
[(x,y) | x <- [1,2,3] , y <- [1,2,3], x /= y]
do x <- [1,2,3]
y <- [1,2,3]
True <- return (x /= y)
return (x,y)
[1,2,3] >>= (\ x -> [1,2,3] >>= (\y -> return (x/=y) >>=
(\r -> case r of True -> return (x,y)
_ -> fail "")))
La definición depende del hecho de que la definición de la función fail
para la mónada lista es la lista vacía. Esencialmente, cada <-
genera un conjunto de valores que se pasa al resto de la computación monádica.
Así x <- [1,2,3] invoca el resto de la computación monádica
tres veces, una por cada elemento en la lista. La expresión devuelta, (x,y), será
evaluada para todas las posibles combinaciones de valores.
En este sentido, podemos ver que la mónada lista es útil para funciones que trabajan con
argumentos multi-valuados. Por ejemplo, la siguiente función:
mvLift2 :: (a -> b -> c) -> [a] -> [b] -> [c]
mvLift2 f x y = do x' <- x
y' <- y
return (f x' y')
convierte una función ordinaria de dos argumentos
(f) en una función sobre múltiples valores (listas de argumentos),
devolviendo un valor para cada posible combinación de dos argumentos de
entrada. Por ejemplo,
| mvLift2 (+) [1,3] [10,20,30] | => | [11,21,31,13,23,33] |
| mvLift2 (\a b->[a,b]) "ab" "cd" | => | ["ac","ad","bc","bd"] |
| mvLift2 (*) [1,2,4] [] | => | [] |
La función es una especialización de la función liftM2 definida en la biblioteca estandarizada para mónadas. Puedes verla como una función que transporta a cierta función, f, desde fuera de la mónada de las listas a la mónada de las listas en la que los cómputos se realizan sobre valores múltiples.
La mónada definida para el tipo Maybe es parecida a la mónada de las listas: el valor Nothing hace el papel de [] y Just x el de [x].
De un modo breve, una mónada de estados construída sobre un
tipo S toma la siguiente forma:
data SM a = SM (S -> (a,S)) -- The monadic type
instance Monad SM where
-- define la propagación de estados
SM c1 >>= fc2 = SM (\s0 -> let (r,s1) = c1 s0
SM c2 = fc2 r in
c2 s1)
return k = SM (\s -> (k,s))
-- extrae el estado de la mónada
readSM :: SM S
readSM = SM (\s -> (s,s))
-- modifica el estado
updateSM :: (S -> S) -> SM ()
updateSM f = SM (\s -> ((), f s))
-- ejecuta una computación en la mónada
runSM :: S -> SM a -> (a,S)
runSM s0 (SM c) = c s0
El ejemplo define un nuevo tipo, SM, para representar cómputos que
implícitamente arrastran un valor de tipo S. Es decir,
una computación de tipo SM t
define un valor de tipo t
que a la vez interactúa (leyendo y modificando) con un estado de tipo
S. La definición SM es simple: se trata de funciones
que toman un estado y producen dos resultados: el valor devuelto
(de cualquier tipo) y el valor del estado actualizado. No podemos usar
aquí un sinónimo de tipos: es necesario un nombre de tipo como
SM para poder usarlo en declaraciones de
instancia. En este caso, se suele usar una declaración newtype
en vez de la declaración data.
La declaración de instancia define la `fontanería' correspondiente a la mónada: como secuenciar dos computaciones y la definición de la computación vacía. La secuenciación (el operador >>=) define un cómputo (denotado con el constructor SM) que pasa un estado inicial, s0, a c1, y entonces pasa el valor resultante de este cómputo, r, a la función que devuelve el segundo cómputo, c2. Por último, el estado resultado de c1 se pasa a c2 y el resultado final se define como el resultado de c2.
La defición de return es más simple: return no modifica el estado en absoluto; simplemente vale para convertir un valor en un cómputo monádico.
Aunque >>= y return son los operadores de secuenciación básicos para la mónada, tambien necesitamos algunas primitivas monádicas. Una primitiva monádica es simplemente una operación que usa la representación interna de la mónada accediendo a las `ruedas y engranajes' que la hacen funcionar. Por ejemplo, en la mónada IO, operaciones como putChar son primitivas ya que se ocupan del funcionamiento interno de la mónada IO. De un modo similar, nuestra mónada de estados usa dos primitivas: readSM y updateSM. Obsérvese que estas dependen de la estructura interna de la mónada - un cambio en la definición del tipo SM requeriría que se realizase un cambio en estas primitivas.
Las definiciones de readSM y updateSM son simples: readSM presenta, con objeto de que sea observado, el estado de la mónada mientras que updateSM permite al usuario alterar el estado de la mónada. (Podríamos también haber usado una función como writeSM como primitiva pero la actualización es a menudo un modo más natural de manejar el estado).
Por último, necesitamos una función para ejecutar cómputos en la mónada, runSM. Ésta toma un valor inicial para el estado y un cómputo y devuelve tanto el valor del resultado del cómputo como el estado final.
De un modo más genérico, lo que estamos intentando es definir toda una computación como una serie de pasos (funciones con tipo SM a), secuenciadas mediante >>= y return. Estos pasos pueden interactuar con el estado (a través de readSM o updateSM) o pueden incluso ignorar el estado. En cualquier caso, el uso (o no uso) del estado se encuentra oculto: no invocamos o secuenciamos los cómputos de un modo diferente dependiendo de que usen o no S.
En lugar de presentar algún ejemplo usando esta mónada tan simple, avanzamos hacia un ejemplo más elaborado que engloba también la mónada de estados. Definimos un pequeño lenguaje embebido para el cálculo del uso de recursos. Con esto queremos decir que construiremos un lenguaje de propósito especial, implementándolo como un conjunto de tipos y funciones en Haskell, para construir una biblioteca de operaciones y tipos hechos a la medida del dominio de interés.
En este ejemplo, consideramos un cómputo que requiere alguna clase de recurso. Si el
recurso está disponible, el cómputo prosigue; cuando el recurso no está disponible, el
cómputo queda suspendido. Usaremos el tipo R
para denotar una computación que use los recursos controlados por nuestra mónada.
La definición de R es la siguiente:
data R a = R (Resource -> (Resource, Either a (R a)))
Cada cómputo es una función de los recursos
disponibles a los recursos sobrantes, emparejados con, o bien un
resultado, de tipo a, o un cómputo suspendido, de
tipo R a, que captura el trabajo hecho hasta el punto en el cual
los recursos se agotaron.
La instancia para la clase Monad correspondiente al tipo R es:
instance Monad R where
R c1 >>= fc2 = R (\r -> case c1 r of
(r', Left v) -> let R c2 = fc2 v in
c2 r'
(r', Right pc1) -> (r', Right (pc1 >>= fc2)))
return v = R (\r -> (r, (Left v)))
El tipo Resource se usa del mismo modo que el estado
en la mónada de estados. Esta definición se puede interpretar del
siguiente modo: para combinar dos cómputos
`dependientes de recursos', c1 y fc2 (una función que produzca
c2), pasamos los recursos iniciales a c1. El resultado será
o bien
Esta declaración de instancia define la estructura
básica de la mónada pero no indica cómo se usan los recursos.
Así, esta mónada podría ser usada para manejar distintos tipos de recursos
o para implementar distintas políticas para el uso de recursos.
Como ejemplo, mostraremos una definición de recursos muy simple:
haremos que el tipo Resource sea un
Integer, que represente los pasos computacionales disponibles:
type Resource = Integer
Esta función consume un paso a no ser que no queden pasos disponibles:
step :: a -> R a
step v = c where
c = R (\r -> if r /= 0 then (r-1, Left v)
else (r, Right c))
Los constructores Left y Right son parte
del tipo Either.
La función continúa con el cómputo en R y devuelve v siempre
que exista al menos un paso computacional disponible.
Si no hay pasos disponibles, la función step suspende el computo
actual (esta suspensión queda capturada en c) y vuelve a introducir
este cómputo suspendido en la mónada.
Hasta ahora, tenemos las herramientas necesarias para definir una secuencia de computaciones `dependientes de recursos' (la mónada) y podemos expresar una forma de uso de recursos mediante step. Por último, necesitamos considerar cómo se expresarán los cómputos correspondientes a esta mónada.
Consideremos una función de incremento para nuestra mónada:
inc :: R Integer -> R Integer
inc i = do iValue <- i
step (iValue+1)
De este modo definimos el incremento como un único paso computacional. La <- es
necesaria para extraer el valor de argumento de la mónada; el tipo de
iValue es Integer en vez de R Integer.
Esta definición no es totalmente satisfactoria, especialmente,
si la comparamos con la definición estandarizada de la función de
incremento. ¿Podríamos mejor `arropar' operaciones existentes
como + para que funcionen en nuestro mundo monádico? Comenzaremos
con un conjunto de funciones de elevamiento (lifting). Éstas
permiten introducir funcionalidad existente en la mónada. Consideremos la definición
de lift1 (se trata de una definición ligeramente diferente
a la función liftM de la biblioteca Monad):
lift1 :: (a -> b) -> (R a -> R b)
lift1 f = \ra1 -> do a1 <- ra1
step (f a1)
Esta función toma una función de un único argumento, f, y crea
una función R que ejecuta la función elevada
en un único paso.
Usando lift1, inc puede ser definida como
inc :: R Integer -> R Integer
inc = lift1 (\i -> i+1)
Esta definición es mejor, pero todavía no es idónea. Primero, añadimos lift2:
lift2 :: (a -> b -> c) -> (R a -> R b -> R c)
lift2 f = \ra1 ra2 -> do a1 <- ra1
a2 <- ra2
step (f a1 a2)
Obsérvese que esta función
explícitamente establece el orden de evaluación en la función elevada: el cómputo
que devuelve a1 ocurre antes que el cómputo para a2.
Usando lift2, podemos crear una nueva versión de == en la mónada R:
(==*) :: Ord a => R a -> R a -> R Bool
(==*) = lift2 (==)
Hemos tenido que usar un nombre un poco diferente
para esta función ya que
== ya está definido, pero en algunos casos podemos usar el mismo nombre para
las funciones elevadas y la original. Esta declaración de
instancia permite que todos los operadores de la clase Num puedan ser usados
en la mónada R:
instance Num a => Num (R a) where
(+) = lift2 (+)
(-) = lift2 (-)
negate = lift1 negate
(*) = lift2 (*)
abs = lift1 abs
fromInteger = return . fromInteger
La función fromInteger se aplica implícitamente
a todas las constantes enteras en un programa Haskell (véase la sección 10.3);
esta definición permite que las constantes enteras
puedan actuar con el tipo R Integer.
Podemos ahora, por fin, escribir
la función de incremento de un modo completamente natural:
inc :: R Integer -> R Integer
inc x = x + 1
Obsérvese que no podemos elevar
la clase Eq del mismo modo que la clase
Num: el tipo de ==* no es compatible con
las posibles sobrecargas de == ya que el resultado de ==* tiene tipo R Bool en lugar de
Bool.
Para poder expresar cómputos interesantes en
R necesitaremos una condicional. Como no podemos usar if (requiere que
la condición tenga tipo
Bool en lugar de R Bool), definimos la función ifR:
ifR :: R Bool -> R a -> R a -> R a
ifR tst thn els = do t <- tst
if t then thn else els
Ahora estamos preparados para escribir un programa más extenso
en la mónada R:
fact :: R Integer -> R Integer
fact x = ifR (x ==* 0) 1 (x * fact (x-1))
Aunque ésta no es la definición habitual de la función factorial
es bastante leíble. La idea de proporcionar nuevas definiciones
para operaciones existentes como + o if es
una parte esencial para crear un lenguaje embebido en Haskell. Las mónadas
son especialmente útiles para encapsular la semántica
de estos lenguajes embebidos de un modo claro y modular.
Ahora estamos preparados para ejecutar algunos programas. Esta función
ejecuta un programa en R dado un número máximo
de pasos computacionales:
run :: Resource -> R a -> Maybe a
run s (R p) = case (p s) of
(_, Left v) -> Just v
_ -> Nothing
Hemos usado el tipo Maybe para tratar
la posibilidad de que el cómputo no termine con el número de pasos
reservados. Podemos ahora computar
| run 10 (fact 2) | => | Just 2 |
| run 10 (fact 20) | => | Nothing |
Podemos, por último, añadir
alguna funcionalidad más interesante a la mónada. Consideremos la siguiente
función:
(|||) :: R a -> R a -> R a
que ejecuta dos cómputos en paralelo, devolviendo el valor del
primero que acabe. Una posible definición de esta función es:
c1 ||| c2 = oneStep c1 (\c1' -> c2 ||| c1')
where
oneStep :: R a -> (R a -> R a) -> R a
oneStep (R c1) f =
R (\r -> case c1 1 of
(r', Left v) -> (r+r'-1, Left v)
(r', Right c1') -> -- r' must be 0
let R next = f c1' in
next (r+r'-1))
Se lleva a cabo un paso de c1, devolviendo
su valor si se completo el cómputo o, si
c1 devuelve un cómputo suspendido (c1'), se evalúa
c2 ||| c1'. La función oneStep
lleva a cabo un único paso de su argumento, devolviendo bien
un valor evaluado o pasando el resto del cómputo
a f. La definición de oneStep es simple:
pasa a c1 un 1 como recurso. Si se alcanza un valor
final, éste es devuelto, ajustando el contador de pasos (es posible
que un cómputo retorne sin llevar a cabo ningún paso por lo que el
contador de recursos devuelto no ha de ser necesariamente 0). Si
la computación queda suspendida, un contador de recursos enmendado
es pasado a la continuación final.
Podemos ahora evaluar expresiones como run 100 (fact (-1) ||| (fact 3)) sin que ésta no acabe ya que los dos cómputos son intercalados. (Obsérvese que nuestra definición de fact no acaba para -1). Podemos llevar a cabo muchas variaciones sobre esta estructura básica. Por ejemplo, podríamos extender el estado para incluir una traza de los pasos computados. También podríamos embeber esta mónada en la mónada estandarizada IO, de modo que los cómputos en R pudiesen interactuar con el mundo externo. Aunque este ejemplo es quizás más avanzado que otros en este tutorial, permite ilustrar la potencia de las mónadas como una herramienta para definir la semántica básica de un sistema. Este ejemplo también es un modelo de un pequeño Lenguaje de Dominio Específico, algo para los que Haskell es especialmente adecuado. Muchos otros LDEs han sido desarrollados en Haskell; véase haskell.org para más ejemplos. Especialmente interesantes son Fran, un lenguaje de animaciones reactivas, y Haskore, un lenguaje para la música por ordenador.