# Introduction

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

• 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

## Monoid in Algebra

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

### Sets

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.

### Operations

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

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

### Semigroup

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.

### Identity

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.

### Monoid

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

### Semiring

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 $(*)$

## Monoid in PureScript

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

### Function Monoids

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


### Applicative Monoid

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.

### Alt Monoid

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 Semiring

The Alternative class is

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


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

## Why should I care?

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.