Alo! Amigos, hoy voy a hablarles de algo que es muy posible que les resulte complicado, ya que es sobre programacion (GASP!) y encima de haskell (super GASP!) y sobre monadas (WTF!?). Anyway lo voy a postear, porque mi blog se nutre de los googleadores que llegan por casualidad.
Para entender este articulo hace falta entender lo que son las monadas y como funcionan, esto lo voy a explicar algun dia en algun otro blogpost pero por ahora no voy a explicar nada.
Este experimento haskelliano es nada más y nada menos que mi intento de reproducir la macro (loop) de Common Lisp, un mini lenguaje de loopeo que posee lisp.
Ejemplo de codigo:
(loop for x from 1
for y in '(a b c d e f g h i j k)
until x < 5 do collect (list x y) if (!= x 3))
Esto lo que hace es itera x desde 1 hasta el infinito, itera y por todos los elementos de la lista '(a b c d e f g) y luego va acumulando mediante el "collect" pares de x y, siempre y cuando x sea distinto de 3.
Resultado de la evaluacion: ((1 a) (2 b) (4 d))
Este minilenguaje que es loop tiene varios de los patrones basicos de loopeo y los abstrae. Quiza este ejemplo no lo muestre pero podemos agregar otros collects, llamar a funciones de todo tipo, etc, es decir las palabras claves de loop son totalmente combinables.
Un defecto de loop sumamente criticado es que es una macro extremadamente compleja, tanto es asi que muchos lisperos detestan la macro. A mi me encanta, porque me permite expresar cualquier loopeo de la manera mas declarativa posible, simplemente escribiendo lo que estoy pensando.
En haskell, pues, lo más parecido a esto es las listas por comprension, pero no se puede hacer con ellas todo lo que se puede hacer con loop con tanta facilidad (aunque se puede verdaderamente hacer un montón). Asi que pues, quise implementar algo lo más parecido a loop (un subset na' mas) pero en haskell.
Si bien haskell tiene macros (via la extension Template Haskell), muchas de las cosas que en lisp se suelen implementar como macros en haskell se pueden implementar como monadas, cosas como computacion no determinstica, manejo de excepciones, et cetera.; dado que las monadas son un concepto mas puro y mas manejable en esto me parece que haskell es superior, aunque las macros de lisp son mucho mas completas (se puede hacer realmente cualquier cosa con ellas).
Pues bien, como se implementa esto? despues de pensar mil cosas distintas y experimentar muchas posibilidades, llegue a la conclusion de que una manera (ante todo sencilla de implementar :D) es utilizando una suerte de mezcla entre la monada State y la monada Maybe.
El tipo de dato abstracto de la monada State suele ser
\ s -> (a,s), mientras que aqui es algo como
\ s -> (Maybe a,s), a esta monada la llame LoopState. La idea de devolver Maybe es que si la funcion monadica llega a devolver Nothing, en ese momento se termina el loop. Además, y esto es por ahora para el for, además del estado guardado que dependera de que hagamos en el loop (si hacemos collecting o buscamos un valor único), se pasa el número de iteracion dentro del estado. Entonces puedo implementar una funcion monádica for :: [a] -> LoopState s a, que segun el número de iteracion, toma el primer elemento de la funcion, el segundo, etc y lo va pasando; pero si la lista no es suficientemente larga devolvera Nothing y eso terminará el loop (esto imita el comportamiento de la macro de lisp, que loopea hasta que se termina el for mas corto).
Para completar la idea, esta monada representa simplemente una secuencia de instrucciones que puede terminar por la mitad, nada más y nada menos. Para el loopeo utilizo una funcion externa que reciba esta monada y la haga loopear siempre y cuando devuelva (Just _), pero aumentando el numero de iteracion a medida que aumentamos el loopeo. Esa es toda la idea.
Algunos ejemplos de como se usa:
myloop = loopCollecting $ do x <- for [1..]
y <- for ['a'..'z']
untilLoop (x > 3)
collect (x,y)
when (y == 'a') $ collect (99, 'x')
myloop2 = loopFind $ do x <- for [1..]
y <- for ['a'..'z']
untilLoop (x > 3)
when (y == 'j') $ found x
myloop3 = loopFind $ do x <- for [1..]
y <- for ['a'..'z']
when (y == 'j') $ found x
Y los resultados de la evaluacion
*Test> myloop
[(1,'a'),(99,'x'),(2,'b'),(3,'c')]
*Test> myloop2
Nothing
*Test> myloop
[(1,'a'),(99,'x'),(2,'b'),(3,'c')]
*Test> myloop3
Just 10
*Test>Obviamente esto asi como está le faltan un par de cosas. En primer lugar, tendria que hacer una version LoopStateT de la monada para que pueda interactuar con la monada IO para que realmente sea interesante la cosa, claro que todavia no termino de entender como funcionan las versiones "Transformer" de las monadas. Y por otro lado sigue sin tener toda la flexibilidad de (loop), que por ejemplo te permite acumular en varias listas, y hacer IO, todo al mismo tiempo. Aqui tan solo puedo acumular en un solo lugar, y sinceramente no se me ocurre por ahora como darle mas flexibilidad sin usar la monada IO en modo unsafe.
Notas: si ya existe algo parecido en haskell, no lo conozco... admito que no soy un experto ni nunca desarolle software demasiado complejo con haskell, entre otras cosas porque no trabajo profesionalmente con el lenguaje.Bueh, el codigo:
---
module Test where
import Control.Monad
newtype LoopState s a = LoopState { runloopstate :: (Int,s) -> (Maybe a, (Int,s)) }
instance Monad (LoopState s) where
return a = LoopState $ \ s -> (Just a, s)
m >>= k = LoopState $ \ s -> let
(a, s') = runloopstate m s
in case a of Just x -> runloopstate (k x) s'
Nothing -> (Nothing, s')
numeroCorridas = LoopState $ \ (n,s) -> (Just n, (n,s))
terminate = LoopState $ \ s -> (Nothing, s)
maybeAt [] _ = Nothing
maybeAt (x:_) 0 = Just x
maybeAt (_:xs) n = maybeAt xs (n - 1)
for lista = do n <- numeroCorridas
case lista `maybeAt` (n-1) of
Just x -> return x
Nothing -> terminate
untilLoop True = terminate
untilLoop False = return ()
collect val = LoopState $ \ (n,l) -> (Just (), (n,val:l))
found val = LoopState $ \ (n, _) -> (Nothing, (n,Just val))
loopCollecting monad = reverse $ loopCollecting' monad 1 []
loopCollecting' monad n acc = let (val, (_, acc')) = runloopstate monad (n, acc)
in case val of Just _ -> loopCollecting' monad (n+1) acc'
Nothing -> acc'
loopFind monad = loopFind' monad 1
loopFind' monad n = let (val, (_, finding)) = runloopstate monad (n, Nothing)
in case val of Just _ -> loopFind' monad (n+1)
Nothing -> finding
