Modular Monad Transformers

September 4th, 2008 by Mauro Jaskelioff

Monad are an essential tool for functional programmers. When it comes to combining monads, the most popular technique is to use monad transformers to add an effect layer to an existing monad. Do you want a new state for your monad? Use the state monad transformer on your monad and voila! it’s done!

Actually, you are not really done. Monads usually come with a set of operations to manipulate the effect they model. For example, the state monad comes with operations for reading and updating the state (get and put), and the environment monad (Reader in Haskell) comes with operations for reading the environment and performing a computation in a modified environment (ask and local). If you want the operations of your monad to be supported by the transformed monad, then you need to show how to lift the operations to the transformed monad. Unless a technology is used for automating these liftings, you need to provide an operation instance for every monad transformer in the library, leading to $\mathcal{O}(n^2)$ operation instances. That’s not modular!

The problem is not in monad transformers (other technologies for combining monads such as distributive laws or coproduct of monads suffer from the same problem). The problem is that many of the operations associated with a monad are not really compatible with the monad.

Monads have axioms that ensure that return and bind are well-behaved, so it is not unreasonable to think that there should be some axioms associated to its operations. So I propose to require operations to be algebraic. In our context this means that an operation h for a monad M should be of type forall a . S (M a) -> M a for some functor S, such that:

join . h = h. fmap join

where join is the multiplication of the monad join = (>>= id).

For example, uncurry (++) :: ([a],[a]) -> [a] is algebraic for the list monad, with S a = (a,a). On the other hand, uncurry local :: (r->r, Reader r a) -> Reader r a has the correct type, with functor S a = (r -> r, a), but is not algebraic, as the condition does not hold. The operation ask :: Reader r r doesn’t seem to have the correct type, but it is isomorphic to a function ask' :: (r -> Reader r a) -> Reader r a, which is algebraic for Reader r with S a = r -> a. It’s convenient to consider algebraic operations up to isomorphism. Then, ask and (++) are algebraic.

So, what’s good about algebraic operations? They can be lifted by any monad morphism! Every algebraic operation is isomorphic to a natural transformation in the Kleisli category of the monad.

%format . = “\cdot”

toK      :: (Functor s, Monad m) =>  (forall a. s (m a) -> m a) ->
                                     (forall a. s a -> m a)
toK f    = f . fmap return

fromK    :: (Functor s, Monad m) =>  (forall a. s a -> m a) ->
                                     (forall a. s (m a) -> m a)
fromK k  = join . k

This means that for every algebraic operation h :: forall a. S (M a) -> M a, monad N, and monad morphism lift :: forall a. M a -> N a, we get an algebraic operation fromK (lift. toK h) :: forall a. S (N a) -> N a, i.e. the lifting of h to N.

Append is algebraic for the list monad, so we get a “liftable” version of append: for every monad morphism out of the list monad, we get a lifted operation.

%format . = “\cdot”

appendL           :: Monad m => (forall x. [x] -> m x) -> m a -> m a -> m a
appendL mm x y  = join  $ mm  $ return x ++ return y

Of course, not all the usual operations are algebraic for their monad. This does not mean that the operation is incorrect, but that the monad should be more powerful. The operations determine the appropriate monad.

The operation local is not an algebraic for Reader but can become algebraic if we implement the environment monad with State:

%format . = “\cdot”

type Reader' r a  = State r a

reader'           :: (r -> a) -> Reader' r a
reader' e         = State (\r -> (e r, r))

runReader'        :: Reader' r a -> r -> a
runReader' r      = fst . runState r

local'           :: (r -> r) -> Reader' r a -> Reader' r a
local' f a       = join  $ State  $ \r -> (a, f r)

