[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