haskell - La mónada Pausa

monads coroutine

Question

Las mónadas pueden hacer muchas cosas increíbles y locas. Pueden crear variables que contienen una superposición de valores. Pueden permitirle acceder a los datos del futuro antes de calcularlos. Te pueden permitir escribir actualizaciones destructivas, pero no realmente. ¡Y luego la mónada de continuación te permite romper las mentes de las personas! Ususalmente tuyo. ;-)

Pero aquí hay un desafío: ¿puedes hacer una mónada que se pueda pausar ?

data Pause s x instance Monad (Pause s) mutate :: (s -> s) -> Pause s () yield :: Pause s () step :: s -> Pause s () -> (s, Maybe (Pause s ()))

La mónada Pause es un tipo de mónada de estado (por lo tanto, mutate , con la semántica obvia). Normalmente, una mónada como esta tiene algún tipo de función "ejecutar", que ejecuta el cálculo y te devuelve el estado final. Pero Pause es diferente: proporciona una función de step , que ejecuta el cálculo hasta que llama a la función de yield mágico. Aquí el cálculo se pausa, volviendo a la persona que llama la información suficiente para reanudar el cálculo más tarde.

Para mayor asombro: permita que la persona que llama modifique el estado entre llamadas de step . (Las firmas tipo arriba deberían permitir esto, por ejemplo).

Caso de uso: a menudo es fácil escribir código que hace algo complejo, pero un PITA total para transformarlo también muestra los estados intermedios en su operación. Si desea que el usuario pueda cambiar algo a mitad de la ejecución, las cosas se vuelven complejas muy rápido.

Ideas de implementación:

• Obviamente se puede hacer con hilos, bloqueos e IO . ¿Pero podemos hacerlo mejor? ;-)

• ¿Algo loco con una mónada de continuación?

• Tal vez algún tipo de mónada de escritor, donde el yield simplemente registra el estado actual, y luego podemos "pretender" que lo pase iterando sobre los estados en el registro. (Obviamente esto impide modificar el estado entre pasos, ya que en realidad no estamos "pausando" nada ahora).

Answer 1

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

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 infijo malhumorado. Para hacer una instancia, solo necesitas que f sea ​​algo sobre lo que puedas mapear: cualquier Functor .

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 en los árboles resultantes". Estos árboles pueden representar estrategias de computación interactiva: el árbol completo cubre todas las interacciones posibles con el entorno, y el entorno elige qué camino seguir en el árbol. ¿Por qué son libres ? Son solo árboles, sin una teoría ecuacional interesante sobre ellos, que dicen qué estrategias son equivalentes a qué otras estrategias.

Ahora tengamos un kit para hacer Functors que corresponda a un conjunto de comandos que podríamos querer hacer. 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 x después de un comando con tipo de entrada s y tipo de salida t . Para hacer eso, debe elegir una entrada en s explicar cómo continuar con el valor en x dado el resultado del comando en t . Para asignar una función a través de tal cosa, vuélvala 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 si acabara de escribir los tipos de valores para los comandos que queremos poder hacer!

Ahora asegurémonos de que podemos ofrecer una opción entre esos comandos. Podemos demostrar que una elección entre funtores produce un functor. Equipamiento más 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)

Por lo tanto, Modify s :+: Yield representa la elección entre modificar y ceder. Cualquier firma de comandos simples (comunicándose con el mundo en términos de valores en lugar de manipular los cálculos) se puede convertir en un functor de esta manera. ¡Es una molestia tener 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 modificar y ceder como one-do-then-return. Además de negociar la entrada ficticia para el yield , eso es simplemente mecánico.

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

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

La función de step le da un significado a los árboles de estrategia. Es un operador de control , construyendo un cálculo (tal vez) de 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 de step ejecuta la estrategia hasta que finaliza con Ret , o cede, mutando el estado a medida que avanza.

El método general es el siguiente: separar los comandos (que interactúan en términos de valores) de los operadores de control (manipulación de cálculos); construir la mónada libre de "árboles de estrategia" sobre la firma de comandos (poner el mango); implementar los operadores de control por recursión en los árboles de estrategia.

Answer 2

No coincide con sus firmas de tipo exactamente, 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

Answer 3

Nota: Esta respuesta está available como un archivo Haskell literario en Gist.

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

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

Reconociendo la mónada del estado

