Lecture 13: Monoids

The midterm exam will be Monday, November 4th, in class.

A semigroup is a pair $(S, op : S \times S \rightarrow S)$, where the binary operator $op$ is associative.

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.

Semigroup and 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 Semigroup typeclass (defined in Data.Semigroup) consists of types that have an associative binary operation,

class Semigroup s where (<>) :: s -> s -> s sconcat :: [s] -> s sconcat [] = undefined sconcat [x] = x sconcat (x:xs) = x <> sconcat xs

where(<>) is the associative binary operator.

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

class Semigroup m => Monoid m where mempty :: m mappend :: m -> m -> m mappend = (<>) 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 mempty; mappend defaults to (<>). The reason that mappend appears at all Monoid is historical; in pre-8.4 versions of Haskell, Semigroup was not a superclass of Monoid. When the change was made, the mappend was kept around for backward compatibility with existing code. (Just in case you come across some older code examples, back then, (<>) = mappend was defined as an infix operator in Data.Monoid.)

Notice that because the member signatures refer 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,

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 Semigroup [a] where (<>) = (++) 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 => Semigroup (Num a) ... 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 => Semigroup (Sum a) where Sum x <> Sum y = Sum (x + y) instance Num a => Monoid (Sum a) where mempty = Sum 0 newtype Product a = Product { getProduct :: a } deriving (...) instance Num a => Semigroup (Product a) where Product x <> Product y = Product (x * y) instance Num a => Monoid (Product a) where mempty = Product 1

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 Semigroup All where All x <> All y = All (x && y) instance Monoid All where mempty = All True newtype Any = Any { getAny :: Bool } deriving (...) instance Semigroup Any where Any x <> Any y = Any (x || y) instance Monoid Any where mempty = Any False

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 Semigroup a => Semigroup (Maybe a) where Nothing <> m = m m <> Nothing = m Just m1 <> Just m2 = Just (m1 <> m2) instance Monoid a => Monoid (Maybe a) where mempty = Nothing

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 Semigroup (First a) where ... instance Monoid (First a) where ... instance Semigroup (Last 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 a, 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 Semigroup (Endo a) where Endo f <> Endo g = Endo (f . g) instance Monoid (Endo a) where mempty = Endo id

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.

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