back to listing index

Monoids for Gophers — Medium

[web search]
Original source (medium.com)
Tags: generics programming haskell golang go functional-programming monoids
Clipped on: 2015-12-11

Image (Asset 1/5) alt=
Image (Asset 2/5) alt=Sam Ehlers·
Image (Asset 3/5) alt=
Sam EhlersOct 20·4 min read

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

Make the Medium you like.

Tailor your account to follow the people and topics you care about most.

Don’t miss Sam Ehlers’s next story
Image (Asset 5/5) alt=Sam Ehlers