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 monoids.
Monoid
Recall that a typeclass definition consists of:
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:
Semigroup
) an associative binary function (<>
); sometimes called its obsolete/deprecated name mappend
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!
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
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!