La mónada de la Pausa

Nota: que usted mismo no proporcionó acceso directo al estado actual s en esta mónada.

Pause s es solo una mónada libre sobre las operaciones mutate y yield. Implementado directamente se obtiene:

data Pause s a
  = Return a
  | Mutate (s -> s) (Pause s a)
  | Yield (Pause s a)

instance Monad (Pause s) where
  return = Return
  Return a   >>= k = k a
  Mutate f p >>= k = Mutate f (p >>= k)
  Yield p    >>= k = Yield (p >>= k)

Con un par de constructores inteligentes para darle la API deseada:

mutate :: (s -> s) -> Pause s ()
mutate f = Mutate f (return ())

yield :: Pause s ()
yield = Yield (return ())

Y la función step para conducirlo

step :: s -> Pause s () -> (s, Maybe (Pause s ()))
step s (Mutate f k) = step (f s) k
step s (Return ()) = (s, Nothing)
step s (Yield k) = (s, Just k)

También podría definir esto directamente usando

data Free f a = Pure a | Free (f (Free f a))

(de mi paquete 'gratis') con

data Op s a = Mutate (s -> s) a | Yield a

Entonces ya tenemos una mónada para Pausa

type Pause s = Free (Op s)

Y solo hay que definir los constructores inteligentes y paso a paso.

Haciéndolo más rápido.

Ahora, estas implementaciones son fáciles de razonar, pero no tienen el modelo operativo más rápido. En particular, los usos asociados a la izquierda de ( > > = ) producen código asintóticamente más lento.

Para evitar que se puede aplicar la Codensity mónada a su mónada libre existente, o simplemente utilizar la 'Church free' mónada directamente, los cuales describo en profundidad en mi blog.

Http://comonad.com/reader/2011/free-monads-for-less /

Http://comonad.com/reader/2011/free-monads-for-less-2 /

Http://comonad.com/reader/2011/free-monads-for-less-3 /

El resultado de aplicar la versión codificada por Church de la mónada Libre es que obtienes un modelo fácil de razonar para el tipo de datos, y aún obtienes un modelo de evaluación rápido.

Así es como lo haría, usando mónadas libres. ¿Qué son? Son árboles con acciones en los nodos y valores en las hojas, con >>= actuando como injerto de árbol.

data f :^* x
  = Ret x
  | Do (f (f :^* x))

No es inusual escribir F^*X para tal cosa en las matemáticas, de ahí mi nombre de tipo de infijo malhumorado. Para crear una instancia, solo necesitas f que sea algo sobre lo que puedas mapear: cualquier Functor servirá.

instance Functor f => Monad ((:^*) f) where
  return = Ret
  Ret x  >>= k  = k x
  Do ffx >>= k  = Do (fmap (>>= k) ffx)

Eso es solo " aplicar k en todas las hojas e injertar los árboles resultantes". Estos árboles pueden representar estrategias para la computación interactiva: todo el árbol cubre todas las posibles interacciones con el entorno, y el entorno elige qué camino en el árbol seguir. ¿Por qué son libres ? Son solo árboles, sin una teoría ecuacional interesante en ellos, diciendo qué estrategias son equivalentes a qué otras estrategias.

Ahora vamos a tener un kit para hacer Funtores que corresponden a un montón de comandos que tal vez quiera ser capaz de hacerlo. Esta cosa

data (:>>:) s t x = s :? (t -> x)

instance Functor (s :>>: t) where
  fmap k (s :? f) = s :? (k . f)

Captura la idea de obtener un valor en xdespués de un comando con el tipo de entrada s y el tipo de salida t. Para hacer eso, debe elegir una entrada en s y explicar cómo continuar con el valor en x dada la salida del comando en t. Para mapear una función a través de tal cosa, la viras a la continuación. Hasta ahora, equipo estándar. Para nuestro problema, ahora podemos definir dos funtores:

type Modify s  = (s -> s) :>>: ()
type Yield     = () :>>: ()

Es como acabo de escribir los tipos de valor para los comandos que queremos ser capaces de hacer!

Ahora asegurémonos de que podemos ofrecer una opción entre esos comandos. Podemos demostrar que una elección entre funtores produce un funtor. Más equipamiento estándar.

data (:+:) f g x = L (f x) | R (g x)

instance (Functor f, Functor g) => Functor (f :+: g) where
  fmap k (L fx) = L (fmap k fx)
  fmap k (R gx) = R (fmap k gx)