Como estamos tratando con estados, buscamos patrones que puedan ser descritos efectivamente por la mónada estatal. 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 en realidad es x -> State sy . Esto nos lleva a firmas actualizadas

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

Generalización

Nuestra mónada de Pause está actualmente parametrizada por el estado. Sin embargo, ahora vemos que realmente no necesitamos el estado para nada, ni usamos ninguna especificación de la mónada estatal. Entonces podríamos tratar de hacer una solución más general que esté 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 ()))

Además, podríamos tratar de hacer mutate y step un step más general al permitir cualquier tipo de valor, no solo () . Y al darnos cuenta de que Maybe a es isomorfo a Either a () podemos finalmente generalizar nuestras firmas para

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 ese step devuelve el valor intermedio del cálculo.

Transformador de mónada

Ahora, vemos que en realidad estamos tratando de hacer una mónada a partir de una mónada: agregue alguna funcionalidad adicional. Esto es lo que generalmente se llama un transformador de mónada . Además, la firma de MonadTrans es exactamente igual a la lift desde MonadTrans . Lo más probable es que estemos en el camino correcto.

La mónada final

La función de 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? Intentemos:

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 está en lo cierto, es solo un valor monádico, sin ninguna suspensión. Esto nos lleva a implementar lo fácil: la función de lift 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 la parte Either deja, representa el cálculo continuo después de una suspensión. 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 cálculo vacío:

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

Aún así, nos falta la parte más importante. La instancia de Monad . Vamos a arreglarlo Implementar el return es simple, simplemente levantamos la mónada interna. Implementar >>= es un poco más complicado. Si el valor de Pause original fue solo un valor simple ( Right y ), entonces simplemente envolvemos fy como resultado. Si se trata de un cálculo detenido que se puede continuar ( Left p ), descendemos recursivamente en é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

Probemos hacer alguna función de modelo que use y actualice el estado, cediendo mientras se está 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 en 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.

Coroutines y monad-coroutine

Lo que hemos implementado es una solución monádica bastante general que implementa Coroutines . Tal vez no sea sorprendente que alguien haya tenido la idea antes :-), y haya creado 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 suspend muchas variaciones de cómo trabajar con cálculos suspendidos. Por ejemplo, pasar un valor a la persona que llama de la resume (que llamamos step ), o esperar a que se proporcione un valor para continuar, etc.

Answer 4

Nota: que no proporcionó acceso directo al estado actual de esta mónada.

Pause s es solo una mónada libre sobre las operaciones de mutate y yield . Implementado directamente usted 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 de paso 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 puedes 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 necesita definir los constructores inteligentes y el paso a paso.

Haciéndolo más rápido.

Ahora bien, 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 un código asintóticamente más lento.

Para Codensity puedes aplicar la mónada Codensity a tu mónada libre existente, o simplemente usar directamente la mónada ''Church free'' , que 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 Free es que obtiene un modelo fácil de razonar para el tipo de datos, y aún obtiene un modelo de evaluación rápido.

Answer 5

Por supuesto; simplemente deja que cualquier cálculo termine con un resultado, o se suspenda, dando una acción para usar en el currículum, junto con el estado en el momento:

data Pause s a = Pause { runPause :: s -> (PauseResult s a, s) }

data PauseResult s a
    = Done a
    | Suspend (Pause s a)

instance Monad (Pause s) where
    return a = Pause (/s -> (Done a, s))
    m >>= k = Pause $ /s ->
        case runPause m s of
            (Done a, s'') -> runPause (k a) s''
            (Suspend m'', s'') -> (Suspend (m'' >>= k), s'')

get :: Pause s s
get = Pause (/s -> (Done s, s))

put :: s -> Pause s ()
put s = Pause (/_ -> (Done (), s))

yield :: Pause s ()
yield = Pause (/s -> (Suspend (return ()), s))

step :: Pause s () -> s -> (Maybe (Pause s ()), s)
step m s =
    case runPause m s of
        (Done _, s'') -> (Nothing, s'')
        (Suspend m'', s'') -> (Just m'', s'')

La instancia de Monad simplemente secuencia las cosas de la manera normal, pasando el resultado final a la continuación k , o agregando el resto del cálculo que se realizará en suspensión.

Answer 6

{-# 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 escribí esto. Le di un step más de definición general, podría llamarse también runPause . De hecho, pensar en el tipo de step me lleva a la definición de Pause .

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

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