back to listing index

### Monoids for Gophers — Medium

[web search]
Original source (medium.com)
Clipped on: 2015-12-11

Sam Ehlers·

### 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.

#### 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 }
view raw sum_monoid.go hosted with ❤ by GitHub

Try it on Go Playground!

#### 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 }
view raw product_monoid.go hosted with ❤ by GitHub

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 }
view raw average_monoid.go hosted with ❤ by GitHub

#### 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 }

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.

Thanks to Ford Hurley and Trey Stout.

• ### Responses

There are no responses written or recommended by the author or people you follow.
There is one other response.