Monoid
in a single methodHere'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.