wren ng thornton wren at freegeek.org
Sun Jan 18 05:09:35 EST 2009

```John Lato wrote:
> Here is the current complete documentation for Data.Monoid 'mappend',
> which happens to be a good example of which I speak:
>
>     An associative operation
>
> That could mean anything.  There are lots of associative operations.

Yes. In combination with the definition of mempty (the identity for
mappend) that's exactly what a monoid is.

I'm not (just) being flippant. This particular example actually
highlights the limitations of type classes. There are, in fact, too many
monoids. Too many to be able to define it based only on the carrier,
i.e. the type that mempty belongs to and that mappend operates over. For
example every (semi-)ring has at least two of them[1]. For more
complicated mathematical structures there can be even more than that.
This isn't to say that we should get rid of Monoid, just that using it
can be... troublesome. But this has been mentioned already on a few

The notion of appending only really applies to "the free monoid on a set
A", aka strings of elements drawn from A. It bears highlighting that I
said strings (in the mathematical sense) and not (linked) lists. The
concatenation involved is mathematical juxtaposition, and the empty
element is the empty string (which is subtly different than the empty
list which is also used to terminate the datatype's recursion). These
monoids are called free because they make no requirements on the
underlying set, no requirements other than the monoid laws. All other
monoids use some sort of structure in the underlying set in order to
simplify expressions (e.g. 1+1 == 2, whereas a+a == aa). Because the
free monoid doesn't simplify anything, all it does is append.

[1] For example,
Natural numbers:
(Nat,+,0)
(Nat,*,1)
Boolean algebra:
(Bool,or,False)
(Bool,and,True)
Bit-vector algebra:
(Bits,bitOr,0)
(Bits,bitAnd,-1)
Any lattice L:
(L,join,Bottom)
(L,meet,Top)
Any total ordering O:
(O,max,NegativeInfinity)
(O,min,Infinity)
Any set universe U:
(Power(U),union,EmptySet)
(Power(U),intersection,U)
...let alone getting into fun things like the log-semiring, polynomials
with natural coefficients, and so on.

--
Live well,
~wren
```