How I learned to stop worrying and love the bomb
Recently, Brandon Williams posted Algebraic Structure and Protocols, a great article describing and building semigroups, monoids and groups using Swift protocols. It’s an interesting article and I encourage you to read it (and his other articles). In fact, I’ll wait while you do…
As with most such articles there are some simple examples, however I find the leap from ok, I see what that is, to oooooh, I see what this thing does! somewhat confounding.
In other words, how do I spot this pattern and use the technique in my own code?
I aired this small grievance, wondering if mconcat([1,2,3,4]) was just a fancy way to replace reduce([1,2,3,4], 0, +)1 in my code? In response, Nick Partridge said yes, but related the following real example from his work:
I am measuring outdoor advertising views. I have many differentCollectors of this metric for various types of signage with a type like:Trip -> ViewCount. e.g. A collector of views for buses seen along the trip or a collector of views for billboards. These are all independent things that I need to collate.
This example was a penny drop moment for me. The Collector type is a monoid!
Given a specific trip, the idea is to calculate the view counts for different types of signage and collate them in some way. It doesn’t really matter what way. Maybe we’re adding them all together for a total, maybe we’re returning a list of counts, or a dictionary of types and counts. It doesn’t matter. We’re taking a list of Collectors and a Trip to process, and returning some collation of the data.
We can process this manually, of course. We can take our list of Collectors, pass the Trip to each, get the results, then collate them however we want.
But if we recognise this as a monoid, we realise that a lot of that code is already written, it’s the same code that processes all our other monoids. A tiny abstraction that is common to a lot of things. We already know how to collate things. We give their type a collation operator and an identity, then mconcat them.
In other words, we can mconcat our Collectors and produce a new composite Collector that does the collating for us. We can pass our Trip to that new Collector and obtain our result directly. For example, instead of something like:
let collectors = [collector1, collector2]
var result: Int
for collector in collectors {
result = result + collector(trip)
}
we can take a small step to this:
let collectors = [collector1, collector2]
collectors.map { collector in collector(trip) }.reduce(0, +)
but once we’ve defined a monoid extension for Collector, we can:
let collate = mconcat([collector1, collector2])
collate(trip)
We have abstracted away the idea of how we’re going to collate our data and instead ask for collated results directly. How to define this monoid is actually covered in Exercise 6 of Brandon’s article.
Semigroups, monoids and groups while perhaps alien, are in fact useful and common. They’re names for patterns we encounter frequently and now recognise. Maybe you’re like me and have just realised you’re working on something monoidal right now.