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

[wren ng thornton]

Edward Kmett wrote:
> A reasonable case can be made for the existence of a monad that does
> something useful with fail. I don't think that that monad should be Either.
> 
> 'Either' takes on the connotation of being the 'sum type' for the category
> of Haskell types. This sum type has a very well formed and simple monad,
> that has a lot of useful theoretical properties, and is useful in a strictly
> larger array of scenarios than the monad with the error constraint, with the
> one notable exception that it doesn't handle the 'fail' property that was
> bolted into Monad in Haskell 98.

Indeed. For type-level programming and category theoretic tricks, it is 
essential to have some canonical type for representing primitive type 
sums, with no additional semantic baggage. Either is the most obvious 
candidate for that role, and is frequently used for it as well. That it 
had been coopted for other purposes not related to being a primitive sum 
is an unfortunate historical problem.


> The obvious name for such a monad would be Error, to go with ErrorT, but the
> Error class conflicts with that name, but perhaps:
> 
> data Fail e a = Error e | OK a
> 
> would be worth adding to Control.Monad.Error, during the same general
> timetable as this change, to provide users who really want the existing mtl
> Either semantics an upgrade path.

+1. It would be nice to distinguish the sums-as-errors type from the 
primitive-sum type.


> In the interest of not killing this proposal with bikeshedding concerns over
> what to call it (Fail, Err, Error, etc), we should probably put that forward
> as a completely separate libraries proposal though.

+1 for dodging bikesheds.

-- 
Live well,
~wren