A monoid is a mathematical structure which captures associativity (a+(b+c) = (a+b)+c) and has an identity notion (a + 0 = 0 + a = a).
They're useful because knowing them allows for identifying and mechanically applying transformations to better leverage parallelism and easily implement incremental computations†.
If you've been programming for a while, I can guarantee you already intuitively understand the concept. Giving it a name allows you to automatically recognize and notice that you've already solved this problem before in another guise.
Alternatively, having named the concept, it's now chunked into your toolkit for use whenever applicable. Structuring your solution so you know it's a monoid allows leveraging all those benefits almost for free.
†With divide and conquer, add memoization and pay attention to the order of subproblems such that you can reuse earlier work, and if you can, we're nearly at dynamic programming. We can specify a bit more structure, to get semirings and collapse a whole heap of disparate seeming machine learning algorithms. But now I have gone too far afield.
A monoid is a concept from math. They have a set of objects (like the integers), and a binary operation (like addition or multiplication over integers). The operation is associative (like addition where the order you compute a set of additions doesn’t matter, you get the same sum). And there’s an identity element (in addition this would be 0).
For CS there are some nice results where the operation can be automatically parallelized. Useful for things like MapReduce if you need to run things at large scale, or in this case for distributing the work over the many shader units of a GPU.
So a bunch of people are giving you good definitions. Here's an article that does FizzBuzz with monoids. I think this is the first thing I saw that actually cemented them into my mind. Probably because it takes a problem-to-solution teaching method. (Unfortunately looks like the original page is dead.)
I just notice a common pattern in a lot of these answers
* First, give a definition
* then some basic examples to clarify the concept
* then some advanced usage to demonstrate the advantages.
I tend to do it myself, maybe because a math concept has a clear definition and math courses do it too. However, it scares away a lot of people, including myself when I'm on the receiving end.
A monoid is a set S with an associative binary operation and a unit. For instance, strings with string concatenation and the empty string form a monoid.
Functions form a monoid as well. Function composition is associative and id is the unit.
From a programming perspective it is a way go generalize adding two things together, but where the order might matter (or might not!).
+ is a monoid. It adds to numbers together. (3+3)+4 = 3+(3+4)
But also concatenation is a monoid
"a" + ("b" + "c") = ("a" + "b") + "c".
Monoids have an empty thing you can add to anything.
E.g. 0 for + and "" for concatenation.
In Haskell, Monoids are abstracted out into a typeclass so that you can write code on any monoid. For example fold up a list of monoid elements into a single element.
To relate it to something you're more likely to already know: it's like a group (in the mathematical sense), except that it doesn't necessarily have inverses.
The paper it mentions and links (The Early Development of the Algebraic Theory of Semigroups) is freely available and has a bunch of discussion of terminology.
Stacks are used in parsing algorithms. In order to create a parallelized parsing algorithm the author has found this monoid representing stacks and stack operations (specifically push and pop). If this pans out, the result is a potential tool in running parsing algorithms in parallel (specifically on GPUs in their desired use-case).
Thank you. So am I correct that he had created a type (for lack of a better term) representing a number of pushes and pops. And the monoid is the algebraic construct that let's us combine those types. So faced with a string of square braces representing pushes and pops like in the example, we can divide them into chunks, count push and pops (also recording indices?) in parallel, and then combine them?
Yes, that's basically it. There are more details, like how I think this can efficiently be implemented on GPU hardware (it's not clear at all that this is the case), but you and GP have captured the basic motivation and idea.
An important example from CS would be the semigroup action on the set of states of a deterministic finite automaton.
The action takes a state from Q, and a symbol from E, and returns a new state. ie f:QxE->Q.
In the case when you have some "no op" action the semigroup action is actually a monoid action.
This all corresponds to the DFA moving through states as it "eats" the string.
Yupyup. For those of us who don't just automatically know what a semigroup action is, Dan Piponi's blog on using monoids to do incremental regular expression matching is probably a good read: http://blog.sigfpe.com/2009/01/fast-incremental-regular-expr...
