Posted on by & filed under Content - Highlights and Reviews, Programming & Development.

The term monoid frustrates a lot of programmers who otherwise are pretty versatile with higher-order generics, mutexes and even XSLT. This blog post will show how using monoids can be very simple and practical. Monoids are the basis of more complicated algebraic structures in mathematics, and are the underlying entities in many operations that we do while coding. There is a code sample in this post for Scala, which is becoming a lingua franca these days, and subsequent posts will focus on Scala.

When you deal with various types in a programming language you will notice common patterns of behavior for binary operations. Here are some examples:

1. Integers with addition. We know that `(a+b)+c == a+(b+c)` and `0+n == n+0 == n`; same with multiplication: `(a*b)*c == a*(b*c)` and `1*n == n*1 == n`
2. Strings with concatenation. `a+(b+c)==(a+b)+c; ""+s==s` and `s+"" == s`, etc.
3. Lists with concatenation, like `List(1,2)+List(3,4) == List(1,2,3,4)`.
4. Sets with their union, like `Set(1,2,3)+Set(2,4) == Set(1,2,3,4)`.

See a common pattern with a data type, a binary operation, and a special instance of the type, and certain rules? This common pattern is called monoid. Read Chapter 12: Monoids for more details about monoids.

Formally

Now, I’ll give a strict formal definition of monoid. Given a type `T`, a binary operation `Op:(T,T) => T`, and an instance `Zero: T`, with the properties that will be specified below, the triple `(T, Op, Zero)` is called a monoid. Here are the properties:

1. Neutral element: `Zero Op a == a Op Zero == a`
2. Associativity: `(a Op b) Op c == a Op (b Op c)`

Now, not every binary operation in the world is associative. For example, this average: `avg(10, avg(30, 50)) != avg(avg(10, 30), 50)`; and for tuples, `(a,(b,c)) != ((a,b),c)`.

So, you may be wondering what’s good about associativity? With an associative operation, you can reorganize a calculation in any order. Say, for instance, that we have the following expression:

In Scala we have, `(Zero /: a) (x Op y)`. This calculation can be regrouped and run in parallel, enabling map/reduce as follows:

The definition above is all that you need to check whether you have a monoid. But it is important to see relationships between monoids. If you have just types, without any additional structure, any function, such as `f:A=>B`, is good for mapping instances of one type to instances of another. But if we have monoids, mappings between monoids should preserve operations.

Mappings Between Monoids

For two monoids, `(A, OpA, ZeroA)` and `(B, OpB, ZeroB)`, we define a mapping from one monoid to another, such as with a function `f: A => B`, that `f(ZeroA) = ZeroB` and `f(x OpA y) = f(x) OpB f(y)`.

Here are some good examples of monoid mappings:

• `exp: (Double,+,0) => (Double,*,1); exp(a+b) == exp(a)*exp(b)`
• length: `(String,+,””) => (Int,+,0)`
• sum: `(List[Int],++,Nil) => (Int,+,0)`

Free Monoids

For any type `T` we can build a monoid on it. Such a monoid will have an interesting universal property, as discussed next.

Suppose we have a type `A`, a monoid `(B, OpB, ZeroB)`, and a function `f:A=>B`. This function just maps instances of `A` to instances of `B`. Now we can extend this function to a monoid mapping from `List[A]` to `(B, OpB, ZeroB)`.

Obviously, if we have `f:A=>B`, we can apply `f` to elements of any list of elements of type `A`, and then fold as follows:

This monoid mapping is uniquely determined by `f`, and it defines `f` if applied to singletons.

`List[A]` is a free monoid because it’s built out of `A` with no constraints, in a universal way.

Let’s look at a simple example. Suppose we have the following:

And the following function:

Having a monoid `(Int, +, 0)`, we can automatically extend this mapping to `List[WeekDay]->Int`, which counts the number of working days.

More Properties?

Not all monoids are created equal. We can find classes of monoids that have additional properties, reflecting the nature of their operations. In this section we will discuss some of those properties.

Commutative Monoids

To start with, here is the commutativity law: for all `a` and `b`, `a Op b == b Op a`.

Some monoids are commutative, and some are not:

But that isn’t true with strings:

You might wonder if we can build a free commutative monoid? Say we have a list of characters: “`abracadabra`“. Forget about the concatenation order; we can just count the number of each entry – or sort the list, obtaining “`aaaaabbcdrr`“. Only the number of occurrences of each element matters – meaning, we have what is known as a Multiset or a Bag:

To count, say, all of the birds, we don’t need to know on which day they were appended to the multiset.

Sets have an interesting property: a set `A` joined with itself is still `set A`. Instances with properties like this are called idempotent:

If we take Bags and add the property for each instance that is idempotent, we have Sets.
Here’s the hierarchy, from Alexander Bunkenburg, “The Boom Hierarchy”.

In Scala

To define a monoid in Scala, we declare the following:

Then, if we define a new class, it can also extend `Monoid[T]`. This is impossible if the class already exists, like, `Int` or `String`. We may need to specify which operation we mean to be the monoidal operation. This is where type class should be used. In Haskell, a type class is defined as just an interface. In Scala; however, it is more complicated. It can depend upon the scope, and involves a so-called witness object. All this will be explained in more detail in my next blog post, so stay tuned.

Safari Books Online has the content you need

Check out these monoid and Scala books available from Safari Books Online: