Composing monadic effects

Mon, 02 Jan 2012 00:00:00 UT

In Haskell, monad transformers are used to combine effects provided by multiple monads.

Boring example: Writer, Reader, State

For instance, if we want to have a read-only environment plus a write-only logging facility, we can start with the Reader monad and add a logging facility to it with the WriterT monad transformer:

type MyMonad w r a = WriterT w (Reader r) a

Or, we could start with the Writer monad and put the ReaderT transformer on top of it:

type MyMonad w r a = ReaderT r (Writer w) a

In the end, it doesn’t matter which way we choose, as both are isomorphic to

type MyMonad w r a = r -> (a, w)

If we want to have a state as well, we can plug in the StateT transformer anywhere in the stack, and again the order doesn’t matter. The resulting monad is now isomorphic to the standard RWS (Reader-Writer-State) monad.

So, we say about those transformers that they commute (recall that Reader is just the ReaderT transformer applied to the Identity monad).

More interesting example: Either + Writer

Not every two transformers commute, though.

Suppose we want to write log messages, plus to be able to abort the computation.

There are two quite different ways to compose these effects.

There’s

type MyMonad e w a = ErrorT e (Writer w) a

isomorphic to (Either e a, w), and then there’s

type MyMonad e w a = WriterT w (Either e) a

isomorphic to Either r (a, w).

We can already see the difference from the types. In the first case, the w is there independently of the value of Either. In the second case, if the computation failed, the whole thing is Left msg, and we don’t get our log w back.

Let’s try the following to confirm our expectations:

> runWriter $ runErrorT $ tell "foo" >> throwError "err" >> tell "bar"
(Left "err","foo")
> runErrorT $ runWriterT $ tell "foo" >> throwError "err" >> tell "bar"
Left "err"

Developing intuition

When reasoning about a stack of monad transformers, it’s useful to keep in mind that a transformer knows nothing about its inner monad. It has to work “inside” that monad. It has no ability to alter or cancel the effects that happened before in that monad. (It can prevent those effects from happening, though — see tell "bar" above.)

In the first example above, which corresponds to ErrorT e (Writer w), the Error monad had to work inside the Writer monad. It simply had no way to tell the writer monad to “forget” what had been told to it before.

In the second example, corresponding to WriterT w (Either e) a, the main monad is now Either e. If it decides to fail, it will return just the error, and nothing else.

The same logic answers the question why there’s no IOT, an IO monad transformer. Imagine this:

do
    targetHit <- launchMissiles
    when targetHit $
        throwError "oops I did it again"

Since throwError happens in the base monad, the whole thing is just Left "oops I did it again" — nothing mentions any IO. But what about the missiles?

If this shallow explanation is not enough to make you comfortable with transformers, I’d advise to read (or even to write) the implementation of some standard transformers.

Even more interesting example: Parsec + State

The Parsec monad already allows us to have our own state, but let’s see how we can add one independently.

Again, we have two ways to layer ParsecT and StateT transformers on top of Identity: ParsecT s () (State u) a and StateT u (Parsec s ()) a. Is there a difference?

Recall that Parsec is a backtracking monad. It can execute one branch, fail, and then execute another branch. Do we observe the state changes that happened in the aborted branch?

This will be our test code:

((put 1 >> char 'b') <|> char 'a') >> get

We’ll try to run it with the input "a" and initial state 0. First, Parsec executes the left branch of <|>, fails, and proceeds with the right branch. If the state is “global”, then the final result will be 1. If the state is subject to backtracking, then we’ll see 0.

In the ParsecT s () (State u) a case, the base monad is State. ParsecT works inside that monad and cannot revert the effects that happened there. (It may seem that it could remember the state of a branch using get and then restore it using put; but a monad transformer has to be polymorphic in the underlying monad and thus cannot rely on existence of get and put.)

And indeed, the code

import Text.Parsec
import Control.Monad.State

main = print $ flip evalState 0 $ runParserT p () "-" "a"
    where p = ((put 1 >> char 'b') <|> char 'a') >> get

prints Right 1.

Let’s now try the second option: layering StateT on top of Parsec. We cannot use the code above as is, because types do not match: e.g. char 'b' has type Parsec s () Char, but we need StateT u (Parsec s ()) Char. Such an upgrade is done by the lift function.

Sometimes, however, we need to “downgrade” computations from StateT u (Parsec s ()) a to Parsec s () a.

For example, to implement a <|> operator of type

(<|>) :: StateT u (Parsec s ()) a -> StateT u (Parsec s ()) a -> StateT u (Parsec s ()) a

we need first to downgrade the arguments to plain Parsec computation, invoke Parsec’s own <|> and then upgrade the result back to StateT.

import Text.Parsec as P
import Control.Monad.State

main = print $ runParser (evalStateT p 0) () "-" "a"
  where
    p = ((put 1 >> char 'b') <|> char 'a') >> get

    char = lift . P.char

    a <|> b = StateT $ \s ->
        runStateT a s P.<|> runStateT b s

Notice how we explicitly run both branches of <|> with the same state. It’s no surprise now that the state will be “backtracked” and the result will be Right 0. By the way, this is the same result as would be achieved using Parsec’s internal state.

Roman Cheplyaka: articles

Composing monadic effects

Boring example: Writer, Reader, State

More interesting example: Either + Writer

Developing intuition

Even more interesting example: Parsec + State