Mixin Monoidal behavior in JavaScript

Like these ninjas, the term monoid is a bit aggressive and intimidating. In practice, though, it’s a actually a very simple concept with very powerful applications not only in mathematics, but in application code and programming language design. To begin, let’s define another stealthy concept — a Semigroup.

Semigroup

Semigroups are more of a recent concept relative to its monoid sibling. Both are algebraic structures. An algebraic structure represents a set of possible elements (e.g the characters in a string or the positive natural numbers) with one or more operations (functions) that abide by certain laws (axioms).

In the case of a semigroup, there is a set of elements with only one binary operation that closes over or restricts the elements contained in said group (hence, “semi”); this operation by contract must be associative. Like we learned in algebra, associative means that you can group the operations different ways and the result is the same:

a . b . c = a . ( b . c ) = ( a . b ) . c

Without going into much detail here, I just want it to point out that if the operations performed on these elements could be carried out in this fashion, then that would imply that each one of them benefits from a certain level of isolation. That is to say, the order doesn’t matter (namely, run b and c, then combine it with a, or run a and b and combine that result with c) so long as the sequence of the operands in question remains the same. This implies that how you obtain these elements (if a, b, c were the results of some arbitrary computations) could be parallelized. I’ll come back to this idea of parallelism later on, for this problem has already been solved using a monoid in JavaScript (care to guess what that is?).

Note: An even smaller semigroup is called commutative if the elements in the set also commute a . b = b . a with respect to its binary operation ..

Back to our discussion, what does the . represent? Associativity requires that this operation be additive. In the Fantasy Land Spec this is known as concat. Encoding the associativity law above results in:

a.concat(b).concat(c) = a.concat(b.concat(c)) = (a.concat(b)).concat(c)

An example of this could be a logging system. Log messages from several decoupled, parallel processes could be aggregated together (ideally sorted by a timestamp) through a reduction process into a single log file. Also think about XML. You can append XML elements together and then take resulting XML element and append further.

For our first example, logs (or strings) form a semigroup. In JavaScript, the operator + is overladed for concatenation of strings:

'Log 1' + 'Log2' + 'Log 3' = 'Log 1' + ('Log2' + 'Log 3')

And is equivalent to:

'Log 1'.concat('Log2').concat('Log 3') = 'Log 1'.concat('Log2'.concat('Log 3'))

It’s intuitive to see that the set of Strings forms a semigroup with respect to+ : Semigroup(String, +) . In addition, the natural numbers form a semigroup with respect to addition Semigroup(Number, +) and multiplication Semigroup(Number, *)(Only in special circumstances for subtraction and division).

So, that’s the gist of a semigroup. From here, we take a tiny leap to get to Monoid.

Monoid

Monoids are semigroups. Done!

As such they are algebraic structures with a Set and a single binary associative (additive) operation (concat). In addition, its set has a single identity element (also known as empty or neutral element) with the following laws. For any monoid M:

  1. m.concat(M.empty()) leaves m unchanged (right identity)
  2. M.empty().concat(m) leaves m unchanged (left identity)

We’ll be proving this law as well as associativity. In other words, monoids are commutative with respect to concat and its neutral element, irrespective of what they are.

Note: You can understand monoids from two perspectives: a set-theoretic definition of monoid (a set of elements with identity and a binary operation). Or a categorical definition that kind of raises the abstraction and treats the monoid as a category with a single object M (hence, “mono”) , and each element of the category is a morphism f :: M -> M ; the binary operator is the composition in the category.

Moving along, just like strings, numbers, and XML elements, monoids concatenate into self-similar structures, this is the how they mostly occur in programming, but can also combine with other monoidal structures of the same type. The identity element is a member of the set that when combined with its given binary operation leaves the elements unchanged. Parting from the semigroups shown before we can spot monoids likeMonoid(Number, +, 0), Monoid(Number, *, 1), Monoid(String, +, ''), Monoid(Boolean, OR, False), Monoid(Boolean, AND, True), and many others. Actually lots of monoidal patterns occur in programming. Another very important one, as you might have guessed, in JavaScript is Monoid(Array, concat, []).

Note: Arrays are monoidal in JavaScript only when Symbol.isConcatSpreadable = true which is the default and shouldn’t ever be changed unless you have a specific need for doing so; otherwise, the structures won’t be equivalent under associativity.

Here’s another more subtle monoid representing JavaScript’s prototypal inheritance mechanism: Monoid(Object, Object.create, {}) and for any class-based inheritance language like Java, we could use Monoid(Class, extends, Object). Some food for thought.

