Monoids

(Not updated very recently)

Recall that given a list [x,y,z]…

 x  :   y  :   z  :  []

… foldr f init [x,y,z] crunches the list down to a result…

(x `f` (y `f` (z `f` init)))

… by iteratively “accumulating” the result in the second argument of foldr.

We can abstract:

certain kinds of operations that combine values, and
the traversal process.

Today we’ll talk about the former; the latter will come another day.

A semigroup (S,op:S×S→S) is a set S with an associative binary operator op.

A monoid (S,op:S×S→S,id) is a set S with an associative binary operator op and an element id that serves as left and right identity operands. We will see three Haskell type classes — Monoid, Alternative, and MonadPlus — that encapsulate this notion.

`Semigroup` and `Monoid`

Represented in Haskell (defined in Data.Semigroup and Data.Monoid and both exposed by Prelude):

class Semigroup_ t where
    (<>)           :: t -> t -> t

    sconcat        :: [t] -> t
    sconcat []     =  undefined
    sconcat [x]    =  x
    sconcat (x:xs) =  x <> sconcat xs

class Semigroup_ t => Monoid_ t where
    mempty  :: t

    mappend :: t -> t -> t
    mappend = (<>)

    mconcat :: [t] -> t
    mconcat = foldr mappend mempty

Laws:

a <> (b <> c) = (a <> b) <> c
a <> mempty = a
mempty <> a = a

The mempty member of Monoid is the identity element.

The mappend member of Monoid is a vestige of Haskell pre-8.4: Semigroup was not a superclass of Monoid before then. (Just in case you come across some older code examples, back then, (<>) = mappend was defined as an infix operator in Data.Monoid.)

List

The List instance is straightforward and illustrates why the Monoid methods were so named:

instance Semigroup_ [a] where
    (<>)   = (++)
instance Monoid_ [a] where
    mempty = []
 -- mappend = (++)

Sum and Product wrappers

newtype Sum a     = Sum     { getSum     :: a } deriving (Show)
newtype Product a = Product { getProduct :: a } deriving (Show)

instance Num a => Semigroup_ (Sum a) where
    Sum x <> Sum y = Sum $ x + y
instance Num a => Monoid_ (Sum a) where
    mempty         = Sum 0

instance Num a => Semigroup_ (Product a) where
    Product x <> Product y = Product $ x * y
instance Num a => Monoid_ (Product a) where
    mempty                 = Product 1

Any and All wrappers for Bool

newtype All = All { getAll :: Bool } deriving (Show)
newtype Any = Any { getAny :: Bool } deriving (Show)

instance Semigroup_ All where
    All x <> All y = All $ x && y
instance Monoid_ All where
    mempty         = All True

instance Semigroup_ Any where
    Any x <> Any y = Any $ x || y
instance Monoid_ Any where
    mempty         = Any True

Maybe, First, and Last

instance Semigroup_ a => Semigroup_ (Maybe a) where
    Nothing <> mx    = mx
    mx <> Nothing    = mx
    Just x <> Just y = Just $ x <> y
instance Monoid_ a => Monoid_ (Maybe a) where
    mempty           = Nothing

> mconcat [Just 1, Nothing, Just 3]   -- Int isn't a Monoid

> mconcat [Just (Sum 1), Nothing, Just (Sum 3)] :: Maybe (Sum Int)

`Alternative`

The Monoid class describes types of kind *. But type constructors can also be monoids.

Recall the First monoid on Maybe values.

getFirst $ First (Just 1) <> First (Just 2)

Would be nice to have:

Just 1  "<>" Just 2  ==  Just 1
Nothing "<>" Just 2  ==  Just 2

So, define an analogous monoid class for type constructors (specifically, applicative functors, because this class is going to also leverage that interface).

class Applicative t => Alternative_ t where
    empty :: t a
    (<|>) :: t a -> t a -> t a

instance Alternative_ Maybe where
    empty             = Nothing
    Nothing <|> right = right
    left    <|> _     = left

> Just 1  <|> Just 2
> Just 1  <|> Nothing
> Nothing <|> Just 2

> Just 1  <>  Just 2    -- quiz: why this doesn't work?

Recall our definition of guard in MonadPlus_; we can generalize the Boolean encoding to any Alternative. In Control.Monad:

guard :: Alternative f => Bool -> f ()
guard True  = pure ()
guard False = empty

`MonadPlus` = `Monad` + Monoid (`Alternative`)

class (Alternative m, Monad m) => MonadPlus m where
    mzero :: m a
    mzero = empty

    mplus :: m a -> m a -> m a
    mplus = (<|>)

Both default definitions in terms of Applicative. So, minimal complete definition is nothing.

instance MonadPlus Maybe

Why? To reduce having to write (Alternative m, Monad m)? No, it’s historical; before Monad was a subclass of Applicative, this class “manually” added the monoid interface to Monad.

Recap

                        Semigroup m
                         |  (<>) :: m -> m -> m
                         |
Functor f               Monoid m
 |  fmap                    mempty :: m
 |                          mappend = (<>) :: m -> m -> m
 |
Applicative f --------- Alternative f
 |  (<*>)                |  empty :: f a
 |  pure                 |  (<|>) :: f a -> f a -> f a
 |                       |
Monad f --------------- MonadPlus f
    (>>=)                   mzero = empty :: f a
    return = pure           mplus = (<|>) :: f a -> f a -> f a

Semigroup and Monoid