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.

Maidstone

This looks related: ghc.haskell.org/trac/ghc/ticket/9588 – Landgrabber

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

Birck

This is a great answer. Thanks for taking the time! – Maidstone

Sorry, one issue remains: Just "a" <> Just "b" == Just "ab" as expected, but Right "a" <> Right "b" == Right "a". Why this difference? – Maidstone

Right, so the instance for Semigroup of Either a b is actually not defined the way you wrote it. It is entirely independent of whether b has an instance of Semigroup or not. It basically just discards a Left value when it is the left term of (<>) and otherwise return the left term. Checkout the actual source code here :-) I am not sure what the rationale behind this definition is but it works out pretty well for you since you seemed to want an Alternative instance. – Birck

@Birck I don't understand what's the problem with Either having kind * -> * -> *. It's not an explanation why Either can't be Alternative. For example, Monad also requires type to have kind * -> * but there's Monad instance for Either — it just implemented as Monad (Either e) — partially applying Either. For example this compiles and works as expected: hastebin.com/duyituzuda.hs Probably not laws are satisfied, didn't check it. But this is valid code and should be explaned, why not an option. – Isa

Well you just added a constraint that e needs to have an identity. It is a perfectly fine solution, and I have mentioned it (using Alternative instead of Monoid to get empty). I don't think you can do it without this constraint. I admit that the sentence describing this is pretty unclear and I should try to reword it better. – Birck

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.

Tampere

The alternative type class seems to frequently cause problems, also because of the underlying laws. Thanks! – Maidstone

Answer 3

Although Either doesn't have an Alternative instance, it does have a Bialternative instance.

{-# LANGUAGE QuantifiedConstraints #-}

class (Bifunctor p, forall a. Applicative (p a)) => Bialternative p where
  {-# MINIMAL left, ((<<|>>) | liftL2) #-}
  left :: a -> p a b

  (<<|>>) :: p (a -> b) c -> p a c -> p b c
  (<<|>>) = liftL2 id

  liftL2 :: (a -> b -> c) -> p a d -> p b d -> p c d
  liftL2 f a b = f `first` a <<|>> b

  (|>>) :: p a c -> p b c -> p b c
  a |>> b = liftL2 (const id) a b

  (<<|) :: p a c -> p b c -> p a c
  a <<| b = liftL2 const a b

Here's the Bialternative instance of Either. You can use |>> instead of <|>.

instance Bialternative Either where
  left :: a -> Either a b
  left = Left

  (<<|>>) :: Either (a -> b) c -> Either a c -> Either b c
  Left f <<|>> Left a = Left (f a)
  Right c <<|>> _ = Right c
  _ <<|>> Right c = Right c

Instances of Bialternative should satisfy the following laws.

Identity

left id <<|>> v = v

Composition

left (.) <<|>> u <<|>> v <<|>> w = u <<|>> (v <<|>> w)

Homomorphism

left f <<|>> left x = left (f x)

Interchange

u <<|>> left y = left ($ y) <<|>> u

Left Catch

pure x <<|>> v = pure x

Right Catch

left x <*> v = left x

Worse