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

[Claus Reinke]

>>>> -1, because the default definition of fail is error, which would
>>>> render the Monad instance useless (unless I'm missing something?).
> However, there is no particular reason to associate 'Left' with failure.
> Not having fail be 'Left' is a signifigant feature, not a limitation of
> an Either instance.
.. 
> this means 'Left' indicates success and 'Right' indicates failure in
> some sense. Defining 'fail' to be Left anything is clearly not correct. 

While I do not find the particular example convincing, I agree that
there is a tension about wanting to use both injections of the sum
type vs leaving one for other uses. It is not a question of constructor
names, it is partly to do with Haskell constructor classes forcing us 
to use the last type parameter as the return parameter and partly
with Either having just enough injections to accomodate one extra
piece of information.

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.
 
> '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
(btw, while it doesn't really matter whether we drive on the Right
or on the Left, it does matter that we all agree on one convention:-).

The problems start when all of these classes are linked to a single
Monad instance, and the 'fail' that has been put in it. So far, I had
thought that there was a way to have all common uses of Either
compatible with a single 'fail' (representing both non-local returns 
and empty sums), so I've been arguing to keep a sufficiently 
general Monad instance for Either. If you are certain that is not 
possible, none of the mutually incompatible Monad instances 
should go in base (mtl should simply use its own Either variant)!

> The fact we can't come up with a sensible 'fail' for it is not an
> indication of a problem with fail, or with either, but with simply
> assuming incorrectly that a non-local return must mean failure, we
> should have accepted what the type system was telling us and realized
> that we shouldnt be giving it a fail :).
> 
> I do think we should make a dedicated failure monad though. It is also a
> useful thing.

As long as we have MonadPlus and MonadError instances for
Either, I assume that we've already decided to use Either for
both sums and failure. I'm not saying that could not be changed,
but if someone wants to use Either in ways that are not compatible
with these existing uses, why should everyone else have to adapt?

Claus