haskelleitheralternative-functorsemigroup

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


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.


Solution

  • 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 :: * -> * -> *