Proposal: Add Data.Semigroup to base, as a superclass of Monoid

[John Wiegley]

1. I propose that we add the following package to base:

     http://hackage.haskell.org/packages/archive/semigroups/0.9.2/doc/html/Data-Semigroup.html

   This is somewhat in the spirit of the AMP proposal: further improving the
   correctness of our algebraic abstractions.

2. That we make Semigroup a superclass of Monoid, so that (minimally):

     class Semigroup a where
         (<>) :: a -> a -> a

     class Semigroup a => Monoid a where
         mempty :: a
         mconcat :: [a] -> a
         mconcat = foldr (<>) mempty

     mappend :: Semigroup a => a -> a -> a
     mappend = (<>)

3. (Optional, recommended) There are other useful functions that can be added
   to Semigroup, such as sconcat and times1p, but I will let Edward speak to
   whether those should be proposed at this time.

4. (Optional, recommended) That we fix the Monoid instance for Maybe to be:

    instance Semigroup a => Semigroup (Maybe a) where
         Just x <> Just y = Just (x <> y)
         _ <> _ = Nothing

    instance Semigroup a => Monoid (Maybe a) where
         mempty = Nothing


For some clarification on what semigroups are and why we'd want to change
Monoid, I excerpt here a selection from Brent Yorgey's "Monoids and
Variations" paper:

                                  Semigroups

  A semigroup is like a monoid without the requirement of an identity element:
  it consists simply of a set with an associative binary operation....
  
  Of course, any monoid is automatically a semigroup (by forgetting about its
  identity element).  In the other direction, to turn a semigroup into a
  monoid, simply add a new distinguished element to serve as the identity, and
  extend the definition of the binary operation appropriately.  This creates
  an identity element by definition, and it is not hard to see that it
  preserves associativity....
  
  Adding a new distinguished element to a type is typically accomplished by
  wrapping it in Maybe.  One might therefore expect to turn an instance of
  Semigroup into an instance of Monoid by wrapping it in Maybe.  Sadly,
  Data.Monoid does not define semigroups, and has a Monoid instance for Maybe
  which requires a Monoid constraint on its argument type...

  This is somewhat odd: in essence, it ignores the identity element of [the
  type] and replaces it with a different one.

-- 
John Wiegley
FP Complete                         Haskell tools, training and consulting
http://fpcomplete.com               johnw on #haskell/irc.freenode.net