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:
class Square
def initialize(side)
@side = side
end
def area
@side * @side
end
def perimeter(side)
@side * 4
end
end
class Circle
def initialize(radius)
@radius = radius
end
def area
@radius * @radius * pi
end
def perimeter
2 * pi * radius
end
end
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 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:
class Shape
def area
raise NotImplementedError
end
def perimiter
raise NotImplementedError
end
end
class Square < Shape
def initialize(side)
@side = side
end
def area
@side * @side
end
def perimeter
@side * 4
end
end
class Circle < Shape
def initialize(radius)
@radius = radius
end
def area
@radius * @radius * pi
end
def perimeter
2 * pi * radius
end
end
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:
def fits_in_box?(shape)
shape.area < 10
end
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.
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:
(1 + 2) + 3 == 6
1 + (2 + 3) == 6
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
1 + 2 == 3
2 + 1 == 3
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:
1 + 0 == 1 # get 1 back unchanged
45 + 0 == 45 # get 45 back unchanged
0 + 45854 == 45854 # you get the picture
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.
[1,2].concat([3,4]) == [1,2,3,4]
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:
[1,2].concat([3,4]).concat([5,6])
[1,2].concat([3,4].concat([5,6]))
Note here however that order DOES matter.
[1,2].concat([3,4]) != [3,4].concat([1,2])
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.
[].concat([1,2]) == [1,2]
[1].concat([]) == [1] # get [1] back unchanged
[45].concat([]) == [45] # get [45] back unchanged
[].concat([45854]) == [45854] # you get the picture[]
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:
a = {a: :b}
c = {c: :d}
e = {e: :f}
a.merge(c.merge(e)) == {a: :b, c: :d, e: :f}
a.merge(c).merge(e) == {a: :b, c: :d, e: :f}
HOWEVER, note that order does matter. Imagine this scenario
first = { foo: :bar }
second = { foo: :fighters }
first.merge(second) == {foo: :fighters}
second.merge(first) == {foo: :bar}
When the two hashes being merged share the same key, the order in which you merge the hashes will determine which key is overwritten.
The commonality here is these properties:
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:
require "spec_helper"
require "number"
RSpec.describe Number do
let(:ten) { Number.new(10) }
let(:three) { Number.new(3) }
let(:five) { Number.new(5) }
let(:identity_value) { Number.new(1) }
it "Is Binary" do
expect(ten.multiply(three).class).to eq Number
end
it "Is Associative" do
expect(ten.multiply(five).multiply(three)).to eq ten.multiply(five.multiply(three))
end
it "Has an Identity value" do
expect(ten.multiply(identity_value)).to eq ten
expect(identity_value.multiply(ten)).to eq ten
end
end
class Number
def initialize(value)
@value = value
end
attr_reader :value
def multiply(other)
return other if @value == 1
return self if other.value == 1
Number.new(@value * other.value)
end
def ==(other)
other.value == value
end
endThis 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?
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.