Monad transformers for exp-polynomial monads I
A functor M is monadic if there exist two natural transformations: t ~> M t ("point") and M(M t) ~> M t ("join"). These natural transformations should commute, and the "join" transformation should additionally satisfy associativity: the result of M (M (M t)) ~> M t should not depend on the order of two "join" transformations that need to be applied.

A functor P is exponential-polynomial (exp-polynomial) if it is defined inductively as either a constant functor, or the identity functor, or a product or a sum of exp-polynomial functors, or a function type S t -> P t where S is an exp-polynomial contrafunctor and P is an exp-polynomial functor.

A monad transformer for a monad M is a functorial functor L ~> T_ML that transforms any monad L into a new monad T_ML, such that M = T_M Id.

For simple exp-polynomial monadic functors such as M t = 1 + t ("Maybe") or M t = c -> t ("Reader"), one can define monad transformers that help combine these monadic functors with other monads. However, the Haskell wikibook says that "In general, there is no magic formula to create a transformer version of a monad; the form of each transformer depends on what makes sense in the context of its non-transformer type." Is this really true? When can we construct a monad transformer, and when is it impossible?

For T_ML to be a monad, we need two natural transformations: Id~> T_ML and T_M(T_ML) ~> T_ML. We will now show that these natural transformations exist when M is an exp-polynomial monad and T_ML is defined as simply the composition of M and L: either as T_ML t = M(L t) or as T_ML t = L(M t). (Clearly, this satisfies the requirement M = T_M Id.)

We will first consider L(M t) and when that doesn't work, M(L t).


For the first transformation, we need Id ~> T_ML, that is, a natural transformation t ~> L(M t). Since both L and M are monads, we already have Id ~> L and Id ~> M. Composing them and lifting where necessary, we get Id ~> M ~> L°M as required. In the same way we obtain Id ~> M°L.

For the second transformation, we need L°M°L°M ~> L°M. If M is a polynomial monad (or even a recursive polynomial monad), it is also traversable. Since any  monad L is also applicative, we can permute the order of functors as M°L ~> L°M. Thus we can transform L°M°L°M ~> L°L°M°M ~> L°M as required.

So far we have shown that all (recursive) polynomial monads have a monad transformer defined as T_ML t = L°M.

It remains to consider the case where M is a non-polynomial monad. In this case, we define the transformer as T_ML = M°L and hope that this will yield a working monad.

For this to work, we need to find a natural transformation M°L°M°L ~> M°L. If we could only permute the order of functors via a natural transformation L°M ~> M°L, we would transform M°L°M°L ~> M°M°L°L ~> M°L as required.

So, it remains to determine under what conditions the exp-poly monad M is such that for any monad L we have a natural transformation L°M ~> M°L.

Note that this transformation is not the same as the condition for M to be traversable (that condition is an opposite transformation). Many monads L are not traversable, so we cannot use traversability to obtain L°M ~> M°L.

It is impossible to show that this transformation exists if we have no information about the two monads M and L. However, presently we know that M is an exp-poly monad. Let us therefore build up M inductively according to the definition of an exp-poly monad.

It is clear that not all exp-poly functors are monads. For example, F t = a->t + b->t is not monadic (not even an applicative functor!). To restrict M to be not only an exp-poly functor but additionally a monad, we need to see how an exp-poly monad can be constructed inductively from simpler functors. (To be continued.)