## Modular Monad Transformers

September 4th, 2008 by Mauro JaskelioffMonad 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 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.

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.

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`

:

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.

September 4th, 2008 at 9:49 pm

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

September 4th, 2008 at 9:57 pm

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

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

September 5th, 2008 at 5:16 am

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.

September 5th, 2008 at 8:19 am

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)

September 5th, 2008 at 10:49 am

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)

September 5th, 2008 at 10:56 am

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

September 5th, 2008 at 3:16 pm

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.

September 5th, 2008 at 3:37 pm

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

September 5th, 2008 at 4:48 pm

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.

September 6th, 2008 at 9:29 am

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.