# Category Theory For Programmers I - Monoids

05 Oct 2017This is a series of posts aiming to demystify some of the core concepts of category theory and by extension functional programming. This is part 1.

### Category Theory

Category theory is the study of how maths works. If that sounds mental, that's because it is. Usefully the things discovered in category theory have some practical applications for programmers, and in some ways form the foundations of a lot of functional programming.

Learning about category theory, then, is to learn about functional programming. This is why it's important. In fact some languages like haskell make very little sense until we can grasp these basic concepts. With that, let's take a few of these concepts in turn and see what they are all about

### Abstractions

Before we look at what a monoid is, let's talk about abstractions.

As programmers we work in abstractions. To utilise an abstraction is to find some commonality that can be shared, to isolate it then share it. An example in ruby:

The commonality here is the methods they implement. This commonality hints that both `Circle`

and `Square`

are two variations of the same *type* of thing. If we were to name the type, we would call it a `Shape`

. We can imagine more `Shape`

s, but each one would have to have both an `area`

and a `perimiter`

. That is to say, no matter what else they may or may not have, any shape *must* have an `area`

and a `perimiter`

. We can isolate these properties and make them available to instances of those types by doing something like this:

This means if we tried to make a `Triangle`

we would *have* to implement an `area`

and `permiter`

method for it.

The flip side of this is that if we know something is a shape, we know that it has an `area`

and a `perimiter`

method. If we know those things for certain there are certain assumptions we can make about shapes. We could write this method for example, and *know* that it will work for any shape we pass it *by definition*:

Pretty powerful stuff.

### Monoids

On to monoids. A monoid is a type of abstraction. To see which kind we are going to look at different instances of things that are monoids and identify the commonality between them. Then we can look at what that buys us.

#### Addition of Numbers

What can we say about addition of numbers? The first thing we can note is that it is **Binary**. That is to say it requires *two* numbers to add together, but returns precisely one number.`1 + 2 = 3`

. Three is a bigger number, but it is just one number.

The next thing we can say is that addition of numbers is **Associative**. What this means is if we add three numbers together, it doesn't matter if we do it like this:

Note that associativity IS NOT ORDER. It is better described as grouping. For addition of numbers we can say that order also doesn't matter. What that means is

AND This is known as being**Commutative**

The final thing to note about addition of numbers is that there is an **Identity value**. An identity value is a zero value. A zero value is a value whereby if you add to it any other number, you get that number back unchanged. For addition of numbers the zero value is literally 0:

#### Concatenating Arrays

Now let's look at another example - concatenating arrays.

To Concatenating two arrays, you take the all the elements out of the first array and then all the elements out of the second array and put them all into a new array.

In order to do that you need two arrays, and we can see from above that we are returned one array. It's a bigger array, but it is just one array. So concatenation of arrays is **Binary** .

Now imagine concatenating three arrays. It doesn't matter if we do it like this:

Or like this: we'll get the same answer. Concatenating arrays is**Associative**.

Note here however that order DOES matter.

Concatenating arrays is**NOT**commutative.

Now imagine concatenating an array to an empty array. We would take the empty out of the first array, and the values out of the second array and make a new array containing both those things.

This means whenever we concatenate an empty array we are returned the array we concatenate it with unchanged. Arrays, then, have an**Identity Value**-

`[]`

#### Merging of Hashes

The last example we will look at is the `merge`

operation for hashes

**Binary** - you need two hashes to merge together, and you are returned one hash as a result.

**Identity** - the identity value is an empty hash `{}`

**Associativity** - the grouping of merges doesn't matter:

HOWEVER, note that order *does matter*. Imagine this scenario

When the two hashes being merged share the same key, the order in which you merge the hashes will determine which key is overwritten.

### Bringing it all together

The commonality here is these properties:

**Identity Value****Associativity****Binary**

This commonality hints that the adding of numbers, and the concatenating of arrays and hashes are three variations of the same type of thing. If we were to name that type of thing, we might call it being `Reduceable`

. We can imagine more Monoids, but each one would have to be `Reduceable`

by obeying these three rules. That is to say, no matter what else they may or may not have, any monoid must be associative, binary and have an identity value. We can isolate these properties and ensure they hold for new kinds of monoids by doing something like this:

This means we can be sure our new monoid would obey those laws.

If we are sure what we have are monoids, then we can do things which leverage those laws and *know* that our monoid type things will not break. But what kind of things can we do?

#### What do monoids buy us?

If we know that something is associative, then we know that, as long as order is maintained, we can break up the total workload in any arbritrary way and we would always get the same result. Imagine if we had to compute an expensive addition operation. We could split the overall problem into many subproblems and pass each subproblem off to different threads. We could still guarantee the answer would be the same as if we didn't, because we know the law of associativity holds!

Pretty powerful stuff.