Monads in Small Bites  Part III  Monoids
This is Part III of my Monads tutorial. Make sure you read the previous parts:
Part III  Monoids (this post)
Monoids
Simply put, Monoids describe types containing a binary function and an identity value.
When applied to the identity value and a random value x
, said function leaves its argument x
untouched, returning it as a result.
This short description should be enough to get the conversation started.
Here’s how Haskell defines a Monoid:
1 2 3 4 5 

This type introduces three new functions so let’s walk through each one of them:
mempty  I started with a lie since
mempty
isn’t actually a function. You can think of it as a constant of the same type of the Monoidm
. It is this monoid’s identity value.mappend  A poorly named function,
mappend
is the binary function I mentioned earlier. It receives two arguments of typem
and returns a value of typem
mconcat  It receives a list of Monoids
m
and reduces them to a single Monoid of typem
. What’s interesting about this snippet is that the Monoid type class provides a default implementation formconcat
: it simply calls foldr with the binary functionmappend
, a starting value ofmempty
and the list of Monoid valuesms
Enough Haskell! Let’s have a look at a few examples.
Did you know that, in Clojure, the functions *
and +
are monoids? Yup. But don’t take my word for it. Let me prove it to you:
1 2 3 4 5 6 7 8 

Whoa! What happened here? Am I just making this stuff up?
Not really. I only defined the same haskell names to their Clojure counterparts for clarity. Totally overkill. The code above is the same as:
1 2 3 4 5 

Did you notice that on the second call to reduce
we did not provide an initial value? That’s because reduce
will attempt to get its initial accumulator by calling the reducing function without arguments  hence mempty == (+)
.
So that means we don’t even need an mconcat
function since in Clojure, reduce
works with monoids as well!
Update: this isn’t entirely true. When I wrote this post I had in mind the version of
reduce
provided by the Clojure (1.5+) reducers library. The source code shows how that is the case.The implementation of
reduce
inclojure.core
however uses the first element of the collection being reduced over as its seed.
But how the hell do you create a monoid in Clojure then? I’m glad you asked. Let’s create our own plusmonoid!
Your first monoid
In Part I I implemented Functors using protocols and records. In Part II I showed how Applicative Functors could be implemented using multimethods.
This time around I won’t be using any of these. I’ll implement Monoids using pure functions:
1 2 3 4 5 6 7 8 9 10 11 

We start by defining a function with multiple arities. The first body receives no arguments, so we just return the identity value for summation, which is 0 (zero). The second body receives two arguments so we can just add them up. Multiplication can be implemented in a similar fashion but obviously with the identity value of one.
Easy, huh?
Oh, by the way, lists are Monoids too! Who’d have thought?
Here’s its Clojure implementation:
1 2 3 4 5 6 7 8 9 10 11 

Same rules apply but for lists mappend
is achieved by using concat
inside our monoid function.
Also, since our binary function concatenates two lists together it makes sense that mempty
is ()
(the empty list). Remember mempty
is supposed to be an identity value so if we stitch ()
and [1 2 3]
together, we’re left with [1 2 3]
which is exactly what we’d expect.
You can see now why I said
mappend
was poorly named. While it makes sense when you think about lists,mappend
doesn’t do any appending in our plusmonoid and in fact most monoids don’t append anything. Just keep this in mind if you see any haskell code using it:mappend
is just a binary function.
Don’t break the law
You saw this coming, huh? Monoids also come with a couple of laws. You know the drill. Let’s prove they both hold.
Identity
Applying
mappend
tomempty
and a monoidx
should be the same as the originalx
monoid.
In Haskell:
1 2 

And the proof in Clojure:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 

Associativity
Applying
mappend
to a monoidx
and the result of applyingmappend
to the monoidsy
andz
should be the same as first applyingmappend
to the monoidsx
andy
and then applyingmappend
to the resulting monoid and the monoidz
In Haskell:
1


And the proof in Clojure  remember that calling the monoid function with two arguments is equivalent to mappend
in haskell:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 

Almost there…
This puts an end to Part III. It’s time to head to the pub.
When you’re back look for the final post in these series  Part IV  where we will conclude our journey by finally introducing Monads!