# Chapter 13: Monoids bring it all together

In this chapter, we will examine

*monoids*by way of*semigroup*.*Monoids*are the bubblegum in the hair of mathematical abstraction. They capture an idea that spans multiple disciplines, figuratively and literally bringing them all together. They are the ominous force that connects all that calculates. The oxygen in our code base, the ground on which it runs, quantum entanglement encoded.*Monoids*are about combination. But what is combination? It can mean so many things from accumulation to concatenation to multiplication to choice, composition, ordering, even evaluation! We'll see many examples here, but we'll only tip-toe on the foothills of monoid mountain. The instances are plentiful and applications vast. The aim of this chapter is to provide a good intuition so you can make some

*monoids*of your own.

Addition has some interesting qualities I'd like to discuss. Let's have a look at it through our abstraction goggles.

For starters, it's a binary operation, that is, an operation which takes two values and returns a value, all within the same set.

// a binary operation

1 + 1 = 2

See? Two values in the domain, one value in the codomain, all the same set - numbers, as it were. Some might say numbers are "closed under addition", meaning the type won't ever change no matter which ones get tossed into the mix. That means we can chain the operation since the result is always another number:

// we can run this on any amount of numbers

1 + 7 + 5 + 4 + ...

In addition to that (what a calculated pun...), we have associativity which buys us the ability to group operations however we please. Incidentally, an associative, binary operation is a recipe for parallel computation because we can chunk and distribute work.

// associativity

(1 + 2) + 3 = 6

1 + (2 + 3) = 6

Now, don't go confusing this with commutativity which allows us to rearrange the order. While that holds for addition, we're not particularly interested in that property at the moment - too specific for our abstraction needs.

Come to think of it, what properties should be in our abstract superclass anyways? What traits are specific to addition and what ones can be generalized? Are there other abstractions amidst this hierarchy or is it all one chunk? It's this kind of thinking that our mathematical forefathers applied when conceiving the interfaces in abstract algebra.

As it happens, those old school abstractionists landed on the concept of a

*group*when abstracting addition. A*group*has all the bells and whistles including the concept of negative numbers. Here, we're only interested in that associative binary operator so we'll choose the less specific interface*Semigroup*. A*Semigroup*is a type with a`concat`

method which acts as our associative binary operator.Let's implement it for addition and call it

`Sum`

:const Sum = x => ({

x,

concat: other => Sum(x + other.x)

})

Note we

`concat`

with some other `Sum`

and always return a `Sum`

.I've used an object factory here instead of our typical prototype ceremony, primarily because

`Sum`

is not *pointed*and we don't want to have to type`new`

. Anyways, here it is in action:Sum(1).concat(Sum(3)) // Sum(4)

Sum(4).concat(Sum(37)) // Sum(41)

Just like that, we can program to an interface, not an implementation. Since this interface comes from group theory it has centuries of literature backing it up. Free docs!

Now, as mentioned,

`Sum`

is not *pointed*, nor a*functor*. As an exercise, go back and check the laws to see why. Okay, I'll just tell you: it can only hold a number, so`map`

does not make sense here as we cannot transform the underlying value to another type. That would be a very limited `map`

indeed!So why is this useful? Well, as with any interface, we can swap out our instance to achieve different results:

const Product = x => ({ x, concat: other => Product(x * other.x) })

const Min = x => ({ x, concat: other => Min(x < other.x ? x : other.x) })

const Max = x => ({ x, concat: other => Max(x > other.x ? x : other.x) })

This isn't limited to numbers, though. Let's see some other types:

const Any = x => ({ x, concat: other => Any(x || other.x) })

const All = x => ({ x, concat: other => All(x && other.x) })

Any(false).concat(Any(true)) // Any(true)

Any(false).concat(Any(false)) // Any(false)

All(false).concat(All(true)) // All(false)

All(true).concat(All(true)) // All(true)

[1,2].concat([3,4]) // [1,2,3,4]

"miracle grow".concat("n") // miracle grown"

Map({day: 'night'}).concat(Map({white: 'nikes'})) // Map({day: 'night', white: 'nikes'})

If you stare at these long enough the pattern will pop out at you like a magic eye poster. It's everywhere. We're merging data structures, combining logic, building strings...it seems one can bludgeon almost any task into this combination based interface.

I've used

`Map`

a few times now. Pardon me if you two weren't properly introduced. `Map`

simply wraps `Object`

so we can embellish it with some extra methods without altering the fabric of the universe.The types we've seen so far which implement the functor interface all implement semigroup one as well. Let's look at

`Identity`

(the artist previously known as Container):Identity.prototype.concat = function(other) {

return new Identity(this.__value.concat(other.__value))

}

Identity.of(Sum(4)).concat(Identity.of(Sum(1))) // Identity(Sum(5))

Identity.of(4).concat(Identity.of(1)) // TypeError: this.__value.concat is not a function

It is a

*semigroup*if and only if its`__value`

is a *semigroup*. Like a butterfingered hang glider, it is one whilst it holds one.Other types have similar behavior:

