¿cómo usar la mónada de estado en Haskell? (y un par de cosillas sobre estos curiosos animales)
Haskell.
Haskell es un lenguaje funcional puro, más que eso, es la Santa Inquisición de la programación funcional. Scheme merece arder en el fuego académico por su impureza, dice el desarrollador Haskell.
El problema es que un programa funcional puro no puede hacer nada interesante, esta encerrado dentro de sí mismo sin poder comunicarse con el mundo exterior. No hay una forma sencilla de relacionarse con ese complejo conglomerado de datos potencialmente interesantes, es decir, de realizar entrada/salida en el campo funcional, a no ser que pasemos todo el mundo como un argumento de nuestra función y devolvamos un nuevo mundo ligeramente modificado, usando el ejemplo clásico de cualquier manual Haskell:
putStringOnScreen :: String -> Mundo -> Mundo -- aqui viene la definicion mundo' = putStringOnScreen "adios mundo, hola mundo" mundo
Dada la dificultad de encerrar todo el mundo, incluyendo una descripción de ese mundo, que incluye una descripción de ese mundo ..., en un solo parámetro, los santos padres del comité Haskell, decidieron que la forma correcta de realizar este tipo de computación, sin perder la pureza del lenguaje, estaba en usar una parte de las matemáticas denominada teoría de categorías, y en particular, el concepto de mónada.
Hay que admitir que el nombre mola: "mónada", Pitágoras, Leibniz, pero qué nombre más chulo... Aunque más allá del nombre, una mónada, atendiendo a su definición, es algo bastante sencillo. Esta última formaliza una mónada como:
Un triplete compuesto por:
- Un tipo de datos polimórfico: 'M a', donde 'a' puede ser cualquier tipo que se va a convertir en monádico.
- Una operación de "bind" (>>=): definida en el Preludio de haskell como (>>=) :: m a -> (a -> m b) -> m b, que enlaza dos funciones monádicas, pasando el resultado de la primera a la segunda y devolviendo el resultado de la segunda
- Una función que inyecta el tipo de data a en la mónada M a (return): Definida en el Preludio con pésimo criterio para la elección del nombre como return :: a -> m a
Resumiendo tenemos, un tipo de dato, M, que puede contener dentro cualquier otro tipo de dato, una función (>>=) que combina dos funciones que procesan el tipo monádico, devolviendo como resultado otra instancia del tipo monádico y una función que, dado un tipo, nos devuelve el tipo encerrado en la mónada (return).
Además, el tipo y funciones definidos en la mónada deben cumplir las 3 Leyes Monádicas, que vienen a decir, de manera informal, que las funciones (>>=) y (return) deben comportarse bien con el elemento identidad y ser asociativas.
Eso es todo, nada excesivamente complicado. El problema viene cuando uno se pregunta: y todo esto, ¿para qué?.
Las mónadas se usan, como veremos, para un montón de cosas en Haskell: para modelar la entrada/salida sin perder pureza, como mencionamos al principio, para modelar computaciones con estado mutable como las de un parser, para las excepciones, etc... La dificultad está en generalizar, a partir de todos estos ejemplos concretos, el verdadero potencial de las mónadas: la de modelar un proceso computacional, ofreciendo la capacidad de generar pequeños minilenguajes de propósito específico, situándose un paso más allá de la capacidad de abstracción que ofrece, por ejemplo, las macros Lisp.
La primera mónada que usamos casi todos desde que empezamos nuestro penar por la tierra Haskell, es la mónada Maybe. Esta mónada se usa para describir una computación que puede, o no, devolver un valor.
Por ejemplo, imaginemos una función que busca el número de una persona en una agenda:
-- una agenda es una lista de tuplas (nombre, teléfono) lookup :: PhoneBook -> String -> Integer lookup pb n = (snd . head . (filter (\ (npb,tnpb) -> n == npb)) ) pb
Si el nombre del argumento está en la agenda, devolvemos el número, ¿pero y si no está?, pues en ese caso en vez de devolver un Integer, podemos modificar la función para devolver "quizas un Integer":
lookup :: PhoneBook -> String -> Maybe Integer
lookup pb n = case (filter (\ (npb,tnpb) -> n == npb) pb) of
((nf,tnf):others) -> Just tnf
otherwise -> Nothing
Ahora comprobamos si hay algún teléfono para el nombre pasado como argumento, filtrando la agenda con una función lambda, y dependiendo de si encontramos o no una lista de entradas en la agenda, devolvemos "solo" el primer teléfono (Just tn) o devolvemos nada en otro caso (Nothing).
Aprovechando la definición de Mónada encerramos el tipo, en este caso Integer, dentro de la mónada (Just tn), además, la biblioteca ofrece funciones que extraen el tipo de la mónada, en este caso (fromJust):
fromJust (Just "hola") == "hola" -- evalua a True
Todas las mónadas ofrecen este tipo de funciones.
Hemos visto como la mónada Maybe se usa, sobre todo, para encerrar un tipo de datos en la mónada, bien, volviendo al problema inicial de la entrada/salida, en Haskell se usa esta capacidad para encerrar las acciones impuras de entrada/salida en una mónada especial, la mónada IO. De esta manera, las funciones que usan esta mónada siguen siendo puras, recibendo y devolviendo valores de la mónada IO que describen una "acción de entrada salida", pero sin que su pureza se vea afectada: sin efectos laterales, ya que estos efectos laterales se producen cuando la acción de entrada/salida descrita por la mónada se ejecuta.
La metáfora que se suele usar es la de un contenedor de residuos nucleares (aunque circulan por ahí todo tipo de variaciones, mi preferida, la de los trajes de astronauta para viajeros entre estaciones espaciales), algo potencialmente muy peligroso, la entrada salida con todos sus efectos laterales, que se protege con un contenedor de seguridad, la mónada.
Por ejemplo, la función del preludio (getLine) encierra en una acción que lee el texto introducido por la entrada estándar hasta que se teclea un retorno de línea. El tipo de esta función es el siguiente
getLine :: IO String
Esta claro que getLine no puede ser una función pura, no recibe ningún argumento, y el tipo de retorno varía cada vez que se invoca la función, esto es lo que indica el tipo de la misma: "¡Cuidado, residuos impuros serán devueltos dentro de la mónada IO cuando esta función se invoque!, úsese con precaución".
En la definición de Mónada vimos que se definían también una función (>>=) para enlazar dos funciones. Esto es muy útil porque en Haskell se usa la "evaluación perezosa", no se puede decidir en que orden se van a ejecutar las llamadas a las funciones, por ejemplo en (5 * (4 + 3)), no se sabe si se va a usar la propiedad distributiva o no, así que para secuenciar llamadas a funciones hay que ingeniárselas con funciones como (>>=) que permiten enlazar la ejecución secuencial de una serie de funciones. Por ejemplo, otra función mónadica IO es (putStrLine) que acepta una cadena y devuelve el tipo unitario encerrado en la mónada IO, mostrando, de paso, la linea por la salida estándar (el efecto lateral). Si quisiésemos leer primero una línea por la entrada y a continuación mostrarla por la salida deberíamos realizar algo como :
getLine >>= putStrLn
De esta manera, repitiendo aplicaciones del operador (>>=), se podrían secuenciar n acciones, algo que es tan habitual, que Haskell tiene una notación específica para este tipo de cómputos que edulcora la sintaxis para hacerla similar a la de un lenguaje imperativo: la notación do.
En esta notación el anterior ejemplo se escribiría:
testIO :: IO ()
testIO = do l <- getLine
o <- putStrLn l
return o
Este "bloque do" parece una serie de comandos ejecutados secuencialmente pero en realidad son funciones enlazadas por la función (>>=). El operador '<-' lo que hace es extraer el tipo encerrado en una mónada. De esta manera, como getLine devuelve (IO String) al pasarlo por (<-) nos quedamos solo con el String. El final de un bloque do debe devolver una mónada para mantener los tóxicos efectos laterales bajo control, por ello acaba con un (return), que como vimos inyecta el tipo en la mónada. Aunque en este caso sobraría simpre que no extraigamos el tipo retornado por putStrLn, ya que esta función devuelve IO ().
Una forma fácil de hacerse una idea de la importancia de la mónada de IO reside en el hecho de que un programa Haskell en ejecución no es más que una acción encerrada en la mónada IO, por eso Haskell obliga a definir el punto de entrada a la aplicación con el tipo de la mónada IO
Después de este rápido repaso por el zoológico de mónadas, volvamos al título del post: la mónada de estado. Esta mónada se usa para modelar una serie de computaciones que comparten un estado común que modifican y leen. El ejemplo más común que se encuentra en la literatura es el de un generador de números aleatorios, ya que las funciones que generan los números deben compartir una semilla con la que generar el siguiente número pseudoaleatorio. Esta semilla debe ser pasada entre las diferentes funciones como un argumento, lo que puede llegar a ser una importante fuente de errores y aburrimiento.
Haskell ofrece una forma muy elegante de solucionar este problema usando la mónada de estado, que se encuentra en el módulo Control.Monad.State.
La principal diferencia entre esta mónada y las anteriores es que la mónada en vez de encerrar un tipo simple, almacena una función. La definición del tipo de la mónada es el siguiente:
newtype State s a = State {
runState :: (s -> (a, s))
}
La mónada State almacena una función del tipo (s -> (a,s)), una función que recibe un estado s, hace algo con el estado y devuelve el resultado de su cómputo y el estado modificado. Se puede acceder a esta función mediante el registro runState del tipo. Por supuesto, siguen pudiéndose enlazar funciones sobre el estado con el operador (>>=) y (return). Además, se definen una función que, como (fromJust) en el caso de la mónada Maybe, permiten extraer el tipo encerrado en la mónada: evalState, execState...
Veamos un ejemplo concreto de su uso con nuestra vieja amiga la agenda de teléfonos:
Hemos definido el tipo para la agenda: una serie de tuplas nombre, teléfono:
type PhoneBook = [(String,Integer)]
A continuación definimos la función de búsqueda en la agenda, esta función es similar a la que definimos antes, solo que en vez de recibir el nombre y la agenda y devolver quizás un número de teléfono, recibe un nombre y devuelve el estado de la computación: la mónada State que encierra una función que recibe un PhoneBook y devuelve quizás un número de teléfono y el PhoneBook. Esto lo hacemos devolviendo en la función que estamos escribiendo, una función lambda encerrada en la mónada State y usando el nombre pasado como argumento en la closure de la función lambda:
stlookup :: String -> State PhoneBook (Maybe Integer)
stlookup s = State (\ pb -> ((check pb s),pb))
where check ((n,tn):es) s = if n == s then
Just tn
else (check es s)
check [] s = Nothing
De la misma manera, podemos definir una función (append) que añade una entrada a la agenda. Esta función recibe como argumento el par nombre, teléfono y devuelve el estado de la computación con la agenda modificada. Esto lo hacemos de manera equivalente a la función anterior usando una función lambda y su closure:
stappend :: (String,Integer) -> State PhoneBook ()
stappend (n,tn) = State (\ pb -> case (evalState (stlookup n) pb) of
(Just _) -> ((),pb)
otherwise -> ((),(n,tn):pb))
Una vez definidas estas funciones, podemos combinarlas en otras funciones usando la notación do, lo que facilita bastante el uso de la mónada de estado, por ejemplo en la función que añade una entrada si esa persona no tiene ya una entrada asociada:
addUnlessExists :: String -> Integer -> State PhoneBook Integer
addUnlessExists n ntn = do tn <- stlookup n
case tn of
(Just tn) -> return tn
otherwise -> do stappend (n,ntn)
return ntn
Para lanzar la computación podemos usar el registro runState de la mónada State, y aplicar la función resultante sobre, por ejemplo, un agenda vacía
(runState (addUnlessExists "Leibniz" 67837483)) []
Pues ya está, esto es, más o menos, un primer paso en el mundo de las mónadas en Haskell. Por supuesto una mónada no puede programarse sólo en Haskell, se puede programar en cualquier lenguaje de programación con un grado mayor o menor sufrimiento.
En cualquier caso, si alguien a conseguido llegar hasta aquí y todavía tiene ganas de más, le recomiendo que eche un vistazo al capítulo 16 del "Real World Haskell", estupendo libro sobre Haskell que acaba de ser publicado y cuyos capítulos "beta" están disponibles gratis online: http://book.realworldhaskell.org/beta/monads.html
