Marty Stumpf

9 Jan 2023

â€¢

6 min read

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 `Monoid`

Recall that a typeclass definition consists of:

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

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**.

`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`

.

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.

`Monoid`

instancesIn 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.

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`

.

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)
```

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.

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`

).

`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!

Did you like this article?

Marty Stumpf

Software engineer. Loves FP Haskell Coq Agda PLT. Always learning. Prior: Economist. Vegan, WOC in solidarity with POC.

See other articles by Marty

hello@works-hub.com

Ground Floor, Verse Building, 18 Brunswick Place, London, N1 6DZ

108 E 16th Street, New York, NY 10003

Join over 111,000 others and get access to exclusive content, job opportunities and more!