// combine with error handling

Right(Sum(2)).concat(Right(Sum(3))) // Right(Sum(5))

Right(Sum(2)).concat(Left('some error')) // Left('some error')

// combine async

Task.of([1,2]).concat(Task.of([3,4])) // Task([1,2,3,4])

This gets particularly useful when we stack these semigroups into a cascading combination:

// formValues :: Selector -> IO (Map String String)

// validate :: Map String String -> Either Error (Map String String)

formValues('#signup').map(validate).concat(formValues('#terms').map(validate)) // IO(Right(Map({username: 'andre3000', accepted: true})))

formValues('#signup').map(validate).concat(formValues('#terms').map(validate)) // IO(Left('one must accept our totalitarian agreement'))

serverA.get('/friends').concat(serverB.get('/friends')) // Task([friend1, friend2])

// loadSetting :: String -> Task Error (Maybe (Map String Boolean))

loadSetting('email').concat(loadSetting('general')) // Task(Maybe(Map({backgroundColor: true, autoSave: false})))

In the top example, we've combined an

`IO`

holding an `Either`

holding a `Map`

to validate and merge form values. Next, we've hit a couple of different servers and combined their results in an async way using `Task`

and `Array`

. Lastly, we've stacked `Task`

, `Maybe`

, and `Map`

to load, parse, and merge multiple settings.These can be

`chain`

ed or `ap`

'd, but *semigroups*capture what we'd like to do much more concisely.This extends beyond functors. In fact, it turns out that anything made up entirely of semigroups, is itself, a semigroup: if we can concat the kit, then we can concat the caboodle.

const Analytics = (clicks, path, idleTime) => ({

clicks,

path,

idleTime,

concat: other =>

Analytics(clicks.concat(other.clicks), path.concat(other.path), idleTime.concat(other.idleTime))

})

Analytics(Sum(2), ['/home', '/about'], Right(Max(2000))).concat(Analytics(Sum(1), ['/contact'], Right(Max(1000))))

// Analytics(Sum(3), ['/home', '/about', '/contact'], Right(Max(2000)))

See, everything knows how to combine itself nicely. Turns out, we could do the same thing for free just by using the

`Map`

type:Map({clicks: Sum(2), path: ['/home', '/about'], idleTime: Right(Max(2000))}).concat(Map({clicks: Sum(1), path: ['/contact'], idleTime: Right(Max(1000))}))

// Map({clicks: Sum(3), path: ['/home', '/about', '/contact'], idleTime: Right(Max(2000))})

We can stack and combine as many of these as we'd like. It's simply a matter of adding another tree to the forest, or another flame to the forest fire depending on your codebase.

The default, intuitive behavior is to combine what a type is holding, however, there are cases where we ignore what's inside and combine the containers themselves. Consider a type like

`Stream`

:const submitStream = Stream.fromEvent('click', $('#submit'))

const enterStream = filter(x => x.key === 'Enter', Stream.fromEvent('keydown', $('#myForm')))

submitStream.concat(enterStream).map(submitForm) // Stream()

We can combine event streams by capturing events from both as one new stream. Alternatively, we could have combined them by insisting they hold a semigroup. In fact, there are many possible instances for each type. Consider

`Task`

, we can combine them by choosing the earlier or later of the two. We can always chose the first `Right`

instead of short circuiting on `Left`

which has the effect of ignoring errors. There is an interface called *Alternative*which implements some of these, well, alternative instances, typically focused on choice rather than cascading combination. It is worth looking into if you are in need of such functionality.We were abstracting addition, but like the Babylonians, we lacked the concept of zero (there were zero mentions of it).

Zero acts as

*identity*meaning any element added to`0`

, will return back that very same element. Abstraction-wise, it's helpful to think of `0`

as a kind of neutral or *empty*element. It's important that it act the same way on the left and right side of our binary operation:// identity

1 + 0 = 1

0 + 1 = 1

Let's call this concept

`empty`

and create a new interface with it. Like so many startups, we'll choose a heinously uninformative, yet conveniently googleable name: *Monoid*. The recipe for*Monoid*is to take any*semigroup*and add a special*identity*element. We'll implement that with an`empty`

function on the type itself:Array.empty = () => []

String.empty = () => ""

Sum.empty = () => Sum(0)

Product.empty = () => Product(1)

Min.empty = () => Min(Infinity)

Max.empty = () => Max(-Infinity)

All.empty = () => All(true)

Any.empty = () => Any(false)

When might an empty, identity value prove useful? That's like asking why zero is useful. Like not asking anything at all...

When we have nothing else, who can we count on? Zero. How many bugs do we want? Zero. It's our tolerance for unsafe code. A fresh start. The ultimate price tag. It can annihilate everything in its path or save us in a pinch. A golden life saver and a pit of despair.

Codewise, they correspond to sensible defaults:

const settings = (prefix="", overrides=[], total=0) => ...

const settings = (prefix=String.empty(), overrides=Array.empty(), total=Sum.empty()) => ...

