haskell - Is the composition of an arbitrary monad with a traversable always a monad?

Question

If I have two monads m and n, and n is traversable, do I necessarily have a composite m-over-n monad?

More formally, here's what I have in mind:

import Control.Monad
import Data.Functor.Compose

prebind :: (Monad m, Monad n) =>
         m (n a) -> (a -> m (n b)) -> m (n (m (n b)))
mnx `prebind` f = do nx <- mnx
                     return $ do x <- nx
                                 return $ f x

instance (Monad m, Monad n, Traversable n) => Monad (Compose m n) where
  return = Compose . return . return
  Compose mnmnx >>= f = Compose $ do nmnx <- mnmnx `prebind` (getCompose . f)
                                     nnx  <- sequence nmnx
                                     return $ join nnx

Naturally, this type-checks, and I believe works for a few cases that I checked (Reader over List, State over List) -- as in, the composed 'monad' satisfies the monad laws -- but I'm unsure if this is a general recipe for layering any monad over a traversable one.

Answer 1

No, it's not always a monad. You need extra compatibility conditions relating the monad operations of the two monads and the distributive law sequence :: n (m a) -> m (n a), as described for example on Wikipedia.

Your previous question gives an example in which the compatibility conditions are not met, namely

S = m = [], with unit X -> SX sending x to [x];

T = n = (->) Bool, or equivalently TX = X × X, with unit X -> TX sending x to (x,x).

The bottom right diagram on the Wikipedia page does not commute, since the composition S -> TS -> ST sends xs :: [a] to (xs,xs) and then to the Cartesian product of all pairs drawn from xs; while the right-hand map S -> ST sends xs to the "diagonal" consisting of only the pairs (x,x) for x in xs. It is the same problem that caused your proposed monad to not satisfy one of the unit laws.