Why are monad transformers different to stacking monads?

Question

In many cases, it isn't clear to me what is to be gained by combining two monads with a transformer rather than using two separate monads. Obviously, using two separate monads is a hassle and can involve do notation inside do notation, but are there cases where it just isn't expressive enough?

One case seems to be StateT on List: combining monads doesn't get you the right type, and if you do obtain the right type via a stack of monads like Bar (where Bar a = (Reader r (List (Writer w (Identity a))), it doesn't do the right thing.

But I'd like a more general and technical understanding of exactly what monad transformers are bringing to the table, when they are and aren't necessary, and why.

To make this question a little more focused:

1. What is an actual example of a monad with no corresponding transformer (this would help illustrate what transformers can do that just stacking monads can't).
2. Are StateT and ContT the only transformers that give a type not equivalent to the composition of them with m, for an underlying monad m (regardless of which order they're composed.)

(I'm not interested in particular implementation details as regards different choices of libraries, but rather the general (and probably Haskell independent) question of what monad transformers/morphisms are adding as an alternative to combining effects by stacking a bunch of monadic type constructors.)

(To give a little context, I'm a linguist who's doing a project to enrich Montague grammar - simply typed lambda calculus for composing word meanings into sentences - with a monad transformer stack. It would be really helpful to understand whether transformers are actually doing anything useful for me.)

Thanks,

Reuben

Tannenberg

What do you mean by "using two separate monads"? Can you give an example? – Deserving

Possible duplicate of mtl, transformers, monads-fd, monadLib, and the paradox of choice – Forelock

I've voted to close because it really does sound like you're asking for the difference between different monad transformer libraries, and that question already has an excellent answer. If you think that your question is different, perhaps you could elaborate. – Forelock

My question is really a theoretical one: what do monad transformers do, regardless of library choice, that stacking monads doesn't. By stacking monads, I mean having a type like (Writer w ([a])), where you have two monadic type constructors. I'm more interested in a category-theoretic answer than anything that pertains particularly to Haskell. – Tannenberg

Well - the List monad is kind of special because any expression which is a list is also a value in the List monad. Try to "stack" Writer and IO - Writer w (IO a) is a value in the Writer monad returning an IO a - and that's different from WriterT w IO a - which is a value in the WriterT w IO monad returning an a. – Deserving

hmm, IO is also maybe not the best example. What about (Writer w (Maybe a)) vs (MaybeT (Writer w) a)? These are, I think, the same type, mutatis mutandis, and act the same too. – Tannenberg

A monad transformer is simply a type t for which t m is a Monad for any Monad m. However, it is not true, in general, that the composition of two monads is a monad - because of this, there aren't many abstract operations (if any at all) that can be defined in terms of the composition of two monads (and without abstraction, programming in Haskell with monads would be very tedious). It is simply a coincidence that most of the transformers commonly encountered compositions of monads (i.e. WriterT x m is Compose m (x,)). – Lengel

@Lengel I'm not sure it's a coincidence that most of the transformers end up looking like composition. The easiest way to make one is roughly to see that for some particular monad its composition with any other monad will be a monad. The idea that we can do that with particular monads (with implementation specific to that monad) but not for all is basically where transformers came from. You're right that it's not necessary, but it's not a coincidence. – Bebe

@user2407038, there are also laws relating to lift. – Countervail

Related: #7041344 – Bercy

Answer 1

To answer you question about the difference between Writer w (Maybe a) vs MaybeT (Writer w) a, let's start by taking a look at the definitions:

newtype WriterT w m a = WriterT { runWriterT :: m (a, w) }
type Writer w = WriterT w Identity

newtype MaybeT m a = MaybeT { runMaybeT :: m (Maybe a) }

Using ~~ to mean "structurally similar to" we have:

Writer w (Maybe a)  == WriterT w Identity (Maybe a)
                    ~~ Identity (Maybe a, w)
                    ~~ (Maybe a, w)

MaybeT (Writer w) a ~~ (Writer w) (Maybe a)
                    == Writer w (Maybe a)
                    ... same derivation as above ...
                    ~~ (Maybe a, w)

So in a sense you are correct -- structurally both Writer w (Maybe a) and MaybeT (Writer w) a are the same - both are essentially just a pair of a Maybe value and a w.

The difference is how we treat them as monadic values. The return and >>= class functions do very different things depending on which monad they are part of.

Let's consider the pair (Just 3, []::[String]). Using the association we have derived above here's how that pair would be expressed in both monads:

three_W :: Writer String (Maybe Int)
three_W = return (Just 3)

three_M :: MaybeT (Writer String) Int
three_M = return 3

And here is how we would construct a the pair (Nothing, []):

nutin_W :: Writer String (Maybe Int)
nutin_W = return Nothing

nutin_M :: MaybeT (Writer String) Int
nutin_M = MaybeT (return Nothing)   -- could also use mzero

Now consider this function on pairs:

add1 :: (Maybe Int, String) -> (Maybe Int, String)
add1 (Nothing, w) = (Nothing w)
add1 (Just x, w)  = (Just (x+1), w)

and let's see how we would implement it in the two different monads:

add1_W :: Writer String (Maybe Int) -> Writer String (Maybe Int)
add1_W e = do x <- e
             case x of
               Nothing -> return Nothing
               Just y  -> return (Just (y+1))

add1_M :: MaybeT (Writer String) Int -> MaybeT (Writer String) Int
add1_M e = do x <- e; return (e+1)
  -- also could use: fmap (+1) e

In general you'll see that the code in the MaybeT monad is more concise.

Moreover, semantically the two monads are very different...

MaybeT (Writer w) a is a Writer-action which can fail, and the failure is automatically handled for you. Writer w (Maybe a) is just a Writer action which returns a Maybe. Nothing special happens if that Maybe value turns out to be Nothing. This is exemplified in the add1_W function where we had to perform a case analysis on x.

Another reason to prefer the MaybeT approach is that we can write code which is generic over any monad stack. For instance, the function:

square x = do tell ("computing the square of " ++ show x)
              return (x*x)

can be used unchanged in any monad stack which has a Writer String, e.g.:

WriterT String IO
ReaderT (WriterT String Maybe)
MaybeT (Writer String)
StateT (WriterT String (ReaderT Char IO))
...

But the return value of square does not type check against Writer String (Maybe Int) because square does not return a Maybe.

When you code in Writer String (Maybe Int), you code explicitly reveals the structure of monad making it less generic. This definition of add1_W:

add1_W e = do x <- e 
              return $ do 
                y <- x 
                return $ y + 1

only works in a two-layer monad stack whereas a function like square works in a much more general setting.

Deserving

Thanks, this is helpful. But I think my question still stands. Suppose for add1_W, you wrote the following: add1_W e = do x <- e return $ do y <- x return $ y + 1 This is still more of a hassle than add1_M, but doesn't require any case statements, and uses both the maybe and writer monads. – Tannenberg

One small correction: in add1_M I believe you mean return (x+1). – Anglocatholic

Answer 2

What is an actual example of a monad with no corresponding transformer (this would help illustrate what transformers can do that just stacking monads can't).

IO and ST are the canonical examples here.

Are StateT and ContT the only transformers that give a type not equivalent to the composition of them with m, for an underlying monad m (regardless of which order they're composed.)

No, ListT m a is not (isomorphic to) [m a]:

newtype ListT m a =
  ListT { unListT :: m (Maybe (a, ListT m a)) }

Dorothy

Might be interesting to note that it's still almost the composition, you just have to move the composition under the fixed point: List a = Fix (1 + a * x) and ListT m a = Fix (m ∘ (1 + a * x)) – Gaulin

I don't think anyone knows an explicit example of a monad that has no transformer. IO and ST monads are opaque - they are not given as explicit type expressions, they are implemented somehow at low level by the library. All known explicit monads have transformers, but I don't think anyone knows why. – Huxley

Actually I might have two examples of monads that appear to have no transformers (but I don't know how to prove that they don't have transformers, so I might be wrong here). My examples are type C r a = Either a ((a -> r) -> r) and type D r a = Either a ((a -> Bool) -> Maybe a). – Huxley

Generally, monad transformers can be classified in 5 different families. 1) functor composition in one or another order (EitherT, WriterT, ReaderT and Q a = (h a) -> a where h is an arbitrary contrafunctor), 2) adjunction recipe (StateT, ContT), 3) recursive recipe (ListT, FreeT), 4) Cartesian product of monads, 5) free pointed monad P a = Either a (m a) where m is another monad. Among these, ContT do not admit the lifting of the base monad Cont r a -> ContT r a, and so can't really be considered a fully featured monad transformer, and so are other monads constructed out of Cont. – Huxley

