An intro to Monoids

And the ‘or’ operator as a monoid.

A monoid (not to be confused with the much talked about monad) is an algebraic structure that has an associative binary function, and an identity element. That is, it must obey two laws:

First, it must have an identity element (`empty`) that acts as an identity with respect to the binary function (`f`).

f empty x = x
f x empty = x

Second, the binary function (`f`) must be associative.

f (f x y) z = f x (f y z)

A specific example of a well known monoid data type are lists. In Haskell, the above laws can be proved out like so:

# identity
[1, 2, 3] `mappend` mempty = [1, 2, 3]
mempty `mappend` [1, 2, 3] = [1, 2, 3]
# associativity
([1, 2] `mappend` [3, 4]) `mappend` [5, 6] == 
 [1, 2] `mappend` ([3, 4] `mappend` [5, 6])

Which is great — Haskell is built off these algebraic principles. What would this look like in a more widely used language, such as JavaScript? Well, we don’t have the built in monoid functions like `mempty` or `mconcat`, but we can get pretty close using out of the box JS:

# identity
[1, 2, 3].concat([]) = [1, 2, 3]
[].concat([1, 2, 3]) = [1, 2, 3]
# associativity
[1, 2].concat([3, 4]).concat([5, 6]) == 
[1, 2].concat([3, 4].concat([5, 6]))

This is super cool. A simple JavaScript array is a monoid — a classic algebraic structure — hiding in plain site all this time. In the example above we use an empty list as the identity value, since an empty list appended or prepended to any other list just returns the original list. The binary function is `concat`, which takes two lists and returns a new list with all the elements joined.

As another example, the standard ‘or’ operator — generally invoked with two pipes`||` — can easily be made into a monoid. In this case, the indentity value would be `false`, since any boolean value or false will return the original value. Let’s try that out:

false || false = false
true  || false = true

Perfect — works like an identity value, just like the empty list did. Our `append` function will essentially be an alias for the or operation, our binary function. We already know that’s associative:

(false || false) || true == false || (false || true)

Putting it all together and wrapping our values into a type-like object might look something like this:

function Or(v) {
  return {
    value: v
  };
}
function empty() {
 return Or(false);
}
function append(m1, m2) {
 return Or(m1.value || m2.value);
}

Let’s give it a spin, first proving identity:

append(empty(), Or(true)) => Or(true)
append(Or(false), empty()) => Or(false)

Nice! Now associativity:

var generalAppend = append(Or(false), Or(true))
append(generalAppend, Or(false)) => Or(true)
append(Or(true), generalAppend) => Or(true)

Very good, and one more function for fun — concat. Not to be confused with `list.concat`, in Haskell monoids generally come with an `mconcat` function, which takes a list of monoids of the same type and reduces that list with the monoid’s binary function, starting with the indentity value. With our ‘or’ monoid, that implementation would look something like this:

function concat(ms) {
  return ms.reduce(append, empty());
}

Taking a step back, imagine taking a list of boolean values, and repeatedly calling the ‘or’ operation between them (false || true || true || false). That is exactly what the above `concat` method will do. Check it out:

concat([Or(false), Or(false), Or(true)]) => Or(true)
concat([Or(false), Or(false), Or(false)]) => Or(false)

Now that’s cool. And hey, monoids ain’t that bad. A gist with the source code and some assertions can be found here. Also, Learn You a Haskell’s chapter on monoids is a great resource for a deeper introduction on the topic.