Category Theory For Programmers I - Monoids

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

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:

  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.

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:

    (1 + 2) + 3 == 6
  
Or like this:
    1 + (2 + 3) == 6
  
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

    1 + 2 == 3
  
AND
    2 + 1 == 3
  
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:

    1 + 0     == 1     # get 1 back unchanged
    45 + 0    == 45    # get 45 back unchanged
    0 + 45854 == 45854 # you get the picture
  

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.

[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])
  
Or like this:
  [1,2].concat([3,4].concat([5,6]))
  
we'll get the same answer. Concatenating arrays is Associative .

Note here however that order DOES matter.

[1,2].concat([3,4]) != [3,4].concat([1,2])
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.

[].concat([1,2]) == [1,2]
  
This means whenever we concatenate an empty array we are returned the array we concatenate it with unchanged.
[1].concat([])     == [1]     # get [1] back unchanged
[45].concat([])    == [45]    # get [45] back unchanged
[].concat([45854]) == [45854] # you get the picture
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:

  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.

Bringing it all together

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
end

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.