Jay Taylor's notes

back to listing index

Monoids for Gophers • /r/golang

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

this post was submitted on 21 Oct 2015
19 points (85% upvoted)


unsubscribe18,204 readers

~64 users here now

Show my flair on this subreddit. It looks like:

Please follow the Go Community Code of Conduct while posting here. In short:

  • Treat everyone with respect and kindness.
  • Be thoughtful in how you communicate.
  • Don’t be destructive or inflammatory.
  • If you encounter an issue, please mail conduct@golang.org.



Other Resources

created by uriela community for 6 years

all 11 comments
sorted by:

[–]natefinch 4 points 1 month ago* 

You didn't really explain what the benefit of using this pattern is. You say it can help with parallelization, but didn't actually show an example. I think this would make the article a lot more compelling, because right now you've added complexity without actually doing anything with it.

If you had code creating goroutines and fanning out the work and then consolidating it, then I think it would be more clear why you'd actually do this.

Also, there was no description of why the identity is important. The only time you use the identity is to prove the identity works, which is not really useful in explaining what it's for :)

[–]zoomzoom83 2 points 1 month ago 

Because a monoid is associative, you can safely break the problem down into smaller pieces, map an operation on the across multiple threads, and then reduce back to a final result without worrying about order of execution or race conditions.

Identity is the "zero value" (i.e. '0' for addition, "" for string concatenation, [] for list concatenation etc. By asserting that your type has a sane zero value, you're able to ensure there's a starting point for a reduce operation.

Anything meeting this criteria (can be added associatively and has a zero value) is already a monoid, and you likely use then day to day already (ever concatenated a string?) - so this isn't adding any complexity, it's just formalising laws and giving a name to the it.

[–]jerf 1 point 1 month ago* 

I think you ought to be careful to draw a distinction between what monoids are and can do, and what monoids can do for Go. Due to the lack of generic types and pretty much any other effective mechanism for doing anything like that efficiently (i.e., reflection can work but will eat your performance for breakfast on most monoid combination operations which tend to be very simple), it's not that useful of a programming abstraction for Go.

While monoids are also in theory good for parallelization, it's also worth pointing out that as they lack any mechanism for generically splitting them into even pieces (because all they have is the identity and combination operator), you generally need something more to actually take advantage of the parallelization possibilities. For instance, for an array, it would be nice to be able to chunk it up, and for a linked list, you basically lose (there is no practical way to parallelize that because, again, most monoidal combinators are quite simple, like "integer addition", and the memory traversal costs completely dominate the problem and can not be parallelized).

This is also sort of an answer to "Why would you ever do this?" that others are asking in this thread. There are other languages that this is useful in. Monoid is an interface, basically, so you can write generic algorithms on that interface. Go's type system is not capable of expressing the interface in question, though.

It's useful to understand and recognize the general concept. There's virtually no way to use this recognition in Go, though.

[–]zoomzoom83 2 points 1 month ago 

Go doesn't support generic statically typed monoids. You won't get the nice clean typeclass based approach used in Haskell.

But a monoid does not require either of these things. Strings in Go are monoids, because they just are. Lists are monoids, because they just are. Any custom type with a default value and an associative concatenation function is a monoid, because it just is. Adding two numbers together? Monoid.

You don't need language support to use monoids. You may not be able to write generic code over any monoid in Go, but by obeying the monoid laws in your data types - even if not generic or type checked - you can be confident that your data type will behave in a specific sane way. (And more specifically, so will other developers using your type)

[–]natefinch 1 point 1 month ago 

My point was just that the blog post showed examples of how to construct the monoids, but not how to actually make use of the benefits they provide. And there were no examples of actually using the identity anywhere, except a self-referential proof that the identity is the identity.

[–]dasacc22 1 point 1 month ago 

there was no description of why the identity is important

Why the identity is important, in general, may be more clear with a different implementation of product

product = func(xs []float64) float64 {
    if len(xs) == 0 {
        return 1 // identity
    return xs[0] * product(xs[1:])

[–]natefinch 1 point 1 month ago 

Ahh, yes, that helps a lot. Thanks.

[–]Fwippy 2 points 1 month ago 

I'm not really familiar with a lot of CS terms - this is basically writing the "reduce" part of map/reduce, with the restriction that the reduction function is associative, which enables parallelism, right?

Also, I know I'd be confused as heck to see a function named mappend in actual code - I'd expect it to be named according to the actual operation performed, like concatenate or sum.

[–]boomshroom 1 point 1 month ago 

Except why would you have a function "concatenate" or "sum" when you're just using builtin types and "+" exists?

[–][deleted] 2 points 1 month ago 

Sadly addition with floating point numbers isn't associative:

package main

import "fmt"

func main() {
    x, y, z := 0.1, 0.2, 0.3
    fmt.Println((x+y)+z == x+(y+z)) // false

[–]boomshroom 1 point 1 month ago 

last I checked, 0.1 + 0.2 + 0.3 isn't supposed to equal 0.6000000000000001

Use of this site constitutes acceptance of our User Agreement and Privacy Policy (updated). © 2015 reddit inc. All rights reserved.

REDDIT and the ALIEN Logo are registered trademarks of reddit inc.