Compose nested monads in Haskell

Question

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

(>>>=) :: (Monad m, Monad n) => m (na) -> (a -> m (nb)) -> m (nb) 

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

Edit: This seems to be impossible in the general case. But this is certainly possible in some special cases. For instance. if the inner monad is possible. Since this is possible for all Monads that I want to use, the presence of additional restrictions seems fine to me. So I am changing the question a bit:

What additional restrictions do I need on n, so the following is possible:

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

Answer 1

Extending comments: as shown in questions , you need to have some function n (ma) -> m (na) in order to be able to make the composition a monad.

If your inner monad is Traversable , then sequence provides such a function, and the following will be of the correct type:

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

A few well-known transformers are actually simple newtype wrappers over something equivalent to this (although basically things are defined with matching patterns, and not literally using instances of the internal monad Monad and Traversable ):

• MaybeT based on Maybe
• Either Based on Either
• WriterT based on (,) ( (,) usually does not have a specific Monad instance, and WriterT uses the wrong order of tuples to use it if it had - but in a spirit that it could have).
• ListT based on [] . Oh, screaming ...

The latter, in fact, is notorious that it is not a monad if the raised monad is “commutative”, otherwise expressions that must be equal to the laws of the monad can produce different orders of effects. My guess is that this comes essentially from lists, which can contain more than one value, unlike other reliably working examples.

So, although the above definition will be correctly printed, it can still violate the laws of the monad.

Just like an afterthought, another transformer is such a nested monad, but in a completely different way: ReaderT , based on the use of (->) as the external monad.