Five Minutes to Monoid

A “monoid” has an identity value, like 0 for addition and 1 for multiplication:

0 + value = value

1 * value = value

Naturally, identity goes both ways:

value + 0 = value

value * 1 = value

A monoid also has an associative operation. You probably learned about the associative property of addition and multiplication when you were ten years old. It just means that the order in which you perform the addition or multiplication of a series of numbers doesn’t matter:

(0 + 1) + 2 = 0 + (1 + 2)

(1 * 2) * 3 = 1 * (2 * 3)

A monoid extends these two ideas, identity and association, to any thing/entity/object for which you can imagine an identity value and an associative operation. A list, or array, is a fine example of a monoid from the world of programming languages. The identity of a list is an empty list. The associative operation is appending. Just as any number added to zero or multiplied by one is the same number, when you append an empty list to a list, you get back the original list:

[] ++ [1,2,3] = [1,2,3]

[1,2,3] ++ [] = [1,2,3]

[1,2,3] ++ [1,2,3] = [1,2,3,1,2,3]

Voilà. In a sense, you’re just defining what identity and append mean for any given monoid. “Appending” to a number can mean either addition or multiplication. Appending to a list means adding zero or more values onto the end of the list. Strings work the same way as lists:

"abc" ++ "" = "abc"
"" ++ "abc" = "abc"
"abc" ++ "xyz" = "abcxyz"

++ is the Haskell operator for appending to lists. I think it’s much nicer than having to type [1,2,3].append([1,2,3]) or some equivalent. And it allows for a more readable nesting of consecutive operations:

[1,2,3] ++ [4,5,6] ++ [7,8,9] = [1,2,3,4,5,6,7,8,9]

The monoid of lists is defined in Haskell more or less like this:

instance Monoid [a] where
  mempty = []
  mappend = (++)

mempty is Haskellese for the identity value: “monoid empty.” mappend is the associative operation: “monoid append.” Naming things is hard.

Haskell also provides some other interesting monoids for us out of the box:

instance Monoid All where
  mempty = All True
  mappend (All x) (All y) = All (x && y)
 
instance Monoid Any where
  mempty = Any False
  mappend (Any x) (Any y) = Any (x || y)

These are handy boolean monoids for expressing conjunction and disjunction. All is useful for determining whether all of a given set of values are true, like a boolean and (here &&), and Any determines whether any of them are true, like a boolean or (||):

> All True <> All False
All {getAll = False}
> All True <> All True
All {getAll = True}
> Any True <> Any False
Any {getAny = True}
> Any True <> Any True
All {getAll = True}
> Any True <> Any False <> Any False <> Any False
Any {getAny = True}

The <> symbol is an alias for mappend. It makes it a little easier to chain appending operations together. Since mappend is a binary operation like + or *, why not use a binary operator here, too? Note also that the results of evaluating the monoidal expressions above are packaged up in curly braces as a matter of syntactic convention. Actually, we need this packaging, because it would be otherwise difficult to distinguish among different monoids for the same types of values. For example, sums are different from products for numbers, so we can’t just use addition and multiplication monoidally without specifying which monoid we want to use. We need to supply this information by using their respective monoidal wrappers:

> Sum 1 <> Sum 2
Sum {getSum = 3}
> getProduct (Product 2 <> Product 2)
4

As you can see, getSum and getProduct are just accessor functions, and you can use them to extract the values from Sum and Product, if necessary.

Where monoids come in handy in programming is in any situation where you need to “fold over” or accumulate values into a final sum value, whatever “sum” means in the given context. This operation, called a “fold” in Haskell, is also called “reduce” in some other languages. Using the library function foldMap, we can simply supply a monoidal type and a list of values (more properly, any kind of value that is “foldable”), and the return result is their “sum” or final, accumulated value, as determined by the implementation of whichever monoid we use:

> foldMap Sum [1,2,3]
Sum {getSum = 6}
> foldMap Product [1,2,3]
Product {getProduct = 6}
> foldMap All [True, True, True]
All {getAll = True}
> foldMap Any [False, False, True]
Any {getAny = True}

As long as the type of value we are folding over is a monoid, then the fold will work as expected, and that’s a nice guarantee to have. If you want to understand what’s happening here in detail, go learn Haskell. Essentially, in the cases above, we’re asking for the final value after applying the associative operation of each monoid to every item in a list, starting with the first two and using the respective identity, or mempty, value as the base case of a recursion.

There are still other monoids worth knowing about:

> Just [1,2,3] <> Nothing
Just [1,2,3]
> Just [] <> Just [1,2,3]
Just [1,2,3]

Just and Nothing are the constructors for the Maybe type, which encodes the possibility that an expected value may be absent. Since Maybe has a Monoid implementation, we can mappend the values contained in a Just, if those values are monoids. Nothing serves as the identity in this case.

> First (Just 1) <> First (Just 2)
First {getFirst = Just 1}
> Last (Just 1) <> Last (Just 2)
Last {getLast = Just 2}
> foldMap First [Just True, Nothing, Just False]
First {getFirst = Just True}
> foldMap Last [Just True, Nothing, Just False]
Last {getLast = Just False}

First is a monoid that, given a series of Maybe values, captures the first one that is a Just and not Nothing. Last, predictably, does the opposite. Using foldMap, we can also apply these monoidal constructors to lists of Maybe values.

> Dual [1,2,3] <> Dual [4,5,6]
Dual {getDual = [4,5,6,1,2,3]}
> getDual $ foldMap (Dual . First) [Just True, Nothing, Just False]
First {getFirst = Just False}
> getDual $ foldMap (Dual . Last) [Just True, Nothing, Just False]
Last {getLast = Just True}

This last example is a little strange and not often used. Dual flips the arguments of its corresponding mappend. As you can see, it reverses the functionality of First and Last and, like the monoid for Maybe, also mandates that the values it contains be monoids. Monoids within monoids: they’re a beautiful thing.

Now that you know all about monoids, here’s a bit more vocabulary to help you through those awkward conversations with category theorists: a semigroup is a monoid without an identity, like a non-empty list. An Abelian monoid is a monoid that is also commutative, like addition and multiplication (but not lists or strings, for which order is significant). You can also just say commutative monoid or, if you prefer, not talk about them at all. But do spread the word about monoids. They are, quite literally, everywhere—whether you take advantage of their useful properties or not. Obviously, you should.