Let’s get to the fun part. There have been plenty of posts on monoids using JavaScript and other languages. In this one, I want to do something a bit differently. My goal is declare a Monoid contract as a reusable, decoupled object behavior and not hard-coded into the object/class declaration. For this, I’d thought it would be nice to use mixins to dynamically enhance any user-defined type to behave as a monoid.

Mixins

A mixin is a way to extend an object’s prototype with some arbitrary behavior — think traits. I’ll be using Reg’s FunctionalMixin in this case to embed the monoid behavior, as such: mixin(type, monoid).

Note: In this case, “functional” has nothing to do with functional programming; rather it means to literally use a function to mix-in the behavior and get around some limitations with object mixins using Object.assign.

Our First Example

I’ll start out with some simple monoids, and work my way up to more interesting, useful ones.

Numbers over addition

This one is a bit trivial because, as mentioned earlier, numbers already behave this way. Numbers form monoids with binary operations + or * and their identities 0 and 1, respectively. But, I’ll go ahead and formalize it for illustration.

First, I’ll define the monoid contract: Sum = Monoid(Number, +, 0). In code:

const Sum = FunctionalMixin({
concat(m) {
return this + m
},
empty() {
return Sum.ID
},
[FunctionalMixin.shared]: {
ID: 0,
}
})

And use this to enhance all numbers:

Sum(Number.prototype)
Number.empty = () => Sum.ID

Now, the laws are straightforward:

Right and left identity

assert.equal(Number(123).concat(Number.empty()), 123)
assert.equal(Number.empty().concat(123), 123)
// 123 + 0 = 0 + 123

Associativity:

const a = Number(10),
b = Number(20),
c = Number(30)
assert.equal(a.concat(b.concat(c)), (a.concat(b)).concat(c))
// 10 + (20 + 30) = (10 + 20) + 30

This example shows the concept of using the FunctionalMixin to embed this behavior. But this isn’t something you would need to do, it’s for demo purposes only. So, let’s move on to a more useful application of this pattern.

History monoid

Let’s part from a simple Writer type that relates a function with the log accompanying it. It’s a way to trace through function calls.

class Writer {
constructor(fn, str) {
this.fn = fn
this.trace = str
}
    static of(fn, str) {
return new Writer(fn, str)
}
    fn() {
return this.fn
}
    run() {
return this.fn()
}
    log() {
return this.trace
}
}
let w = Writer.of(() => 42, 'Life, the Universe, and Everything')
w.run() // 42
w.log() // 'Life, the Universe, and Everything'

Because Writer maps basically two sets of elements: functions and strings, I need a pair that would equally meet the monoidal laws and work with concat and empty.

Consider the typePair with a left and a right element. As you know, pairs don’t posses any business logic or behavior of their own — they are just 2-tuples. Therefore, a pair is monoidal only if its corresponding elements are monoidal. In essence, we’re not inventing a new class of elements here, just combining them. Writer stores an operation (Function) with its log (String).

We already talked about Monoid(String, +, ''), let’s focus on Function. Functions are monoidal with respect to composition and identity function (id = x => x) orMonoid(Function, compose, id). The laws are straightforward to prove using compose:

compose(f, id) = compose(id, f)
compose(compose(a, b), c) = compose(a, compose(b, c))

Now, we’ll use the FunctionalMixin so that Writer behaves like a monoid using a pair:

const MPair = FunctionalMixin({
concat(m) {
return new this.constructor(
R.compose(m.fn, this.fn), // left
this.trace.concat(m.trace)) // right
},
empty() {
return new this.constructor(id, this.trace.empty())
}
})
MPair(Writer.prototype)
Writer.empty = () => new Writer(id, String.empty())

On the left, functions concatenate using composition, and on the right strings concatenate with append.

Note: We could add another dimension, say a number that holds the timestamp of the log, and make it a 3-tuple. This would work as well because numbers are monoidal with respect to addition as you saw earlier.

You can easily verify that all of the laws hold. By doing this, now I can trace through an entire sequence of functions and collect the logs at the end:

let h = Writer.of(() => 10, 'Starting with 10.')
.concat(Writer.of(val => val + 20, 'Adding 20.'))
.concat(Writer.of(val => val + 30, 'Adding 30.'))
.concat(Writer.of(result => result / 3, 'Dividing by 3.'))
.concat(Writer.of(id, 'Printing result.'))
assert.equal(h.run(), 20)
assert.equal(h.log(), 'Starting with 10.Adding 20.Adding 30.Dividing by 3.Printing result.')

