[Haskell-cafe] Could someone teach me why we use Data.Monoid?

wren ng thornton wren at freegeek.org
Fri Nov 13 21:34:24 EST 2009


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


More information about the Haskell-Cafe mailing list