In a monad transformer, why is the known monad the inner one?

Question

For example, MaybeT is defined as:

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

But not:

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

Why is this?

Answer 1

After expanding newtypes, we have join :: Monad m => m (Maybe (m (Maybe a))) -> m (Maybe a) in the first case and join :: Monad m => Maybe (m (Maybe (m a))) -> Maybe (m a) in the second.

To implement the first join you need a way to distribute Maybe over m: dist1 :: Monad m => Maybe (m a) -> m (Maybe a) :

join1 :: m (Maybe (m (Maybe a))) -> m (Maybe a)
join1 = fmap join . join . fmap dist1

To implement the second join you need the opposite distributive law dist2 :: Monad m => m (Maybe a) -> Maybe (m a)

join2 :: Maybe (m (Maybe (m a))) -> Maybe (m a)
join2 = fmap join . join . fmap dist2

dist1 is easy to implement (I'll leave proving the monad transformer laws to you):

dist1 :: Monad m => Maybe (m a) -> m (Maybe a) 
dist1 = sequenceA

dist2 is not so easy. It can't be done for an arbitrary Monad. As a counterexample, let's pick m to be the "reader" monad (->) r:

dist2 :: (r -> Maybe a) -> Maybe (r -> a)

Since you don't have access to an r, the only implementation of dist2 that'll typecheck is const Nothing, which clearly won't satisfy the monad laws.

Answer 2

Looking at StateT might be instructive:

newtype StateT s m a = StateT { runStateT :: s -> m (a,s) }

Here the state is neither "inner" nor "outer", but its type is interleaved with the monad it is transforming, some bits inside, some outside. And indeed

newtype ReaderT r m a = ReaderT { runReaderT :: r -> m a }

is all "outer". So it depends on what transformer it is. There's probably some category theory that at least partially explains this interleaving, I'm curious to know about it (intelligentsia?).

Contrast with applicative functors, for which

newtype Compose f g a = Compose { getCompose :: f (g a) }

is an applicative as well, so there is always a clear "inner/outer" relationship. You could make an applicative-only StateT, and finding its structure by Compose (State s):

ApplicativeStateT s f a = s -> (s, f a)

In fact, there's another one if you compose on the right:

ApplicativeStateT' s f a = f (s -> (s,a))

But monads have no such regularity.