Monoids for Gophers

Google’s Go is a great, simple, and practical programming language. It stays lean by not implementing abstractions that are often abused and can bog down other languages. Monoids are a simple but powerful abstraction. I’ve found Go and monoids to be surprisingly compatible.

What is a monoid?

In abstract algebra, a branch of mathematics, a monoid is an algebraic structure with a single associative binary operation and an identity element.

Thanks, Wikipedia. That’s… terse.

Assuming very little familiarity with monoids or abstract algebra a more relevant question is “Why do I care?”.

In a complex program it can be hard to know what parts can be done in parallel. It’s even harder to predict which parallel operations will be worth while. Using monoids as a design pattern we can effectively defer some decisions about what to do in parallel while still deeper understanding how it can be done in parallel. Monoids give us a way to “conquer” for a divide and conquer algorithm. They allow us to make assumptions about our programs that are non trivial and have been proven by people who have elevated scrutiny to an art form. Finally simple monoids can be combined easily to form more complex monoids to handle more complex tasks.

So, if we can satisfy the definition and some simple laws we can know a lot about how to compose the elements of our monoid.

For any monoid we know:

• Two elements can be reduced to one with the “associative binary operation”. We’ll call this operation `mappend` in a nod to Haskell where I learned of this concept.
• If we don’t have an element and we need one we can start with the `identity` element.
• `mappend` is associative so `mappend(mappend(a, b), c) == mappend(a, mappend(b, c))` with any values in a, b, and c.
• `mappend(identity, a) == a` with any value for a.
• We can reduce any number of elements down to one by using `mappend` on each two.
• We can split groups of elements any way we like, reduce the groups with `mappend` then combine the results of each group with `mappend` and get the same result as we would have without grouping. In this way monoids facilitate safe parallelism.
• If we have two monoids we can combine them to produce another monoid.

Getting Concrete

Monoids are a painfully abstract concept, in order to have any hope of gaining an intuition for them we’re going to need to look at some concrete examples.

Let’s start with some monoids we can do with numbers.

Sum

Try it on Go Playground!

Product

Ok, maybe this is vaguely interesting, but over analyzing ways to Sum numbers isn’t a programmer super power.

Let’s see an example with something other than numbers.

String concatenation

Putting it all together

Now we’re starting to see that a lot of concepts can be shoehorned into a monoid, lets try combining some of them.

Average

Two dimensional translation

Try it on Go Playground

They… are… everywhere!

We can go further building up a monoid for slices of two dimensional paths (similar to those found in SVG) and combining that with our two dimensional translation monoid to form something capable of positioning two dimensional paths. Monoids scale incredibly well with complexity. This is how the core of the layout engine is implemented for the Handwriting.io API.

Going without Generics

Go doesn’t have generics. This is probably the most often criticized aspects of the language. We can still think abstractly and act concretely. Yes there will be boilerplate code that you might not have written in another language, but it doesn’t mean that monoids are off limits. The extra concrete boilerplate code could possibly be an asset in introducing this concept to others.

Hedging our bets at design time

Modelling parts of our domain using monoids helps us to keep our concerns separate, because we’re trying to enforce the monoid laws for identity and associativity. In fact, probably the best way to protect our monoid from feature creep is to build a test using `testing/quick` to enforce the laws.

Golang doesn’t protect our monoid from mutation. The best way we can do this is to ensure the value returned from `mappend` doesn’t share anything with the arguments that went in. This comes with a cost. Doing things in this way will allocate more memory and we might need to optimize before all is said and done.

There is some question as to what happens over time as this code is maintained by other programmers who may or may not have drank the Abstract Algebra flavored kool-aid. They might rename the `mappend` functions so something more domain suitable. They might break associativity and invalidate the assumptions we got for free. Even if the next programmer doesn’t bother to google the word “monoid” they saw in your comment, what they will see is a variable and a function that takes two arguments. This all is in normal Go syntax that won’t scare anyone away and doesn’t require any odd third party libraries. You can be confident that you’re not leaving behind some Rube Goldberg device for the next person.

End Results

Monoids are a great way to keep our options open when it comes to parallelism. This was my original goal when using monoids in the layout engine, but nearing the end of the project I found the performance didn’t benefit from parallelism. The extra copying I was doing to protect against mutation didn’t amount to enough to justify optimization. The benefit that I really got from this journey into generalized abstract nonsense was a clean, consistent and extensible domain model.

Check out my work at Handwriting.io and follow me on twitter. Also, we’re currently hiring in New York, details on AngelList.