Is it possible to change the monad type in a monadic sequence?

Question

I know it's possible to change the wrapped type, so that you can have

f :: (a -> m b)
g :: (b -> m c)
f >>= g :: (a -> m c)

but is it possible to change m? If m is a MonadError and is implemented both by an Either ErrorA and Either ErrorB, can i somehow chain them? Obviously I can't chain them directly, because what would be the type of Left? However, I'm in a situation where I end up calling show in either case, but I haven't found a better solution than

case mightFail1 of
  Left e -> show e
  Right v -> either show doStuff mightFail2

which fails to properly use the monadic behavior of stopping at the first error without me having to check explicitly.

Answer 1

The entire notion of "changing the container" is called a "natural transformation". Specifically, we want a function which transforms containers without affecting what's inside. We can ensure this is the case in the type system by using forall.

-- natural transformation
type (m :~> n) = forall a. m a -> n a

Then these can be applied whenever we want. For instance, if you can transform ErrorA -> ErrorB then there's a general operation for you

mapE :: (e -> e') -> (Either e :~> Either e')
mapE f (Left e)  = Left (f e)
mapE _ (Right a) = a

You can even get really fancy with type operators and sum types.

-- a generic sum type
infixr 9 :+:
newtype (a :+: b) = Inl a | Inr b

liftE :: (Either e :~> Either (e' :+: e))
liftE = mapE Inr

Bifunctors achieve roughly the same effect but they are a totally different way of viewing the problem. Instead of generally changing out the container, they affect another covariant parameter (or index) in the container itself. So, Bifunctor actions can always be seen as natural transformations, but NTs are more general.