This post will attempt to show what a monoid is from the algebraic perspective and apply it through PureScript.

How to read

- if you know the algebraic definition of a monoid, feel free to skip to Monoid in PureScript
- if you know the basic PureScript definition but want to see how Applicative is a monoid and Alternative is a Semiring, skip to Applicative Monoid

Before I can introduce a monoid, I need to give a brief (and extremely informal) definition of sets, operations, associativity, identity, etc.

We are used to grouping things together. We sometimes call such a group a *set*
of things. For example, the numbers 1 through 10 form the set
$ A = \{ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 \} $.

Similarly, we have the set of boolean values $ B = \{ true, false \} $, the set of musical notes $ Notes = \{ A, A\#, B, C, C\#, D, D\#, E, F, F\#, G, G\# \} $, the set of friends of a person, etc.

It’s worth mentioning that there’s also infinite sets, for example $ \Bbb{N} $ for all natural numbers (0 through infinity), $ \Bbb{Z} $ for all integral numbers (minus infinity through infinity), $ \Bbb{R} $ for all real numbers, etc.

We can define operations on these sets. For example, an operation that adds 1 to an element of the natural numbers set $\Bbb{N}$ would look like

This means that **addOne** *takes* a natural number and *returns* a natural
number. We *call* it by just putting a number next to the operation, such as

Operations do not need to be arithmetic. For example, we can define an operation that gives us the next musical note

and use it

These operations are *unary* operations. *Binary* operations take *two* inputs.
For example, addition of two numbers is

This means that $(+)$ takes two numbers and returns a number

Associativity of a binary operator simply means that, if you have any three elements (e.g., a, b, c) from a set and a binary operation (e.g., $(+)$) on the set, then the order in which you apply the operation does not matter

A semigroup has two components: a set and an associative binary operation.

As an example, consider all notes and possible combination of chords (i.e., two or more notes, played at the same time) and an operation $(+)$ that is the set union between the two (i.e., all notes are used, duplicates are removed)

The order does not matter because we play all the notes at the same time.

The identity element for a binary operation $(+)$ is an element $e$ that is neutral for the operation, i.e., for any element $a$ from the set, the following hold:

This is another way of saying that there exists an element in the set such that, combining that element with any other element, we get that other element back.

For example, 0 is the neutral element for addition of numbers. Whatever number you add to 0, you get that number back. Same goes for multiplication of numbers and the number 1.

A *monoid* is a semigroup with identity.

A monoid $\mathcal{M}$ has a set M, an associative binary operation $(+)$, and an identity element $e$, and for all elements $a$, $b$, and $c$ in M

A *semiring* combines two monoids, along with a couple of new laws.

A semiring $\mathcal{S}$ has a set S, and *two* associative binary operations $(+)$
and $(*)$, and each of these operations has its own identity element ($0$ for $(+)$
and $1$ for $(*)$).

There are two new laws that must be obeyed: *distributivity* of $(*)$ over $(+)$
and *annihilation* of $0$ over $(*)$.

Formally

- S, $(+)$ and $0$ form a
*commutative*monoid that

- S, $(*)$ and $1$ form a monoid

- $(*)$ distributes over $(+)$

- $0$ annihilates $(*)$

In PureScript, we can define semigroups and monoids as type classes

```
class Semigroup m where
append ∷ m → m → m
class Semigroup m <= Monoid m where
mempty ∷ m
```

For example, we can implement the addition monoid

```
instance Semigroup Int where
append a b = a + b
instance Monoid Int where
mempty = 0
```

However, implementing the Int monoid for multiplication is impossible because we
can’t define two instances of monoid for the same type. One solution is creating
a *newtype* wrapper for both addition and multiplication and create two monoid
instances.

```
newtype Sum = Sum Int
instance sumSemigroup ∷ Semigroup Sum where
append = (+)
instance sumMonoid ∷ Monoid Sum where
mempty = 0
newtype Product = Product Int
instance prodSemigroup ∷ Semigroup Product where
append = (*)
instance prodMonoid ∷ Monoid Product where
mempty = 1
```

Here’s a few more examples of monoids

- boolean disjunction with false as the identity
- boolean conjuction with true as the identity
- set union with the empty set as identity
- list concatenation with empty list as identity

There are two possible monoid instances for function types.

The set of functions `a → m`

where `m`

is a monoid form a monoid. The
input is *distributed* to all functions, and their results are combined together
using the `m`

monoid instance to a single value. One example is functions that
return lists, where the composition of such functions gives us back a flat list,
instead of a list of lists.

```
instance fnSemigroup1 ∷ Semigroup m <= Semigroup (a → m) where
append f g = \x → append (f x) (g x)
instance fnMonoid1 ∷ Monoid m <= Monoid (a → m) where
mempty = const mempty
```

The set of functions `a → a`

can be *sequenced* one after the other to create a
pipeline of operations on the input.

```
instance fnSemigroup2 ∷ Semigroup (a → a) where
append f g = f <<< g
instance fnMonoid2 ∷ Monoid (a → a) where
mempty = id
```

I will assume familiarity with the `Applicative`

class.

```
class Functor f <= Apply f where
apply ∷ ∀ a b. f (a → b) → f a → f b
class Apply f <= Applicative f where
pure ∷ ∀ a. a → f a
```

How is this a monoid? Let’s try to create a different definition and see if we can implement one in terms of the other

```
class TupleMonoid f where
tappend ∷ ∀ a b. f a → f b → f (Tuple a b)
tempty ∷ f Unit
```

The types for `tappend`

and `tempty`

do not match exactly the types required for
the monoid `append`

and `empty`

, which is why we need a new class. Let’s consider
associativity for `TupleMonoid`

, where $(+)$ is `tappend`

and $(a, b)$ is
`Tuple a b`

The types are not exactly equal, but they hold the exact same data and we can easily define functions that map between the two. So we say the associativity law holds up to isomorphism.

As for identity

Again, since `unit`

is a trivial value, we can easily create isomorphic
functions between the equalities above.

This *up to isomorphism* addendum is also why we can’t use the default
Semigroup and Monoid lasses, but the `TupleMonoid`

will do.

Now, let’s try to define `TupleMonoid`

for any `f`

that has an `Applicative`

. We
will use a newtype just to keep things clean

```
newtype TMApplicative f a = TMApplicative (f a)
-- ... derive newtype Functor, Apply, Applicative
instance tmMon ∷ Applicative f ⇒ TupleMonoid (TMApplicative f) where
tappend fa fb = Tuple <$> fa <*> fb
tempty = TMApplicative <<< pure $ unit
```

`tappend`

basically *lifts* the `Tuple`

constructor so we end up with simple
implementations for the `TupleMonoid`

instance. Try mapping out the types
if it doesn’t make sense.

Now the question is, can we implement it the other way around: given `f`

with
`Functor`

and `TupleMonoid`

instances, can we implement an `Applicative`

instance? Turns out we can, although it’s a bit trickier

```
newtype TMMonoid f a = TMMonoid (f a)
-- ... derive newtype Functor, TupleMonoid
instance appTM ∷ (Functor f, TupleMonoid f)
⇒ Apply (TMMonoid f) where
apply fab fa = tappend fab fa <#> \(Tuple ab a) → ab a
instance applTM ∷ (Functor f, TupleMonoid f)
⇒ Applicative (TMMonoid f) where
pure a = a <$ tempty
```

The trick with `apply`

is that `tappend fab fa ∷ f (a → b, a)`

, so we `map`

(`<#>`

is just `flip map`

) a function that takes a tuple and applies `fst`

to
`snd`

to get a `f b`

.

As for `pure`

, `<$`

is implemented as `map (const x)`

, so we just discard the
unit from `tempty`

but keep the container to get an `f a`

.

Similarly to `Apply`

and `Alternative`

, PureScript has `Alt`

and `Plus`

classes which are the rough equivalents of `Semigroup`

and `Monoid`

```
class Functor f <= Alt f where
alt ∷ ∀ a. f a → f a → f a
class Alt f <= Plus f where
empty ∷ ∀ a. f a
```

Obviously, `alt`

(also known as `<|>`

) is `append`

and `empty`

is identity.
These classes already look like a monoid, so there’s not much work to do here.

The `Alternative`

class is

```
class (Applicative f, Plus f) <= Alternative f
```

Additionally, it guarantees the laws

```
(f <|> g) <*> x = (f <*> x) <|> (g <*> x) -- distributivity
empty <*> f = empty -- annihilation
```

Which are the laws of `Semiring`

. We are only missing commutativity of `<|>`

,
but this is not possible to obtain from (most) `Alt`

instances.

It’s an interesting perspective, and we could draw a few analogies and perhaps
some insight into the reasons of how some `Applicative`

and `Alternative`

instances
work.

Num | Alternative | Array | Maybe |
---|---|---|---|

+ | <|> | concat | first non-Nothing |

0 | empty | [] | Nothing |

* | <*> | cartesian product | Nothing annihilates |

1 | pure | [a] | Just a |

Check out the repository with full source code and quickcheck tests.

Questions? Comments? Tweet them,
or post an issue on this
blog's github repo.