Jay Taylor's notes
back to listing indexMonoids for Gophers — Medium
[web search]
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
| 1 | package main |
| 2 | |
| 3 | import ( |
| 4 | "fmt" |
| 5 | "log" |
| 6 | ) |
| 7 | |
| 8 | // Sum monoid |
| 9 | var identity int = 0 |
| 10 | var mappend = func(a, b int) int { |
| 11 | return a + b |
| 12 | } |
| 13 | |
| 14 | func main() { |
| 15 | |
| 16 | // n could be replaced with any value of type int |
| 17 | n := 42 |
| 18 | identityVerified := mappend(identity, n) == n && mappend(n, identity) == n |
| 19 | if !identityVerified { |
| 20 | log.Fatal("invalid identity") |
| 21 | } |
| 22 | |
| 23 | // a, b, and c could be any values of our given type |
| 24 | a := 1 |
| 25 | b := 9 |
| 26 | c := 40 |
| 27 | associativityVerified := mappend(mappend(a, b), c) == mappend(a, mappend(b, c)) |
| 28 | if !associativityVerified { |
| 29 | log.Fatal("not associative") |
| 30 | } |
| 31 | |
| 32 | fmt.Println("You've got a monoid") |
| 33 | |
| 34 | numbers := []int{1, 2, 3, 4, 5, 6, 7, 8, 9} |
| 35 | sum := identity |
| 36 | for _, n := range numbers { |
| 37 | sum = mappend(sum, n) |
| 38 | } |
| 39 | fmt.Printf("The sum of %v is %d\n", numbers, sum) |
| 40 | } |
Product
| 1 | package main |
| 2 | |
| 3 | import ( |
| 4 | "fmt" |
| 5 | "log" |
| 6 | ) |
| 7 | |
| 8 | // Product monoid |
| 9 | var identity int = 1 |
| 10 | var mappend = func(a, b int) int { |
| 11 | return a * b |
| 12 | } |
| 13 | |
| 14 | func main() { |
| 15 | |
| 16 | // n could be replaced with any value of type int.... |
| 17 | n := 42 |
| 18 | identityVerified := mappend(identity, n) == n && mappend(n, identity) == n |
| 19 | if !identityVerified { |
| 20 | log.Fatal("invalid identity") |
| 21 | } |
| 22 | |
| 23 | // a, b, and c could be any values of our given type |
| 24 | a := 1 |
| 25 | b := 9 |
| 26 | c := 40 |
| 27 | associativityVerified := mappend(mappend(a, b), c) == mappend(a, mappend(b, c)) |
| 28 | if !associativityVerified { |
| 29 | log.Fatal("not associative") |
| 30 | } |
| 31 | |
| 32 | fmt.Println("You've got a monoid") |
| 33 | |
| 34 | numbers := []int{1, 2, 3, 4, 5, 6, 7, 8, 9} |
| 35 | product := identity |
| 36 | for _, n := range numbers { |
| 37 | product = mappend(product, n) |
| 38 | } |
| 39 | fmt.Printf("The product of %v is %d\n", numbers, product) |
| 40 | } |
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
| 1 | package main |
| 2 | |
| 3 | import ( |
| 4 | "fmt" |
| 5 | "log" |
| 6 | ) |
| 7 | |
| 8 | // String Concatenation Monoid |
| 9 | var identity string = "" |
| 10 | var mappend = func(a, b string) string { |
| 11 | return a + b |
| 12 | } |
| 13 | |
| 14 | func main() { |
| 15 | |
| 16 | // s could be replaced with any value of type string |
| 17 | s := "foo" |
| 18 | identityVerified := mappend(identity, s) == s && mappend(s, identity) == s |
| 19 | if !identityVerified { |
| 20 | log.Fatal("invalid identity") |
| 21 | } |
| 22 | |
| 23 | // a, b, and c could be any values of our given type |
| 24 | a := "foo" |
| 25 | b := "bar" |
| 26 | c := "baz" |
| 27 | associativityVerified := mappend(mappend(a, b), c) == mappend(a, mappend(b, c)) |
| 28 | if !associativityVerified { |
| 29 | log.Fatal("not associative") |
| 30 | } |
| 31 | |
| 32 | fmt.Println("You've got a monoid") |
| 33 | |
| 34 | strings := []string{"Hello", " Gophers!", |
| 35 | " Can", " I", " sell", " you", |
| 36 | " some", " monoids?"} |
| 37 | concatenated := identity |
| 38 | for _, s := range strings { |
| 39 | concatenated = mappend(concatenated, s) |
| 40 | } |
| 41 | fmt.Println(concatenated) |
| 42 | } |
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
| 1 | package main |
| 2 | |
| 3 | import ( |
| 4 | "fmt" |
| 5 | "log" |
| 6 | ) |
| 7 | |
| 8 | // A monoid that combines sum and count to calculate an average |
| 9 | type average struct { |
| 10 | sum int |
| 11 | count int |
| 12 | } |
| 13 | |
| 14 | var identity = average{} |
| 15 | |
| 16 | func mappend(a, b average) average { |
| 17 | return average{ |
| 18 | sum: a.sum + b.sum, |
| 19 | count: a.count + b.count, |
| 20 | } |
| 21 | } |
| 22 | |
| 23 | func toAverage(i int) average { |
| 24 | return average{sum: i, count: 1} |
| 25 | } |
| 26 | |
| 27 | func (a average) Float64() float64 { |
| 28 | return float64(a.sum) / float64(a.count) |
| 29 | } |
| 30 | |
| 31 | func main() { |
| 32 | |
| 33 | // n could be replaced with any value of type average |
| 34 | n := toAverage(42) |
| 35 | identityVerified := mappend(identity, n) == n && mappend(n, identity) == n |
| 36 | if !identityVerified { |
| 37 | log.Fatal("invalid identity") |
| 38 | } |
| 39 | |
| 40 | // a, b, and c could be any values of our given type |
| 41 | a := toAverage(1) |
| 42 | b := toAverage(9) |
| 43 | c := toAverage(40) |
| 44 | associativityVerified := mappend(mappend(a, b), c) == mappend(a, mappend(b, c)) |
| 45 | if !associativityVerified { |
| 46 | log.Fatal("not associative") |
| 47 | } |
| 48 | |
| 49 | fmt.Println("You've got a monoid") |
| 50 | |
| 51 | numbers := []int{1, 2, 3, 4, 5, 6, 7, 8, 9} |
| 52 | result := identity |
| 53 | for _, n := range numbers { |
| 54 | result = mappend(result, toAverage(n)) |
| 55 | } |
| 56 | fmt.Printf("The average of %v is %f\n", numbers, result.Float64()) |
| 57 | } |
Two dimensional translation
| 1 | package main |
| 2 | |
| 3 | import ( |
| 4 | "fmt" |
| 5 | "log" |
| 6 | ) |
| 7 | |
| 8 | type point struct { |
| 9 | x int |
| 10 | y int |
| 11 | } |
| 12 | |
| 13 | // we can think of a 2D translation as moving the origin to a new point |
| 14 | // so a translation is defined by a point |
| 15 | type translation point |
| 16 | |
| 17 | var identity = translation{} |
| 18 | |
| 19 | func mappend(a, b translation) translation { |
| 20 | return translation{x: a.x + b.x, y: a.y + b.y} |
| 21 | } |
| 22 | |
| 23 | func (t translation) apply(p point) point { |
| 24 | return point{x: t.x + p.x, y: t.y + p.y} |
| 25 | } |
| 26 | |
| 27 | func main() { |
| 28 | |
| 29 | // n could be replaced with any value of our type |
| 30 | n := translation{x: 42, y: 42} |
| 31 | identityVerified := mappend(identity, n) == n && mappend(n, identity) == n |
| 32 | if !identityVerified { |
| 33 | log.Fatal("invalid identity") |
| 34 | } |
| 35 | |
| 36 | // a, b, and c could be any values of our given type |
| 37 | a := translation{x: 1, y: 15} |
| 38 | b := translation{x: 9, y: -20} |
| 39 | c := translation{x: 40, y: 2} |
| 40 | associativityVerified := mappend(mappend(a, b), c) == mappend(a, mappend(b, c)) |
| 41 | if !associativityVerified { |
| 42 | log.Fatal("not associative") |
| 43 | } |
| 44 | |
| 45 | fmt.Println("You've got a monoid") |
| 46 | |
| 47 | t := mappend(a, b) |
| 48 | t = mappend(t, c) |
| 49 | p := t.apply(point{x: 10, y: 10}) |
| 50 | |
| 51 | message := "After appending our translations and applying them,\n" + |
| 52 | "our point moved from (10, 10) to (%d, %d)\n" |
| 53 | fmt.Printf(message, p.x, p.y) |
| 54 | } |
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.
Responses
Make the Medium you like.
Tailor your account to follow the people and topics you care about most.
Sam Ehlers