#4159: move Monad and MonadFix instances for Either from mtlto base

[Ross Paterson]

On Thu, Jul 01, 2010 at 10:27:39AM +0200, Claus Reinke wrote:
> Anyway, since I want to use Left for fail messages (at least sometimes)
> and you want to use Left for something else (at least hypothetically),
> it does not seem to be a good idea to fix one Monad instance in base
> that is sure to disappoint one of us, right? Once people start importing
> Control.Monad.Instances in their packages, as they will when mtl and
> co start depending on that, one of us is stuck with an Either Monad
> they cannot use.

It will happen long before that: Control.Monad.Instances is imported
directly by Control.Applicative and Control.Monad.Fix, and hence by
Control.Arrow, Data.Foldable, Data.Traversable, the ST modules and
the modules in containers.  Anyone straying outside of haskell98 will
probably get it.

With Haskell as it is, local instances are unworkable.  We do have to
decide on a single instance (unless no instances at all are possible).

> [John Meacham wrote:]
> >'Either' is a monad with a non-local return, _not_ necessarily an
> >error monad.
> 
> Either is just a sum type. There are classes that want to use it for
> non-local returns (MonadError) and classes that want to use
> it for sums (MonadPlus). And if I believe you, there are uses that
> want to use it for something else, or at least the other way round

No, he also wants to use Left for non-local returns, but argues that
such returns are not always failures.

It seems to me that MonadPlus is not a good fit for Either -- how can
it be a monoid?