Magicloud Magiclouds wrote:
Hum... simple like that. So you meant the Monoid just abstracts/represents the ability to build a stack, right?
The key idea behind monoids is that they define sequence. To get a handle on what that means, it helps to think first about the "free monoid". If we have some set S, then we can generate a monoid which describes sequences of elements drawn from S (the neutral element is the empty sequence, the operator is juxtaposition). The tricky thing is that we *really* mean sequences. That is, what we're abstracting over is the tree structure behind a sequence. So if we have a sequence like "abcd" we're abstracting over all the trees (a(b(cd))), (a((bc)d)), ((ab)(cd)),... including all the trees with neutral elements inserted anywhere: ((a)(b(cd))), the other ((a)(b(cd))), (a((b)(cd))),... The places where monoids are useful are exactly those places where we want to abstract over all those trees and consider them equal. By considering them equal, we know it's safe to pick any one of them arbitrarily so as to maximize performance, code legibility, or other factors. One use is when we realize the significance of distinguishing sequences from lists. Sequences have no tree structure because they abstract over all of them, whereas lists convert everything into a canonical right-branching structure. Difference-lists optimize lists by replacing them with a different structure that better represents the true equivalence between different ways of appending. Finger trees are another way of optimizing lists which is deeply connected to monoids. Another place that's helpful is if we want to fold over the sequence. We can parallelize any such fold because we know that the grouping and sequence of reductions are all equivalent. This is helpful for speeding up some computations, but it also lets us think about things like parallel parsing--- that is, actually building up the AST in parallel, working on the whole file at once rather than starting from the beginning and moving towards the end. Another place it's useful is when we have some sort of accumulator where we want to be able to accumulate groups of things as well as individual things. The prime example here is Duncan Coutts' example of supporting multiple config files (where commandline flags can be thought of as an additional config file). CSS is another example of this sort of accretion. Just to build on the config file example a bit more. What sorts of behavior do we expect from programs when some flag is specified more than once? The three most common strategies are: first one wins, last one wins, and take all of them as a list. All three of these are trivially monoids. Some of the stranger behaviors we find are also monoids. For example, some programs interpret more than one -v flag as incrementing the level of verbosity. This is just the free monoid generated by a singleton set, aka unary numbers, aka Peano integers. We could generalize this so that we accept multiple -v=N flags which increment the verbosity by N, in which case we get the (Int,0,+) monoid. Given all these different monoids, we can define the type signature of a config file as a mapping from flags to the monoids used to resolve them. And doing so is far and away the most elegant approach to config handling I've seen anywhere. So monoid == sequence. Similarly, commutative monoid == set. Stacks don't have a heck of a lot of equivalences, so I can't think of a nice algebraic structure that equates to them off-hand. (And the sequentiality of monads comes from being monoids on the category of endofunctors.) -- Live well, ~wren