Alternative instance

[masaeedu]

Hello there. I was a little bit surprised by the behavior of the Alt instance in this library, which goes like this:

-- | For two errors, this instance reports only the last of them.
instance Alt (Validation err) where
  Failure _ <!> x =
    x
  Success a <!> _ =
    Success a

This is lawful in the sense that it is associative, but then the constant semigroup is a lawful semigroup implementation for any type whatsoever. For the same reason the constant semigroup cannot be a monoid, this instance also prevents us from having a lawful Alternative instance.

I originally got my wires crossed and started looking at the Alternative instance in the wrong library:

instance Monoid err => Alternative (Validation err) where
  Failure _ <|> x =
    x
  Success a <|> _ =
    Success a
  empty =
    Failure mempty

Which violates the requirement that x <|> empty = x. It seems the full Alternative is no longer part of this library.

Would it make sense to have the following Alternative instance for Validation instead?

instance Semigroup e => Alt (Validation e)
  where
  Failure e1 <|> Failure e2 = Failure $ e1 <> e2
  Success x  <|> _          = Success x
  _          <|> Success x  = Success x

instance Monoid e => Alternative (Validation e)
  empty = Failure mempty

This does not (necessarily*) discard any failures, and is a lawful implementation of Alternative. To verify this is a lawful monoid, we can observe that:

• Either a :: * -> * is a lawful applicative

• For any applicative (f :: * -> *, liftA2, pure) and any monoid (e :: *, <>, mempty) there is a monoid (f e :: *, liftA2 (<>), pure mempty)

• All of this is still true if we relabel the constructors of Either a e in the following way:

  Right   :: e -> Either a e
  Failure :: e -> Either a e
  
  Left    :: a -> Either a e
  Success :: e -> Either a e

Compare the suggested Alternative instance with:

data Either' a e = Success a | Failure e

instance Applicative (Either' a)
  where
  liftA2 f (Failure e1) (Failure e2) = Failure $ e1 `f` e2
  liftA2 _ (Success x)  _            = Success x
  liftA2 _ _            (Success x)  = Success x

  pure e = Failure e

instance Monoid e => Monoid (Either' a e)
  where
  (<>) = liftA2 (<>)
  mempty = pure mempty

* For folks who are interested in preserving the old behavior where half the errors get thrown away, you can always just plug in the Const semigroup and it will work the way the instance does right now.

[treeowl]

Makes sense to me.