[Haskell-cafe] Re: Comments from OCaml Hacker Brian Hurt

[wren ng thornton]

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 
other recent threads.

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