The Pause monad

Question

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

Answer 1

Note: that you provided yourself no direct access to the current state s in this monad.

Pause s is just a free monad over the mutate and yield operations. Implemented directly you get:

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) 

with a couple of smart constructors to give you the desired API:

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

and the step function to drive it

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) 

You could also define this directly using

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

(from my 'free' package) with

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

then we already have a monad for Pause

type Pause s = Free (Op s) 

and just need to define the smart constructors and stepper.

Making it faster.

Now, these implementations are easy to reason about, but they don't have the fastest operational model. In particular, left associated uses of (>>=) yield asymptotically slower code.

To get around that you can apply the Codensity monad to your existing free monad, or just use the 'Church free' monad directly, both of which I describe in depth on my 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/

The result of applying the Church encoded version of the Free monad is that you get an easy to reason about model for the data type, and you still get a fast evaluation model.