Or to return a useful value when we have nothing else:

sum([]) // 0

They are also the perfect initial value for an accumulator...

It just so happens that

`concat`

and `empty`

fit perfectly in the first two slots of `reduce`

. We can actually `reduce`

an array of *semigroup*'s down by ignoring the*empty*value, but as you can see, that leads to a precarious situation:// concat :: Semigroup s => s -> s -> s

const concat = x => y => x.concat(y)

[Sum(1), Sum(2)].reduce(concat) // Sum(3)

[].reduce(concat) // TypeError: Reduce of empty array with no initial value

Boom goes the dynamite. Like a twisted ankle in a marathon, we have ourselves a runtime exception. JavaScript is more than happy to let us strap pistols to our sneakers before running - it is a conservative sort of language, I suppose, but it stops us dead in our tracks when the array is barren. What could it return anyhow?

`NaN`

, `false`

, `-1`

? If we were to continue on in our program, we'd like a result of the right type. It could return a `Maybe`

to indicate the possibility of failure, but we can do one better.Let's use our curried

`reduce`

function and make a safe version where the `empty`

value is not optional. It shall henceforth be known as `fold`

:// fold :: Monoid m => m -> [m] -> m

const fold = reduce(concat)

The initial

`m`

is our `empty`

value - our neutral, starting point, then we take an array of `m`

's and crush them down to one beautiful diamond like value.fold(Sum.empty(), [Sum(1), Sum(2)]) // Sum(3)

fold(Sum.empty(), []) // Sum(0)

fold(Any.empty(), [Any(false), Any(true)]) // Any(true)

fold(Any.empty(), []) // Any(false)

fold(Either.of(Max.empty()), [Right(Max(3)), Right(Max(21)), Right(Max(11))]) // Right(Max(21))

fold(Either.of(Max.empty()), [Right(Max(3)), Left('error retrieving value'), Right(Max(11))]) // Left('error retrieving value')

fold(IO.of([]), ['.link', 'a'].map($)) // IO([<a>, <button class="link"/>, <a>])

We've provided a manual

`empty`

value for those last two since we can't define one on the type itself. That's totally fine. Typed languages can figure that out by themselves, but we have to pass it in here.There are some

*semigroups*that cannot become*monoids*, that is provide an initial value. Look at`First`

:const First = x => ({ x, concat: other => First(x) })

Map({id: First(123), isPaid: Any(true), points: Sum(13)}).concat(Map({id: First(2242), isPaid: Any(false), points: Sum(1)}))

// Map({id: First(123), isPaid: Any(true), points: Sum(14)})

We'll merge a couple of accounts and keep the

`First`

id. There is no way to define an `empty`

value for it. Doesn't mean it's not useful.The notion of a binary operation is everywhere in abstract algebra. It is, in fact, the primary operation for a

*category*. We cannot, however, model our operation in category theory without an*identity*. This is the reason we start with a semi-group from group theory, then jump to a monoid in category theory once we have*empty*.Monoids form a single object category where the morphism is

`concat`

, `empty`

is the identity, and composition is guaranteed.Functions of type

`a -> a`

, where the domain is in the same set as the codomain, are called *endomorphisms*. We can make a*monoid*called`Endo`

which captures this idea:const Endo = run => ({

run,

concat: other =>

Endo(compose(run, other.run))

})

Endo.empty = () => Endo(identity)

// in action

// thingDownFlipAndReverse :: Endo [String] -> [String]

const thingDownFlipAndReverse = fold(Endo(() => []), [Endo(reverse), Endo(sort), Endo(append('thing down')])

thingDownFlipAndReverse.run(['let me work it', 'is it worth it?'])

// ['thing down', 'let me work it', 'is it worth it?']

Since they are all the same type, we can

`concat`

via `compose`

and the types always line up.You may have noticed that

`join`

is an operation which takes two (nested) monads and squashes them down to one in an associative fashion. It is also a natural transformation or "functor function". As previously stated, we can make a category of functors as objects with natural transformations as morphisms. Now, if we specialize it to *Endofunctors*, that is functors of the same type, then`join`

provides us with a monoid in the category of Endofunctors also known as a Monad. To show the exact formulation in code takes a little finagling which I encourage you to google, but that's the general idea.Even applicative functors have a monoidal formulation known in the category theory as a

*lax monoidal functor*. We can implement the interface as a monoid and recover`ap`

from it:// concat :: f a -> f b -> f [a, b]

// empty :: () -> f ()

// ap :: Functor f => f (a -> b) -> f a -> f b

const ap = compose(map(([f, x]) => f(x)), concat)

So you see, everything is connected, or can be. This profound realization makes

*Monoids*a powerful modelling tool for broad swaths of app architecture to the tiniest pieces of datum. I encourage you to think of*monoids*whenever direct accumulation or combination is part of your application, then once you've got that down, start to stretch the definition to more applications (you'd be surprised how much one can model with a*monoid*).Last modified 2mo ago