Lecture 13: Monoids

A monoid is triple $(S, op : S \times S \rightarrow S, id \in S)$, where the binary operator $op$ is associative and where $id$ serves as left and right identity operands. We will see three Haskell typeclasses — Monoid Alternative, and MonadPlus — that encapsulate this notion.

Monoid

We have seen how the foldr function provides a general way to "crunch" a list of values down to a single result. A few simple examples:


    > foldr (+) 0 [1,2,3,4,5]
    15
    > foldr (*) 1 [1,2,3,4,5]
    120
    > foldr (:) [] [1,2,3,4,5]
    [1,2,3,4,5]
    > foldr (++) [] [[1,1],[2,2],[3,3],[4,4],[5,5]]
    [1,1,2,2,3,3,4,4,5,5]
    > foldr (&&) True [True,True,True,False]
    False
    > foldr (||) False [True,True,True,False]
    True
    > foldr (||) True [True,True,True,False]
    True

We will now consider Haskell typeclasses that describe values that can result from this crunching process. We will start with the latter. In a subsequent lecture, we will describe types, beyond just lists, that can be crunched down to a single result.

The Monoid typeclass (defined in Data.Monoid) consists of types that have an associative binary operation with identity,


    class Monoid m where
        mempty :: m
        mappend :: m -> m -> m
        
        mconcat :: [m] -> m
        mconcat = foldr mappend mempty

where mempty is the identity, and mappend is the associative binary operator. An instance of Monoid must define at least mempty and mappend. Notice that because this signature refers to the variable m in places where values are required (and, furthermore, because only ground types are inhabited by values), the kind of m is *. That is, only ground types (as opposed to type operators) can be Monoids.

The names mempty and mappend work well for the List instance, which we will see below, but not as well for many other Monoids whose identities and operators have little to with "emptiness" or "appending." Nevertheless, these are the names and we will learn to live with them. Somewhat recently, the operator (<>) was defined as a synonym for mappend, which helps mitigate the naming issue.

The monoid laws can be expressed as, for all values a, b, and c of a monoid m,

a <> (b <> c) == (a <> b) <> c (associativity),
a <> mempty == a (right identity), and
mempty <> a == a (left identity).

Exercise 13.1

Among the seven example calls to foldr above, which binary operators and identities (the first and second arguments to foldr, respectively) do not constitute monoids, according to the definitions and laws just discussed?

List

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


    instance Monoid [a] where
        mempty  = []
        mappend = (++)

Notice how, based on the surrounding context, Haskell infers what the types of mempty and (<>) should be and retrieves the implementations from the List instance appropriately:


    > [1,2] <> mempty <> [3,4,5] <> [6]
    [1,2,3,4,5,6]
    > foldr mappend mempty [[1,2],[],[3,4,5],[6]]
    [1,2,3,4,5,6]
    > mconcat [[1,2],[],[3,4,5],[6]]
    [1,2,3,4,5,6]

Sum and Product

There are two useful ways of defining a monoid on numbers: (+) paired with the identity element 0 and (*) paired with the identity element 1. However, if we were to define an instance of the form


    instance Num a => Monoid (Num a)
        ...

we could represent only one of these two monoids. To get around this obstacle, Data.Monoid defines two wrapper types for numbers, called Sum and Product, which capture the different monoids on numbers:


    newtype Sum a = Sum { getSum :: a } deriving (...)
    
    instance Num a => Monoid (Sum a) where
        mempty                         = Sum 0
        Sum x `mappend` Sum y          = Sum (x + y)

    newtype Product a = Product { getProduct :: a } deriving (...)
    
    instance Num a => Monoid (Product a) where
        mempty                         = Product 1
        Product x `mappend` Product y  = Product (x * y)

We can now choose between the two Monoids by explicitly wrapping and unwrapping numbers (without any additional run-time overhead, due to the use of newtype in the type definitions):


    > getSum . mconcat . map Sum $ [1..6]
    21
    > getProduct . mconcat . map Product $ [1..6]
    720

Any and All

Similarly to numbers, there are two Monoids on booleans, which are defined by way of two wrapper types:


    newtype All = All { getAll :: Bool } deriving (...)
    
    instance Monoid All where
        mempty                 = All True
        All x `mappend` All y  = All (x && y)
    
    newtype Any = Any { getAny :: Bool } deriving (...)

    instance Monoid Any where
        mempty                 = Any False
        Any x `mappend` Any y  = Any (x || y)

The following examples exhibit the same functionality as calling the all id and any id functions from the Prelude:


    > getAll . mconcat . map All $ []
    True
    > getAny . mconcat . map Any $ []
    False
    > getAll . mconcat . map All $ [True,True,True,False]
    False
    > getAny . mconcat . map Any $ [True,True,True,False]
    True

Maybe, First, and Last

There are many other useful Monoids, besides the common ones on lists, numbers, and booleans above. For example, the following derived instance "lifts" all Monoids over a to Monoids over Maybe a:


    instance Monoid a => Monoid (Maybe a) where
        mempty                     =  Nothing
        Nothing `mappend` m        =  m
        m       `mappend` Nothing  =  m
        Just m1 `mappend` Just m2  =  Just (m1 `mappend` m2)

