Monoids in Javascript

“Alternatively, the fundamental notion of category theory is that of a Monoid”

— Categories for the Working Mathematician

Wikipedia says a monoid is an algebraic structure with a single associative binary operation and an identity element. Any structure that has those two elements is a monoid.

Suppose that S is a structure and ⊗ is some binary operation S ⊗ S → S, then S with ⊗ is a monoid if it satisfies the following two axioms:

1. Associativity:   (a ⊗ b) ⊗ c = a ⊗ (b ⊗ c) holds.
2. Identity element: There exists an element e such that for all a  e ⊗ a = a ⊗ e = a  

Let us take the integers we can take addition as a binary operation between two integers.

The addition is associative. This means there is no importance on the order of the addition.

(x+(y+z)) = ((x+y) +z)

And 0 is the identity element for addition since :

x + 0 = x

For those reasons, the pair (+,0) forms a monoid over the integers. However, we can form different other monoids over the integers.

For example, multiplication * also can be viewed as a monoid with its respective identity element the 1. In this way the pair (*,1) is another monoid over the integers.

Strings in javascript have a default monoid, which is formed by the concatenation and the empty string (concat,‘’ ).

We will use monoids in our code by defining simple object literals that have two functions,

1. one that returns the identity element called empty

2. and one that represents the binary operation called concat .

var Sum = { empty: () => 0, concat: (x, y) => x + y }
var Product = { empty: () => 1, concat: (x, y) => x * y }

which we will use it like this:

Product.concat(Product.empty(), 5);

This definition would allow us to use it with the reduce function of a list in a direct manner

Alternatively, if we want to have closure [meaning that the return type of the concat and empty is of the same type with the initial object], we could define one new class for each monoid.

The return type is Sum allowing for fluent chaining. You can Run the jsFiddle below:

Folding Monoids

Monoids have this very desirable property that if we keep applying this binary operation, we can always reduce the computation to a single element of the same type:

(M⊗…(M (⊗(M ⊗ M))) → M

this is called folding. We already know folding as reduce from the js Array type. However, we are going to generalize fold in a latter chapter for data structures that we will call traversables. Coming back to fold, let us try to derive reduce.

Lets say we have some sequence of integers 2,4,5,6 and we want to add them this a beginner level problem:

var array  = [2,4,5,6 ]
var accumulation = 0;
    for (let i = 0; i < array.length; i++) {
     const element = array[i];
    accumulation =  accumulation + element
}

I highlighted there the elements of a monoid. So, let’s abstract away. If we replace the (0,+) with any other monoid this should work, so why not abstract and reuse.

Now we can use this function with all kind of monoids

var sum = fold([2, 4, 5, 6],
       { empty: () => 0, concat: (a, b) => a + b })
var product = fold([2, 4, 5, 6], 
      { empty: () => 1, concat: (a, b) => a * b })
var max = fold([2, 4, 5, 6], 
     { empty: () => -Infinity, concat: (a, b) => Math.max(a, b) })

you might recognize that this actually is the array.reduce . The reduce is nothing more than an abstraction of the for loop.