The Pause monad

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

Solution 2:

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.

The Pause monad

Solution 1:

Solution 2:

Related

Recent Posts