Comment by dllthomas | Hacker News Reader

Comment by dllthomas | Hacker News Reader

Parent Full thread

"In addition, it must have an element that can combine with any other element and result in the other element."

Aka, an identity element.

Monoids that have inverses (that is, every element has another element that, when combined, produces the identity element) are "groups". Of the examples you gave:

"Strings over composition" does not form a group - there's nothing you can concatenate with a non-empty string to get an empty string.

"Integers over addition" does form a group. The inverse of x is -x.

"Natural numbers over max" is not a group. Once you get above 0 you cannot get back to it just by applying max.

"Booleans over and" is not a group. Once you have false you can't get back to true.

"Functions over composition" is not a group. Many functions have inverses, but some do not. If you restrict the set to "functions with inverses" then you do have a group.

Exactly. I was trying to avoid any mathematical jargon while describing monoids because they are such general and pervasive structures in programming. Further, being able to construct useful new monoids is crucial for making full use of a finger tree and I didn't want to have someone find an interesting structure unapproachable because they had to walk through an abstract algebra jargon storm in order to understand it. I realize I referenced associativity without describing it, so I didn't quite achieve my goal, but hopefully the examples got the idea across to someone who might otherwise have dismissed it due to the perception that it was too academic and unapproachable.

As an aside, trying to remove the jargon from a definition like this is surprisingly hard and really expands the size of the definition. I think it is still worthwhile to try when writing for a general audience because algebraic structure is everywhere and very useful to recognize for people who are interested in rigorously manipulating abstraction, i.e. programmers.

I agree; my "aka" wasn't meant as criticism. It's easy to get lost in the longer definitions, so I was just restating it directly in the hopes that one or the other - or the combination - will be clear to most people.

Though I'm not sure "abstract algebra jargon storm" properly describes use of "associative" and "identity" - I remember learning about the "associative property of multiplication" and such in elementary school and my wife confirms she had similar experience.

Reply on news.ycombinator.com