benmachine/

Monoid in a single method

Here's the standard Monoid class:

class Monoid m where
  mempty :: m
  mappend :: m -> m -> m

and laws:

mappend mempty x = x
mappend x mempty = x
mappend (mappend x y) z = mappend x (mappend y z)

I claim this is equivalent to:

class Monoid m where
  mconcat :: [m] -> m

with the laws:

mconcat [x] = x
mconcat . map mconcat = mconcat . concat

First, define mconcat in terms of mempty and mappend, as usual:

mconcat = foldr mappend mempty

and prove its first law:

mconcat [x]
  = foldr mappend mempty [x]
  = mappend x (foldr mappend mempty [])
  = mappend x mempty
  = x

Proving rigorously that the second law holds for all monoids is a little tedious, but the intuition is clear: given a list of lists of monoids, you can combine the inner lists first, and combine the results, or you can concatenate the lists into a big long list, and then combine that. Thinking of associativity as the ability to parenthise an expression freely, you can see the sublists as parentheses, and the second law tells you that you can throw them away.

Okay, now the less usual way around: suppose we have an mconcat that satisfies those laws. It's pretty easy to imagine how you might define mempty and mappend from it:

mempty = mconcat []
mappend x y = mconcat [x,y]

Now, we need to prove the original Monoid laws using the laws we came up with for mconcat.

First, the identity laws:

mappend x mempty
  = mconcat [x,mempty]
  = mconcat [mconcat [x],mconcat []]
  = (mconcat . map mconcat) [[x],[]]
  = (mconcat . concat) [[x],[]]
  = mconcat [x]
  = x

and likewise on the other side. Notice that we used both laws in this proof: either one alone will not do! Now, associativity:

mappend (mappend x y) z
  = mconcat [mconcat [x,y],z]
  = mconcat [mconcat [x,y],mconcat [z]]
  = (mconcat . map mconcat) [[x,y],[z]]
  = (mconcat . concat) [[x,y],[z]]
  = mconcat [x,y,z]
  = (mconcat . concat) [[x],[y,z]]
  = (mconcat . map mconcat) [[x],[y,z]]
  = mconcat [mconcat [x],mconcat [y,z]]
  = mconcat [x,mconcat [y,z]]
  = mappend x (mappend y z)

Done! So defining a monoid instance is equivalent to defining a way to squash a list-of-things into a thing, subject to some natural conditions. Notice that the mconcat laws don't directly correspond to the traditional ones in the sense that there isn't an identity law or an associativity law – both are necessary to prove either.