Category Theory For Programmers I - Monoids05 Oct 2017
This 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 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
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
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
Shapes, 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
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.
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: Or like this: we'll get the same answer.
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:
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
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.