Why is there no alternative instance for Either but a semigroup that behaves similarily to alternative?

Question

I am a Haskell newbie and I wonder why there is no alternative instance for Either but a semigroup, which behaves as I would expect it from alternative:

instance Semigroup (Either a b) where
Left _ <> b = b
a      <> _ = a

This instance discards or corrects "errors" and when both operands are tagged with Right, it takes the first. Isn't this exactly the "choice" that alternative offers?

I would expect the semigroup instance to look roughly like:

instance (Semigroup b) => Semigroup (Either a b) where
Left e  <> _       = Left e
_       <> Left e  = Left e
Right x <> Right y = Right (x <> y)

That means it propagates errors and appends regular results.

I guess I have either a wrong notion of Either or of the involved type classes.

Answer 1

What would you expect an Alternative instance to give you. I think a good way for you to get a feel for how Alternative and Semigroup differ is to look at another type that has instances for both: for example Maybe String:

λ > Just "a" <> Just "b"
Just "ab"
λ > Just "a" <> Nothing
Just "a"
λ > Nothing <> Just "b"
Just "b"
λ > Nothing <> Nothing
Nothing


λ > Just "a" <|> Just "b"
Just "a"
λ > Just "a" <|> Nothing
Just "a"
λ > Nothing <|> Just "b"
Just "b"
λ > Nothing <|> Nothing
Nothing

Alright, so the main difference seems to be for Just "a" and Just "b". This makes sense since you are combining them in the case of the Semigroup rather than taking the left biased option in the case of Alternative.

Now why couldn't you have an Alternative instance for Either. If you look at the functions which are part of the Alternative type class:

λ > :i Alternative
class Applicative f => Alternative (f :: * -> *) where
  empty :: f a
  (<|>) :: f a -> f a -> f a
  some :: f a -> f [a]
  many :: f a -> f [a]
  {-# MINIMAL empty, (<|>) #-}

It looks like it defines a notion of empty; this is the identity of the (<|>) operator. The identity in the case means that the alternative between the identity and something else is always that something else.

Now, how would you construct an identity for Either e a? If you look at the constraint on the Alternative instance, you can see that it requires f to have an Applicative instance. That's fine, Either has an Applicative instance declared for Either e. As you can see the Either is only an applicative functor on the second type variable (a in the case of Either e a). So an identity for Either e would need e to also have an identity. While it is possible to construct a type where e has an instance of Alternative you can't make an instance for Alternative for Either with that e because no such constraint is in the type class definition (something along the lines of: (Alternative e, Applicative (f e)) => Alternative (f e)).

TL;DR: I am sorry if I lost you with my rambling, the short of it is that f in the case of Either is of the wrong kind, Alternative requires f :: * -> * while Either is of kind Either :: * -> * -> *

So Maybe can have an instance of Alternative because it has kind Maybe : * -> * and has a notion of identity (Nothing) that is required by empty. Have a look at all the instances of Alternative and pay attention to the kind of each instance data type.

You can find the kind of a data type in ghci with :k:

λ > :k Maybe
Maybe :: * -> *
λ > :k Either
Either :: * -> * -> *

Answer 2

Per the ticket Dietrich Epp posted above, the issue with Alternative is empty. If you have:

instance Alternative (Either a) where ...

You'd need to be able to pull some value Either a b "out of thin air" that was your identity object. One possible instance might be:

instance (Monoid a)=> Alternative (Either a) where 
  empty = Left mempty
  ...

You also ask why the Semigroup instance is defined the way it is, and frankly I don't understand it either. It would seem that the instance you propose would also permit a (compatible/lawful) Monoid instance as well:

instance Monoid b=> Monoid (Either a b) where
  mempty = Right mempty

And this would be consistent with the Maybe instance (the algebraic relationship between Maybe and Either being obvious).

So the situation isn't good. Part of the issue is Alternative is sort of a second-class class if you will; it is a monoidal higher-kinded thingy, but its relation to Monoid and Semigroup, which obviously and explicitly (in the docs) form a hierarchy, is not defined.

I'm sure there's been a large amount of discussion on the libraries mailing list, and if there are some obvious "correct" solutions it's likely that moving to them could cause (in the worst case silent) breakage.