Making a monoid: the art of mush-mashing

In our last post, we looked at the many uses for the JavaScript array reduce method. While it can be used in many scenarios including, mapping, filtering, aggregation, recursion, and function composition, there is a certain pattern that reduce works particularly well with. This pattern happens to be called a monoid.

const numbers = [1, 2, 3, 4, 5];
const sum = numbers.reduce((a, b) => a + b, 0);
const product = numbers.reduce((a, b) => a * b, 1);
const min = numbers.reduce((a, b) => (a < b ? a : b), Infinity);
const max = numbers.reduce((a, b) => (a > b ? a : b), -Infinity);

const booleans = [true, false, false, true];
const any = booleans.reduce((a, b) => a || b, false);
const all = booleans.reduce((a, b) => a && b, true);

Interfaces are not very explicit in JavaScript, but any two objects that implement a certain set of methods can be said to share an interface. This interface can even be shared through prototypal inheritance or object composition. If we move one layer of abstraction higher, a monoid is simply a set of rules that an interface can follow.

The proper definition of a monoid is a set that is closed under an associative binary operation and that has an identity element. Let's break this down piece by piece. A binary operator is simply a function that takes two things of the same type, and mush-mashes them together to get another thing. If the new thing is of the same type as the original things, it is said to be closed. If it doesn't matter which order we apply the function to more than two things, than it is said to be associative. Finally, the identity is a special thing that when you run it through the function with a second thing, you always get back the second thing. Let's see some examples of monoids.

Examples of monoids

Addition and multiplication of numbers

Here, our binary operator is the + operator, which takes two numbers and produces another number. The identity is 0, which means when we add 0 to any number, we get back that number. Similar to addition, the binary operator for multiplication is the * operator, and the identity is 1.

Boolean logic

The boolean operators && and || take two boolean values and produce another boolean value. The identity for && is true and the identity for || is false. @t0nyba11 pointed out last time that using a reduce on a set of boolean values to find if any or all of them are true is not such a great idea. The reason for this is that the JavaScript engine is smart enough to know that boolean logic is a monoid, and therefore it can skip evaluation when it recognizes the identity of the operation.

Min and max

These may not be as immediately obvious, but min is a binary operator that takes two items, and returns the lower of the two. Notice that unlike addition and multiplication, min doesn't really create a new value. But because it produces a value of the same type as what it was given, it is a closed binary operation. Is there an identity to the min function? What can we pass to min to guarantee that the second thing is always returned? Well, if we always compare to Infinity, we will never get a number greater than that, so Infinity is our identity. The same is true for max with -Infinity as the identity.

Concatenation

Array concatenation takes two arrays and appends one to the other. The identity for this operation is simply an empty array. String concatenation work the same way with an empty string as the identity. Unlike the previous example we have seen, concatenation is not commutative, which means the order in which we pass the two arguments to the function matters. For example, "Hello".concat("World") does not produce the same thing as "World".concat("Hello"). Commutativity is not a requirement for a monoid.

Function composition

Function composition takes two functions and produces a new function that performs one after the other. Just like concatenation, function composition is not guaranteed to be commutative, which means calling f(g()) may not result in the same as g(f()). The identity of function composition is a special function called the identity function (unsurprisingly), and is defined as const id = (x) => x.

Monoids in practice

Composing monoids

One cool property about monoids is that you can create new monoids out of two or more existing monoids. Let's say we want a data structure containing a list of items with additional properties for the minimum and maximum values. We could implement this data structure like this:

function List(array) {
  this.list = array;
  this.min = Math.min(...array);
  this.max = Math.max(...array);
}
List.prototype.concat = function (list) {
  return new List(this.list.concat(list.list));
};

const list1 = new List([1, 2, 3]);
// List { list: [ 1, 2, 3 ], min: 1, max: 3 }
const list2 = new List([9, 8, 7]);
// List { list: [ 9, 8, 7 ], min: 7, max: 9 }
const list3 = list1.concat(list2);
// List { list: [ 1, 2, 3, 9, 8, 7 ], min: 1, max: 9 }

Notice how we didn't actually have to define the binary operation for the min and max properties. This is because whenever a new List is created, it is calculating the min and max of the given array. In the concat method, the two arrays are concatenated, and the min and max values are recalculated. This works pretty well for small Lists, but if we were to concatenate with large Lists, the min and max would have to run over all the elements of both lists again. To fix this problem, we can explicitly define the min and max operations in the concat method, but we'll also have to pull in their initial values in the constructor. We can add a static method to automatically calculate the min and max values from the given array:

function List(array, min, max) {
  this.list = array;
  this.min = min;
  this.max = max;
}
List.fromArray = function (array) {
  return new List(array, Math.min(...array), Math.max(...array));
};
List.prototype.concat = function ({ list, min, max }) {
  return new List(
    this.list.concat(list),
    Math.min(this.min, min),
    Math.max(this.max, max)
  );
};
const list1 = List.fromArray([1, 2, 3]);
// List { list: [ 1, 2, 3 ], min: 1, max: 3 }
const list2 = List.fromArray([9, 8, 7]);
// List { list: [ 9, 8, 7 ], min: 7, max: 9 }
const list3 = list1.concat(list2);
// List { list: [ 1, 2, 3, 9, 8, 7 ], min: 1, max: 9 }

Using monoids with reduce

And just like that, we are back to where we started! Monoids and reduce are a match made it heaven. Let's review the abstraction that reduce provides:

const array = [1, 2, 3, 4, 5];
const INITIAL_VALUE = 0;

const reducer = (accumulator, element) => accumulator + element;

// Without reduce
let accumulator = INITIAL_VALUE;
for (let i = 0; i < array.length; i++) {
  accumulator = reducer(accumulator, array[i])
}

// With reduce
const accumulator = arrray.reduce(reducer, INITIAL_VALUE);

The reducer is our binary operator that takes two elements of the same type, and mush-mashes them together. The INITIAL_VALUE is our identity for the reducer operation. If what we are giving the reduce method is indeed a monoid, we can leave off the initial value and it will use the first value in the array as the initial value.

NOTE: Not every application of the reduce method is an example of a monoid! If we can leave the initial argument off, we know that it is a monoid. This is because the accumulator must be of the same type as the elements in the array. If the accumulator is of a different type than the elements in the array, you'll have to provide an initial value, and you are no longer working with a monoid.

If this series has been interesting to you and you'd like to dive in deeper, check out the excellent series on the Fantasy Land specification by Tom Harding. Next time, we'll take a look at a coding challenge that applies some of the concepts we have covered so far.