@Huxley Would you please provide more resources to read about this classification? – Ptomaine

I now believe I was wrong to claim (back in 2019) that the monads type C r a = Either a ((a -> r) -> r) and type D r a = Either a ((a -> Bool) -> Maybe a) have no transformers. I have worked on this question for some time and figured out how to write transformers for them. – Huxley

@KareemTaha I have added more detail in my answer below. – Huxley

Answer 3

To make this question a little more focused:

1. What is an actual example of a monad with no corresponding transformer (this would help illustrate what transformers can do that just stacking monads can't).

There are no known examples of a monad that lacks a transformer, as long as the monad is defined explicitly as a pure lambda-calculus term, with no side effects and no external libraries being used. The Haskell monads such as IO and ST are essentially interfaces to an external library defined by low-level code. Those monads cannot be defined by pure lambda-calculus, and their monad transformers probably do not exist.

Even though there are no known explicit examples of monads without transformers, there is also no known general method or algorithm for obtaining a monad transformer for a given monad. One could define an arbitrarily complicated type constructor that combines products, co-products, and function types, for example like this code in Haskell:

 type D a = Either a ((a -> Bool) -> Maybe a)

One can implement the monad's methods for D and prove that the monad laws hold, but it is far from obvious how to define a transformer for the monad D.

This D may be a contrived and artificial example of a monad, but there might be legitimate cases for using that monad, which is a "free pointed monad on the Search monad on Maybe".

To clarify: A "search monad on n" is the type S n q a = (a -> n q) -> n a where n is another monad and q is a fixed type.

A "free pointed monad on M" is the type P a = Either a (M a) where M is another monad.

In any case, I just want to illustrate the point. I don't think it would be easy for anyone to come up with the monad transformer for D and then to prove that it satisfies the laws of monad transformers. There is no known algorithm that would takes an arbitrary monad's code, such as the code of D, and then generate the code for its transformer.

2. Are StateT and ContT the only transformers that give a type not equivalent to the composition of them with m, for an underlying monad m (regardless of which order they're composed.)

Monad transformers are necessary because stacking two monads is not always a monad. Most "simple" monads, like Reader, Writer, Maybe, etc., stack with other monads in a particular order. But the result of stacking, say, Writer + Reader + Maybe, is a more complicated monad that no longer allows stacking with new monads.

There are several examples of monads that do not stack at all: State, Cont, List, Free monads, the Codensity monad, and a few other, less well known monads, like the "free pointed" monad shown above.

For each of those "non-stacking" monads, one needs to guess the correct monad transformer somehow.

I have studied this question for a while and I have assembled a list of techniques for creating monad transformers, together with full proofs of all laws. There doesn't seem to be any system to creating a monad transformer for a specific monad. I even found a couple of monads that have two inequivalent transformers.

Generally, monad transformers can be classified in 6 different families:

1. Functor composition in one or another order: EitherT, WriterT, ReaderT and a generalization of Reader to a special class of monads, called "rigid" monads. An example of a "rigid" monad is Q a = (H a) -> a where H is an arbitrary (but fixed) contravariant functor.

2. The "adjunction recipe": StateT, ContT, CodensityT, SearchT, which gives transformers that are not functorial.

3. The "recursive recipe": ListT, FreeT

4. Cartesian product of monads: If M and N are monads then their Cartesian product, type P a = (M a, N a) is also a monad whose transformer is the Cartesian product of transformers.

5. The free pointed monad: P a = Either a (M a) where M is another monad. For that monad, the transformer's type is m (Either a (MT m a)) where MT is the monad M's transformer.

6. Monad stacks, that is, monads obtained by applying one or more monad transformers to some other monad. A monad stack's transformer is build via a special recipe that uses all the transformers of the individual monads in the stack.

There may be monads that do not fit into any of these cases, but I have seen no examples so far.

Details and proofs of these constructions of monad transformers are in my draft book here https://github.com/winitzki/sofp

Huxley

You might also find this question interesting: Is the monad transformer of a monad unique in Haskell? – Dorothy

@DanielWagner Thank you. I posted an answer to that question. – Huxley