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

[Claus Reinke]

>> As I said, even if you just want to drop 'Error', you could define
>> 'fail s = Left (error s)'. That would still be less defined than the
>> current instance, but more defined than the proposed instance.
> That didn't occur to me -- it seems harmless enough, but it wouldn't be
> enough to support pattern binding with the Either monad, would it?

Only partially - sufficient to use it for MonadPlus mzero composition
or for MonadError early exit, but not sufficient to make use of the
error information (essentially, we model 'Either Void b' on 'Maybe b').
The alternative provided in mtl additionally allows us to embed the
error information in whatever type we use for Left (via a custom Error
instance). Quite a bit of thought must have gone into the mtl design
there, which is why it makes me sad that so many are willing to
throw that away without discussion, and without equivalent
alternatives.

The alternative I gave in the example code keeps these possibilities
while also providing a default instance for Error (for people who
do not want to bother defining their own). The use of Overlapping
Instances should be limited to the defining module (unless you
want to define your custom instance for Error for a use of Either
that would not be possible in the original proposal), but might
have other issues - I'd be interested to hear about them.

I realize now that there are uses that wouldn't be served by
this alternative, because they are incompatible with established
use in mtl. Obviously, I am against replacing an instance that
has been incompatible with those new uses with an instance
that would be incompatible with old uses.

I thought this proposal was about reducing conflicts between
mtl alternatives and their clients, by moving the instance up
in the package hierarchy. That would be something I agree
with. I also agree that the source of trouble is in forcing fail
into Monad, but until that is changed, we're stuck with it.

And If the current proposal is about changing the instance
in breaking (and, given Haskell's limitations, non-fixable)
ways, then I am no longer opposed just on details, but on
principle: those who want Either with different uses should
use a different Either-like type.

>> >Do you mean an overlapping instance?  There are problems with that too.
>>
>> Yes to both. But it would avoid the problems with the unconstrained
>> Monad instance for Either a, wouldn't it?
>
> It seems disproportionate: Either is a Prelude type, and it seems 
> reasonable
> to stick to the core language in defining its instances of Prelude 
> classes.
> One can always use a new type for the Error thing.

There is a good reason that Either does not have a Monad instance
in the Prelude. To make an instance that serves most uses, one needs
additional tools (the mtl solution uses few tools, so would fit your
requirements, but has an annoying extra constraint; the
OverlappingInstances solution lets us avoid that constraint, and
there is a precedent for this kind of use in base).

And yes, mtl should have used and should use some other type for
its Error thing. And the current proposal is headed to repeat that
mistake, by fixing Either's Monad to one class of uses. Only that
the proposal's instance has a narrower class of uses(*), and a wider
exposure of the problematic instance. But I have already cast my
one vote, and I've tried to highlight the issues and alternatives.

Claus

(*) Haskellers who don't use fail, explicitly or implicitly, should
    not be bothered by a fail that tries to map error messages to
    their Left type (fail :: Error a => Either a b), but Haskellers who
    do use fail (mostly implicitly) are stuck if fail is error.