Furthermore, it is often useful to work with alternative versions of Maybe Monoids, namely, where the binary operator returns the first and last non-Nothing values, if any, in a list of Maybe values. The Monoid instance for Monoid is already "taken," so the First and Last wrapper types are defined to provide each of these two choices, and can be used as follows:


    > getFirst . mconcat . map First $ [Just 1, Nothing, Just 3]
    Just 1
    > getLast . mconcat . map Last $ [Just 1, Nothing, Just 3]
    Just 3

Notice that these two instances make sense even when the underlying type is not a Monoid

Exercise 13.2

Without first peeking at the implementations in Data.Monoid, fill in the definitions below.


    newtype First a = First { getFirst :: Maybe a } deriving (Show)
    newtype Last a  = Last  { getLast  :: Maybe a } deriving (Show)
    
    instance Monoid (First a) where
        ...
    
    instance Monoid (Last a) where
        ...

*Exercise 13.3 Note that (UPDATE) without constraints on the underlying types s and t, Either s t, unlike Maybe, is not an element of the Monoid typeclass. Explain the obstruction.

Endo

And one more Monoid for now, endomorphisms under composition:


    newtype Endo a = Endo { appEndo :: a -> a }
    
    instance Monoid (Endo a) where
        mempty                  = Endo id
        Endo f `mappend` Endo g = Endo (f . g)

Alternative

The Monoid typeclass is useful but describes only ground types. What about type operators that also exhibit monoidal structure? For example, recall that we defined a wrapper type for Maybe called First that constituted a Monoid with an mappend operator that returns the first (leftmost) non-Nothing value.


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

We might like to describe this monoidal structure directly for Maybe even though it is not a ground type. The Alternative class describes Applicative functors f that also exhibit monoidal structure.


    class Applicative f => Alternative f where
        empty :: f a
        (<|>) :: f a -> f a -> f a

Notice the correspondence between empty and (<|>) in Applicative to mempty and (<>) in Monoid, respectively. Unsurprisingly, an Alternative type f ought to satisfy all of the same laws as Monoids... in addition to the ones for Applicative... in addition to the ones for Functor!

The Maybe instance for Applicative is quite like the First a instance of Monoid:


    instance Alternative Maybe where
        empty         = Nothing
        Nothing <|> r = r
        l       <|> _ = l

And now we can write the previous examples directly in terms of the Maybe monoid (Alternative):


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

There are many other applicative functors with monoidal structure. For example, Alternative types are quite handy when writing parsers, as we shall see later in the course.

There's a handy library function in Control.Monad that generalizes the guardMaybe function we saw several lectures ago:


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

*Exercise 13.4

The function mconcat :: Monoid a => [a] -> a combines a list of Monoids. For example:


    > getFirst . mconcat . map First $ [Just 1, Just 2]
    Just 1
    > getFirst . mconcat . map First $ [Just 1, Nothing]
    Just 1
    > getFirst . mconcat . map First $ [Nothing, Just 2]
    Just 2

Implement a function


    altconcat :: Alternative f => [f a] -> f a

that combines a list of Alternatives. Once defined, you will be able to use altconcat as follows:


    > altconcat [Just 1, Just 2]
    Just 1
    > altconcat [Just 1, Nothing]
    Just 1
    > altconcat [Nothing, Just 2]
    Just 2

MonadPlus

There are some Monad types that are also Alternatives, a combination captured in the MonadPlus typeclass:


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

which the documentation describes as “Monads that also support choice and failure,” but which we might prefer to think of as a monoidal monad. Indeed, notice that the class constraints require that a MonadPlus be a Monad plus an Alternative (recall that the Alternative type class describes single-argument type constructors that are monoids, as opposed to Monoid which describes ground types that are monoids).

As the documentation states, the minimal completion definition for MonadPlus is nothing! Indeed, the default definitions say it all:


        mzero = empty
        mplus = (<|>)

So, to make our friend Maybe an instance of MonadPlus, the instance declaration is simpler than trivial, it's empty:


    instance MonadPlus Maybe

Notice the lack of the where keyword.

This is the first time we've seen a type class that doesn't require any methods to be implemented. So, what's the point? Well, one explanation is that writing both constraints (Alternative m, Monad m) could get tedious after a while, and so defining the MonadPlus class serves as a useful shorthand. This isn't a bad idea, but it turns out the real explanation is rather more incidental. Remember the history of the standard libary pre-7.10? Because Applicative was not a superclass of Monad, the constraints (Alternative m, Monad m) would not have been sufficient a "monad-plus-monoid." Instead, the constraints needed to be (Applicative m, Alternative m, Monad m), which quickly becomes unwieldy. Instead, MonadPlus was defined with the single class constraint Monad, disconnected from the Applicative/Alternative geneology. With the restructuring of Monad in 7.10, (Alternative m, Monad m) suffices to describe a "monad-plus-monoid" and so the definitions come for free.

Recap

Monoid and Alternative both describe monoids, the former for types of kind * and the latter for those types of kind * -> *. Note that the latter is also defined to be a subclass of Applicative, because the combination of these two classes is often useful. MonadPlus simply combines Monad and Alternative and is a relic of older versions of the language.


    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 :: f a
        return                  mplus :: f a -> f a -> f a

CMSC-16100

Honors Introduction to Programming, I

Autumn Quarter, 2017