Compose nested Monads in Haskell

Question

Is there a way to implement bind for nested monads? What I want is the following signature:

(>>>=) :: (Monad m, Monad n) => m (n a) -> (a -> m (n b)) -> m (n b)

It looks like it should be a trivial task, but I somehow just can't wrap my head around it. In my program, I use this pattern for several different combinations of monads and for each combination, I can implement it. But for the general case, I just don't understand it.

Edit: It seems that it is not possible in the general case. But it is certainly possible in some special cases. E.g. if the inner Monad is a Maybe. Since it IS possible for all the Monads I want to use, having additional constraints seems fine for me. So I change the question a bit:

What additional constraints do I need on n such that the following is possible?

(>>>=) :: (Monad m, Monad n, ?? n) => m (n a) -> (a -> m (n b)) -> m (n b)

Answer 1

Expanding on the comments: As the linked questions show, it is necessary to have some function n (m a) -> m (n a) to even have a chance to make the composition a monad.

If your inner monad is a Traversable, then sequence provides such a function, and the following will have the right type:

(>>>=) :: (Monad m, Monad n, Traversable n) => m (n a) -> (a -> m (n b)) -> m (n b)
m >>>= k = do
    a <- m
    b <- sequence (map k a)
    return (join b)

Several well-known transformers are in fact simple newtype wrappers over something equivalent to this (although mostly defining things with pattern matching instead of literally using the inner monads' Monad and Traversable instances):

• MaybeT based on Maybe
• ExceptT based on Either
• WriterT based on (,) ((,) doesn't normally have its Monad instance defined, and WriterT is using the wrong tuple order to make use of it if it had - but in spirit it could have).
• ListT based on []. Oh, whoops...

The last one is in fact notorious for not being a monad unless the lifted monad is "commutative" - otherwise, expressions that should be equal by the monad laws can give different order of effects. My hunch is that this comes essentially from lists being able to contain more than one value, unlike the other, reliably working examples.

So, although the above definition will be correctly typed, it can still break the monad laws.

Also as an afterthought, one other transformer is such a nested monad, but in a completely different way: ReaderT, based on using (->) as the outer monad.