I came across a useful Reddit post and since that place has gone down the drain I thought I’d preserve it here:
It is a well known in Haskell folklore that monads don’t combine, but what does that mean exactly?
Redditor /u/kn2322 shared a nice list of publications:
King and Wadler 1992: Combining Monads
This seems to be the first publication.
Jones and Duponcheel 1993: Composing Monads
This is a more accessible explanation. Here is an excerpt from the abstract:
In practice, it is usually possible to construct a monad that supports some specific combination of features. However, the techniques used are typically ad-hoc and it is very difficult to find general techniques for combining arbitrary monads. This report gives three general constructions for the composition of monads, each of which depends on the existence of an auxiliary function linking the monad structures of the components. In each case, we establish a set of laws that the auxiliary function must satisfy to ensure that the composition is itself a monad.
McBride and Paterson 2005: Applicative Programming with Effects
This reintroduces the problem of monad composition and proposes applicatives as a weaker notion which does compose.
Of course recently algebraic effects have become a popular way to combine monad-like structures which are more powerful than applicatives. A good strating point is Swierstra’s Data types à la carte which introduces free monads.
I think combine is adequate to convey the concept informally (see the title of the first paper). If I had to choose between your options I’d choose “compose”, but I think “commute” also plays a role.
I think being precise here is important because those are actually separate issues:
Arbitrary Monads don’t compose, yes, but in practice that doesn’t really matter since ~all monads are actually monad transformers and transformers compose.
Monad transformers don’t commute. StateT s (ExceptT e Identity) behaves subtly differently than ExceptT e (StateT s Identity) and despite not being quite as known in the folklore, this is something that leads to actual bugs in practice (especially with MTL-style where the order is only defined when the transformers are actually discharged, and any function that uses MonadError and MonadState can in principle be used with both StateT ... ExceptT ... and ExceptT ... StateT ...)
I found it. Jumper149 showed me how to do it using the deriving-trans package. It uses ComposeT and a type called Elevator. Then for a mtl-style monad class MonadFoo and transformer FooT, you have to define four instances:
The regular MonadFoo (FooT m a)
An instance MonadFoo (ComposeT FooT t m) (can be derived using 1)
An instance MonadFoo m => MonadFoo (Elevator t m)
An instance MonadFoo (t' m) => MonadFoo (ComposeT t t' m)
In any case, I think the practical limitations of Haskell are overshadowing the theoretical issues, which are discussed in for example the composing monads paper linked above. That also mentions that some monads do compose and characterises when that is the case.
Finally, I still stand behind my choice of keeping the wording in the title vague and appreciate that we can now discuss both composition and commutation in this thread.
MonadTrans t has a superclass constraint forall m. Monad m => Monad (t m), so following that twice already gives you an instance for Monad (f (g m)).
This superclass is (comparatively) recent, so it presumably didn’t exist yet when the instances for mmorph and deriving-trans were written. (and since Monad (f (g m)) is implied by the two MonadTrans constraints, their instance is technically slightly more generic)