localL           :: Monad t =>  (forall x. Reader' r x -> t x) ->
                                (r -> r) -> t a -> t a
localL lift f t  = join $ lift $ State  (\r -> (t, f r))


Since local' is algebraic for Reader', we get a liftable operation localL. The apparently arbitrary move from Reader into State seems like a big eureka step. Actually, it’s the result of applying a general technique for finding appropriate monads for a given set of operations (paper in process).

Using these ideas, I managed to re-implement the monad transformer library with automatic lifting of operations. I will release the library as soon as I write a minimum of documentation.

10 Responses to “Modular Monad Transformers”

  1. Luke Palmer Says:

    Very nice work! I have been wondering about this and related problems recently, and I would call this a fine result. Thanks!

  2. Luke Palmer Says:

    Upon further investigation, it looks like your law is incorrect. I think you mean:

    h >=> f = h . fmap (>>= f)

  3. Dave Menendez Says:

    I’m confused by the analysis of local. First, if S a = (r -> r) -> a, then S (Reader r a) -> Reader r a = ((r -> r) -> Reader r a) -> Reader r a, which is not the type of local. Maybe S a = (r -> r, a)?

    Second, local’ doesn’t seem to act like local. If I understand the given definition, then in local’ f e1 >>= e2, the changed environment created by f will be visible in e1 and e2, instead of just e1.

  4. Mauro Jaskelioff Says:

    Thanks, Luke. I think you are right. The law should be,

    h (>>= (>>=f)) = h . fmap (>>=(>>=f))

    or equivalently

    join . h = h . fmap join

    (I’m going to edit it in the main post)

  5. Mauro Jaskelioff Says:

    Ugh! I shouldn’t post things when I’m tired.

    Dave: As you say, the correct functor for local is the pair
    S a = (r->r, a), and of course local is the curried version of
    S (Reader r a) -> Reader r a.

    The function local' is algebraic, and its semantics will be preserved by the liftings However, as you mention, the semantics of local’ are not the same as those of local (I admit the name is totally misleading). You can get the semantics of the old local in the following manner:

    reallocal :: (r->r) -> Reader r a -> Reader r a
    reallocal f m = do
    old < - ask
    a <- local f m
    local (const old) (return a)

  6. Mauro Jaskelioff Says:

    (accidentally pressed return, should be Reader’ and not Reader, local’ and not local, and ask’ and not ask).
    reallocal is not algebraic, and hence, not liftable. However, it is actually defined for any monad which supports ask' and local' and those are liftable.

    Sorry for all the confusion.

  7. Dave Menendez Says:

    So local’ is just set in disguise.

    local’ f m = get >>= \s -> set (f s) >> m

    I don’t mean to be negative, but I’m not seeing how this technique makes anything simpler. Defining a state reader in terms of a state transformer is already trivial, and defining a morphism from [] into a given monad seems at least as complicated as defining mzero and mplus directly.

  8. Mauro Jaskelioff Says:

    The fact that defining Reader in term of State is trivial (and this is a good thing). What you gain is that you don’t need to define, ask and local for every monad transformer!

    Also, the monad morphism from [] into another monad is exactly what you get with any monad transformer. For example,

    lift :: [a] -> StateT s [a].

  9. Dave Menendez Says:

    Again, lifting get and set through a monad transformer is already trivial. Instead of two boilerplate definitions (“lift get” and “lift . set”), you have one boilerplate definition for the monad morphism (something like “lift . liftState”).

    The example of appendL is more compelling.

    What about other operations? I’m guessing that throwError is algebraic and catchError is not.

  10. Mauro Jaskelioff Says:

    Actually you don’t need any boilerplate definitions. If all the operations are algebraic (for example, get and put) then you can write:

    instance (MonadState s m, MonadTrans t, Monad (t m)) => MonadState s (t m) where
    get = lift get
    put = lift . put

    and the boilerplate is gone. The surprising thing is that you can do the same for other operations. I showed above the simplest example that I know of, which is for ask and local, but the same technique can be applied to other operations. There is a general technique which allows you to determine the appropriate monad in which catchError is algebraic (catchError is not algebraic with the current semantics). This same technique yields State as the appropriate monad for local.

Leave a Reply