The Pause monad

coroutine, free-monad, haskell, monad-transformers, monads

Solution

Sure; you just let any computation either finish with a result, or suspend itself, giving an action to be used on resume, along with the state at the time:

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')

The `Monad` instance just sequences things in the normal way, passing the final result to the `k` continuation, or adding the rest of the computation to be done on suspension.

Problem

Monads can do many amazing, crazy things. They can create variables which hold a superposition of values. They can allow you to access data from the future before you compute it. They can allow you to write destructive updates, but not really. And then the continuation monad allows you to break people's minds! Ususally your own. ;-) But here's a challenge: Can you make a monad which can be paused? ``` data Pause s x instance Monad (Pause s) mutate :: (s -> s) -> Pause s () yield :: Pause s () step :: s -> Pause s () -> (s, Maybe (Pause s ())) ``` The `Pause` monad is a kind of state monad (hence `mutate`, with the obvious semantics). Normally a monad like this has some sort of "run" function, which runs the computation and hands you back the final state. But `Pause` is different: It provides a `step` function, which runs the computation until it calls the magical `yield` function. Here the computation is paused, returning to the caller enough information to resume the computation later. For extra awesomness: Allow the caller to modify the state between `step` calls. (The type signatures above ought to allow this, for example.) Use case: It's often easy to write code that does something complex, but a total PITA to transform it to also output the intermediate states in its operation. If you want the user to be able to change something mid-way through execution, things get complex really fast. Implementation ideas: Obviously it can be done with threads, locks and `IO`. But can we do better? ;-) Something insane with a continuation monad? Maybe some kind of writer monad, where `yield` just logs the current state, and then we can "pretend" to `step` it by iterating over the states in the log. (Obviously this precludes altering the state between steps, since we're not really "pausing" anything now.)

Original source