Monoids, The Forgotten Friends

The Monoid typeclass is one of the simplest type clasees in Haskell’s Data package. Normally, it’s compared to an accumulator or a log. Although these comparisons could be helpfull for someone making his first contacts with the language, I think its simplicity makes it ideal for a more formal introduction. The difficulties a newbie will find with the formalisms will be paid off handsomely when they studies other more complex typeclasses and libraries.

Once you grasp the concept of monoids, you’ll start to see them everywhere, and what’s more important, you’ll learn how the famous Monoid, Functor, Foldable, Traversable and Monad classes will help you to write more generic code.

On Haskell and Mathematics

Before diving into the examples, let’s take a moment to talk about monoids, not as a Haskell typeclass, bus as a mathematical concept. In mathematics, a monoid is a triplet (type, value, function) that satisfy certain rules, the monoid rules. A type alone is not a monoid. Only the three element together, and only when they satisfy those rules, are a monoid.

In Haskell, concepts like monoids are approximated as type classes. A type class can declare values and functions, but it can’t declare rules. So, the monoid rules can’t be enforced in haskell. Also notice that a type can implement a type class only once, meanwhile, in math a type can be in several monoids.

Monoid Definition

In haskell, the monoid class is declared as:

1
2
3
4
class Monoid m where
  mempty :: m
  mappend :: m -> m -> m
  mconcat :: [m] -> m

Let’s forget for one moment mconcat, who’s not necessary for the minimal definition of Monoid and already has a default implementation. This means that a type m can be a monoid if it has one value, which we’ll call mempty and a function that takes two values of that type and returns a value of the exact same type. Additionaly, a monoid must satisfy the following rules (which can’t be expressed in the class definition):

1
2
mpemty `mappend` a = a
a `mappend` mpempty = a

This simply means that if one of the arguments of mappend is mempty, the result is the other argument.

Our First Monoid

Now that we know the definition of monoid, it’ll be nice to see some examples. To define a monoid we need a type, one value of that type and a function that satisfy the above definition. Let’s see if we can find a way to make monoids from a numeric type. Haskell has more than a dozen of number types, all of which are part of the Num class. Once we’ve chose our type (Num) we need a function that takes two numbers, and return another number. We have a lot of functions to chose: addition, substraction, multiplacation, division, potentation…

Let’s try with addition. With our type (Num), and mappend (+) selected, we only need mempty, a number that satisfy:

1
2
mempty + a = a
a + mempty = a

That number is of course zero. We’ve discovered that numbers, the addition and zero, form a monoid. Using mathematical language, we’d say that (Num, +, 0) is a monoid. So, we could make our Num an instance of Monoid using + as mappend and 0 as mempty. But there are other monoids that have numbers as their types. For example, (Num, *, 1) is also a monoid. And since both addition and multiplication are very important, and we can only chose a triplet for our Num monoid, Haskell, wisely, chose none.

Notice also, that we can’t make a monoid using - or /, we can’t find any mempty that satisfy the monoid rules for these functions.

More Examples

Other examples of triplets that form a monoid are:

• (Num, maxBound, <)
• (Num, minBound, >)
• (Boolean, False, ||)
• (Boolean, True, &&)
• (List, [], ++)

The idea that Monoid captures is that there are certain data types on which it makes sense to “summarize” (mappend) their values; data types who have a “null” (mempty) value. If you have two sounds, you can create a new one by playing them sequentially, that’s a Monoid. Or you can play them simultaneously, that’s another monoid. If you have two images, you can get a new one by putting them side by side, or one above other. There is a mempty sound (no sound) and a mempty image (a 0x0 pixels image).

Monoid Importance

In my opinion, the real importance of Monoid and other fundamental type classes (Functor, Traversable, Applicative, Foldable, Monad, …), is that they define very generic interfaces. As such, they can be applied in a broad range of situations, making the code more general, and transmitting a clearer idea of the nature of the algorithms.