Using these simple rules, I was able to lift the trace of a single function call into a trace of a sequence of calls — a history. In fact, there is such a thing as a History monoid, used for representing the history of running processes as a collection of strings . This was a drastic simplification of that.

This all sounds very cool, it seems there’s lots of foundations in monoids as chainable computations!

What about async?

The reality is, however, that in JavaScript 95% of the time you’re dealing with an asynchronous API of some sort, whether it’s file IO, HTTP call, interacting with the console, etc. So can monoids help us here as well?

As you saw earlier, functions are monoidal over composition, so whether they are asynchronous is beside the point. All we need to do is make sure that we use an asynchronous abstraction that is also monoidal under some form of “concatenation.” How do we concatenate events separated in time? “Do this then do that…” How about promises? If asynchronous functions is what we want, let’s implement the Chain monoid around promises and composition.

const then = f => p => p.then(f)
const now = x => Promise.resolve(x)
const Chain = FunctionalMixin({
concat(m) {
return new this.constructor(
R.compose(then(m.fn), this.fn))
},
empty() {
return new this.constructor(now)
}
})

As identity I choice a promise that resolve right-away. Just so that we don’t mess with the Function.prototype, consider this simple wrapper.

class Computation {
constructor(fn) {
this.fn = fn
}
run(withValue) {
return this.fn(withValue)
}
static of(fn) {
return new Computation(fn)
}
}
Chain(Computation.prototype)
Computation.empty = () => new Computation(now)

Given a simple function helper to test this out with:

const asyncConcatN = N => x => new Promise((resolve, reject) => {
setTimeout(() => {
console.log(`Invoking long running
process using ${x} and ${N}...`)
resolve(x.concat(N))
}, 2000)
})
const a = Computation.of(asyncConcatN(10))
const b = Computation.of(asyncConcatN(20))
const c = Computation.of(asyncConcatN(30))

Similar to the synchronous case, the order I combine these doesn’t matter, the result is the same:

// right associative
a.concat(b.concat(c))
.run(Number.empty())
.then(result => {
assert.equal(result, 60)
})
// left associative
(a.concat(b)).concat(c)
.run(Number.empty())
.then(result => {
assert.equal(result, 60)
})
// Running long running process using 0 and 10...
// Running long running process using 10 and 20...
// Running long running process using 30 and 30...

That’s quite impressive because now I don’t have to really worry about the timing of these functions or deeply nested callbacks, they are still executing in the same manner.

In fact, this monoid pattern has penetrated deeply into the design of Promise. Coming back to the relationship between associativity and concurrency I alluded to earlier, you can see that reflected here:

Promise.all([Promise.all([a, b]), c]))
Promise.all([a, Promise.all([b, c]))

Last but not least: Fold

Endowing classes with monoid behavior has other benefits. One such benefit is the ability some abstract data type, like a list, to be “folded” or “reduced” to a single value. You’re already familiar with this concept in JavaScript arrays:

[1,2,3,4,5].reduce(add, 0) // 15 

More specifically, a fold takes two parameters: an accumulator callback function and an initial value. Hence, we can make a direct parallel to monoids as naturally foldable with concat as the accumulator and empty as the initial value. And because this is the contract that all monoids abide by, we can generalize a single fold function to work with all of them!

// fold :: Monoid m -> [m] -> m
function fold(M) {
return arr =>
arr.reduce((acc, m) => acc.concat(m), M.empty())
}

This will work in all cases with elements of type M, irrespective of what M is because reduce only relies on the monoid contract. From numbers:

assert.equal(fold(Number)([1,2,3,4,5]), 15)

To strings:

assert.equal(fold(String)(['123', '456', '789']), '123456789')

And arrays:

assert.deepEqual(fold(Array)([[1], [2], [3], [4], [5]]), [1, 2, 3, 4, 5])

Finally, even asynchronous functions:

it('Should fold into a single value', ()  => {
return fold(Computation)([a, b, c])
.run(Number.empty())
.then(result => {
assert.equal(result, 60)
})
})

And it doesn’t take a ninja to walk the path of the monoid!

To conclude, remember a monoid is an algebraic structure with just an additive operation with an identity object. While very simple in structure, it’s use is immensely powerful and has inspired lots of really great API designs over the years.

Thanks! I hope you were able to get something out of this. For those of you who don’t know me, I’m Luis Atencio author of Functional Programming in JavaScript, an introductory tour of important FP concepts in JS, and RxJS in Action.

One clap, two clap, three clap, forty?

By clapping more or less, you can signal to us which stories really stand out.