Functional Typeclasses 2: `Monoid`

This is the second of a series of articles that deep dives a few very powerful type classes that every functional programmer should know. For example, Monoid, Functor, Applicative, Alternative and Monad are all prevalent in production code. We explain them with examples in Haskell. This series assumes the audience is familiar with some functional programming concepts we went through in the previous series.

In the previous post, we went through one of the most universal typeclasses: Semigroup. In this post, we go through a subclass of Semigroup: Monoid. Monoid is also very prevalent and we will look at some notable monoids.

Monoid

Recall that a typeclass definition consists of:

• operations (aka functions or methods) that apply to the typeclass instances.
• laws that these operations need to satisfy.

The typeclasses in functional programming are based on abstract algebra. In abstract algebra, a Monoid is a set equipped with an associative binary operation and an identity element.

Methods of Monoid

In Haskell, only a type that has a Semigroup instance can have a Monoid instance:

class Semigroup a => Monoid a where

A type has a Monoid instance if it has the following methods:

• (inherited from Semigroup) an associative binary function (<>); sometimes called its obsolete/deprecated name mappend
• an identity element (mempty)

<> is the same as the Semigroup method. But Monoid has an additional method (mempty). Therefore, Monoid is a subset of Semigroup, or, to say it the other way around, Semigroup is a superset of Monoid. This means that every Monoid is a Semigroup, but not every Semigroup is a Monoid.

Laws

The methods has to satisfy the following laws:

For the binary function: as we know from the Semigroup law, it has to be associative. I.e.:

x <> (y <> z) = (x <> y) <> z

For the identity element: anything <> to the identity element has to return itself.

Right identity: anything <> to mempty (with mempty on the right) is itself

x <> mempty = x

Left identity: same but with mempty to the left of <>

mempty <> x = x

The Haskell Monoid class also provides a default concatenation function. It has the following definition:

mconcat = foldr (<>) mempty

With <> and mempty defined, mconcat is an extra method based on them. So there is no new method required technically. This is an extra function provided by the Monoid library in Haskell that you can use by default.

Looking at the signature and definition of foldr:

foldr :: (a -> b -> b) -> b -> [a] -> b

mconcat is foldr applied to the binary operator, with the starting value of the identity element. So its signature is:

mconcat :: [a] -> b

mconcat takes a list and <> the list from right to left. We will see some examples of this below.

Notable Monoid instances

In the previous post, we reviewed a few common Semigroup instances. Some of them are also Monoid instances, but some of them aren't.

Let's look at every typeclass we went through previous time and try it in GHCi.

List

From the previous post we know that the <> function for List is ++. Thus, <> is the same as ++ for List.

For mempty, because the empty list [] has the property of the identity element for list, it's the same as mempty for list. Trying it out in GHCi:

Prelude> []<>[1,2,3]
[1,2,3]
Prelude> [1,2,3]<>mempty
[1,2,3]
Prelude> (mempty :: [a]) -- if we specify that `mempty` is of type list, it returns an empty list
[]

For mconcat, let's look at the type signature of foldr again:

foldr :: (a -> b -> b) -> b -> [a] -> b

Our <> function takes in lists, and return a list, so a and b above are of type List here. And we need to give mconcat a list of lists. mconcat will <> the list of lists from right to left, returning a List. This is the same as the function concat in List. In fact, this is a common use of mconcat.

Prelude> mconcat [[1,2,3],[],[4,5,6],[],[7],[8,9],[],[0]]
[1,2,3,4,5,6,7,8,9,0]

OK, this all makes sense and list is definitely a Monoid.

Non-empty list

Recall that the NonEmpty data family is a list that has at least one element in it. So mempty is not defined in NonEmpty! The NonEmpty data family is not an instance of Monoid! GHCi confirms it:

Prelude> import Data.List.NonEmpty
-- GHCi complains about not having a `Monoid` instance for `NonEmpty Int`
Prelude Data.List.NonEmpty> (mempty :: NonEmpty Int)

<interactive>:2:2: error:
    • No instance for (Monoid (NonEmpty Int))
        arising from a use of ‘mempty’
    • In the expression: (mempty :: NonEmpty Int)
      In an equation for ‘it’: it = (mempty :: NonEmpty Int)

Maybe

From the previous post we know how the <> function works for Maybe a. Recall that the type variable a has to have a Semigroup instance for the <> function to work:

Semigroup a => Semigroup (Maybe a) -- for `<>` we only need Semigroup

In fact, Maybe is listed as an instance of Monoid if the type variable has a Semigroup instance:

Semigroup a => Monoid (Maybe a)

Either Integer String is a Semigroup instance, so Maybe (Either Integer String) has a Monoid instance. Let's try it out in GHCi:

Prelude> import Data.Maybe
Prelude Data.Maybe> Just (Right 1) <> Just (Left "string")
Just (Right 1)
-- `Nothing` satisfies the laws for the identity element.
Prelude Data.Maybe> Just (Left "a left") <> Nothing
Just (Left "a left")
Prelude Data.Maybe> Nothing <> Just (Right 2)
Just (Right 2)
-- `mempty` and `Nothing` are the same for the `Maybe` typeclass.
Prelude Data.Maybe> Just (Left "a left") <> mempty
Just (Left "a left")
Prelude Data.Maybe> mempty <> Just (Right 2)
Just (Right 2)

For mconcat, recall that it takes in a list of something, and returns a something. Here we have Maybe (Either Integer String) as the something. Let's give it a list of that, and we should get just a Maybe (Either Integer String) back:

Prelude Data.Maybe> mconcat [Just (Right 1), mempty, Just (Left "a left"), mempty]
Just (Right 1)

Recall from the previous post that association of Maybe a works by applying <> to a's while ignoring Nothing (because Nothing is the identity element!). That's why we need a to have a Semigroup instance. So what's happening is:

mconcat [Just (Right 1), mempty, Just (Left "a left"), mempty]
-- recall that `mconcat` is `foldr` with some inputs, so it works from right to left.
=> Just (Right 1) <> (mempty <> (Just (Left "a left") <> mempty))
=> Just (Right 1) <> (mempty <> Just (Left "a left"))
=> Just (Right 1) <> Just (Left "a left")
=> Just (Right 1 <> Left "a left")
-- `<>` for `Either` returns the first `Right` and if there is no `Right`, returns the last `Left`. 
=> Just (Right 1)

It's interesting to note that because Maybe essentially lets us say it's just a or Nothing(mempty), it is the simplest way to give anything with a Semigroup instance a Monoid instance.

Either

Looking at the documentation, you won't be able to find a Monoid instance for Either! This is because there is no identity element for Either. Recall that Either only has two constructors:

data Either a b =
  Left a
  | Right b

This means the empty element has to be either Left a or Right b! We cannot construct it any other way!

We know that <> for Either returns the first Right, so Right definitely cannot be the identity element since it violates the left identity law (mempty <> x = x).

Also, we know that if there is no Right, <> returns the last Left. Therefore, Left cannot be the identity element either, because it violates the right identity law (x <> mempty = x).

Why do I care about Monoid?

The requirements of Monoid seem simple, but it's because it's so simple that the concept of Monoid is very useful!

In an earlier post, I illustrated that any Monoid instances can be unfolded, and wrote a generalized unfold function that works for any Monoid.

You can see another example of the power this simple typeclass brings from this post. Now that you know what monoids are, you should be able to understand it.

I'm sure you will find more examples in your FP journey!

In the next post, we will deep dive another common typeclass: Functor. You don't want to miss this one!