Entonces, Modify s :+: Yield representa la elección entre modificar y ceder. Cualquier firma de comandos simples (comunicarse con el mundo en términos de valores en lugar de manipular cálculos) se puede convertir en un funtor de esta manera. Es una molestia que tengo que hacerlo a mano!

Eso me da tu mónada: la mónada libre sobre la firma de modificar y ceder.

type Pause s = (:^*) (Modify s :+: Yield)

Puedo definir los comandos modify y yield como one-do-then-return. Aparte de negociar la entrada ficticia para yield, eso es solo mecánico.

mutate :: (s -> s) -> Pause s ()
mutate f = Do (L (f :? Ret))

yield :: Pause s ()
yield = Do (R (() :? Ret))

La función step entonces da un significado a los árboles de estrategia. Es un operador de control , construyendo un cálculo (tal vez) desde otro.

step :: s -> Pause s () -> (s, Maybe (Pause s ()))
step s (Ret ())            = (s, Nothing)
step s (Do (L (f  :? k)))  = step (f s) (k ())
step s (Do (R (() :? k)))  = (s, Just (k ()))

La función step ejecuta la estrategia hasta que termina con un Ret, o cede, mutando el estado a medida que avanza.

El método general es así: separe los comandos (interactuando en términos de valores) de los operadores de control (manipulando cálculos); construya la mónada libre de" árboles de estrategia " sobre la firma de los comandos (manejando el controlador); implemente los operadores de control por recursión sobre la estrategia arbol.

No coincide exactamente con sus firmas de tipo, pero ciertamente simple:

{-# LANGUAGE FlexibleInstances, MultiParamTypeClasses, UndecidableInstances #-}
import Control.Monad.State

newtype ContinuableT m a = Continuable { runContinuable :: m (Either a (ContinuableT m a)) }
instance Monad m => Monad (ContinuableT m) where
    return = Continuable . return . Left
    Continuable m >>= f = Continuable $ do
        v <- m
        case v of
            Left  a -> runContinuable (f a)
            Right b -> return (Right (b >>= f))

instance MonadTrans ContinuableT where
    lift m = Continuable (liftM Left m)

instance MonadState s m => MonadState s (ContinuableT m) where
    get = lift get
    put = lift . put

yield :: Monad m => ContinuableT m a -> ContinuableT m a
yield = Continuable . return . Right

step :: ContinuableT (State s) a -> s -> (Either a (ContinuableT (State s) a), s)
step = runState . runContinuable

-- mutate unnecessary, just use modify

{-# LANGUAGE TupleSections #-}
newtype Pause s x = Pause (s -> (s, Either x (Pause s x)))

instance Monad (Pause s) where
  return x = Pause (, Left x)

  Pause k >>= f = Pause $ \s -> let (s', v) = k s in
                                case v of
                                  Left x -> step (f x) s'
                                  Right x -> (s', Right (x >>= f))

mutate :: (s -> s) -> Pause s ()
mutate f = Pause (\s -> (f s, Left ()))

yield :: Pause s ()
yield = Pause (, Right (return ()))

step :: Pause s x -> s -> (s, Either x (Pause s x))
step (Pause x) = x

Así es como yo escribiría esto. Di step una definición un poco más general, también podría llamarse runPause. De hecho, pensar en el tipo de step me lleva a la definición de Pause.

En el paquete monad-coroutine encontrará un transformador monad general. La Pause s mónada es la misma que Coroutine (State s) Id. Puedes combinar las corrutinas con otras mónadas.

Relacionado: la mónada Prompt en http://themonadreader.files.wordpress.com/2010/01/issue15.pdf

Nota: Esta respuesta está disponible como un archivo de Haskell alfabetizado en Gist.

Disfruté bastante este ejercicio. Traté de hacerlo sin mirar las respuestas, y valió la pena. Me llevó un tiempo considerable, pero el resultado es sorprendentemente cercano a dos de las otras respuestas, así como a la biblioteca monad-coroutine. Así que supongo que esta es una solución algo natural a este problema. Sin este ejercicio, no entendería cómo monad-coroutine realmente obrar.

Para agregar algún valor adicional, explicaré los pasos que finalmente me llevaron a la solución.

Reconociendo la mónada del estado

Ya que estamos tratando con estados, buscamos patrones que puedan ser efectivamente descritos por la mónada de estado. En particular, s - s es isomorfo a s -> (s, ()), por lo que podría ser reemplazado por State s (). Y la función del tipo s -> x -> (s, y) se puede voltear a x -> (s -> (s, y)), que es en realidad x -> State s y. Esto nos lleva a actualizar firmas

mutate :: State s () -    Pause s ()
step   :: Pause s () -    State s (Maybe (Pause s ()))

Generalización

Nuestra Pause mónada está actualmente parametrizada por el estado. Sin embargo, ahora vemos que realmente no necesitamos al estado para nada, ni usamos ningún detalle de la mónada estatal. Así que podríamos intentar hacer una solución más general que sea parametrizada por cualquier mónada:

mutate :: (Monad m) =    m () -> Pause m ()
yield  :: (Monad m) =    Pause m ()
step   :: (Monad m) =    Pause m () -> m (Maybe (Pause m ()))

También, podríamos tratar de hacer mutate y step más generales permitiendo cualquier tipo de valor, no solo (). Y al darse cuenta de que Maybe a es isomorfo a Either a () finalmente podemos generalizar nuestras firmas a

mutate :: (Monad m) =    m a -> Pause m a
yield  :: (Monad m) =    Pause m ()
step   :: (Monad m) =    Pause m a -> m (Either (Pause m a) a)

De modo que step devuelve el valor intermedio del cálculo.

Monad transformer

Ahora, vemos que en realidad estamos tratando de hacer una mónada a partir de una mónada - añadir alguna funcionalidad adicional. Esto es lo que generalmente se llama un transformador de mónada . Además, la firma de mutate es exactamente la misma que lift de MonadTrans. Lo más probable es que estemos a la derecha. pista.

La mónada final

La función step parece ser la parte más importante de nuestra mónada, define exactamente lo que necesitamos. Tal vez, esta podría ser la nueva estructura de datos? Probemos:

import Control.Monad
import Control.Monad.Cont
import Control.Monad.State
import Control.Monad.Trans

data Pause m a
    = Pause { step :: m (Either (Pause m a) a) }

Si la parte Either es Right, es solo un valor monádico, sin ningún suspensiones. Esto nos lleva a cómo implementar lo más fácil - el lift función de MonadTrans:

instance MonadTrans Pause where
    lift k = Pause (liftM Right k)

Y mutate es simplemente una especialización:

mutate :: (Monad m) => m () -> Pause m ()
mutate = lift

Si el Either part is Left, it represents the continued computation after a suspension. Así que vamos a crear una función para eso:

suspend :: (Monad m) => Pause m a -> Pause m a
suspend = Pause . return . Left

Ahora yield un cálculo es simple, simplemente suspendemos con un vacío cálculo:

yield :: (Monad m) => Pause m ()
yield = suspend (return ())

Aún así, nos estamos perdiendo la parte más importante. La instancia Monad. Vamos a arreglar se. Implementar return es simple, solo levantamos la mónada interna. Implementar >>= es un poco más complicado. Si el valor original Pause era solo un valor simple (Right y), entonces simplemente envolver f y como resultado. Si es un cómputo pausado que puede ser continuado (Left p), descendemos recursivamente a él.

instance (Monad m) => Monad (Pause m) where
    return x = lift (return x) -- Pause (return (Right x))
    (Pause s) >>= f
        = Pause $ s >>= \x -> case x of
            Right y     -> step (f y)
            Left p      -> return (Left (p >>= f))

Pruebas

Tratemos de hacer alguna función de modelo que use y actualice el estado, produciendo mientras que dentro del cálculo:

test1 :: Int -> Pause (State Int) Int
test1 y = do
            x <- lift get
            lift $ put (x * 2)
            yield
            return (y + x)

Y una función auxiliar que depura la mónada-imprime sus pasos intermedios a la consola:

debug :: Show s => s -> Pause (State s) a -> IO (s, a)
debug s p = case runState (step p) s of
                (Left next, s')     ->  print s' >> debug s' next
                (Right r, s')       ->  return (s', r)    

main :: IO ()
main = do
    debug 1000 (test1 1 >>= test1 >>= test1) >>= print

El resultado es

2000
4000
8000
(8000,7001)

Como se esperaba.

Corrutinas y mónada-corutina

Lo que hemos implementado es una solución monádica bastante general que implementa Corrutinas. Tal vez no es sorprendente que alguien tuviera la idea antes: -), y creó el paquete monad-coroutine. Menos sorprendente, es bastante similar a lo que creamos.

El paquete generaliza la idea aún más. El cálculo continuo se almacena dentro de un funtor arbitrario. Esto permite suspender muchas variaciones cómo para trabajar con cálculos suspendidos. Por ejemplo, para pasar un valoral llamador de resume (que llamamos step), o para esperar a que se proporcione un valor para continuar, etc.