# Fantas, Eel, and Specification 5: Monoid

Good Tuesday, Fantasists! This week, we’re going to take a quick(!) look at the semigroup’s older sibling: the monoid. We saw last week that a `Semigroup` type is one that has some concept of combining values (via `concat`). Well, a `Monoid` type is any `Semigroup` type that happens to have a special value - we’ll call it an identity value - stored on the type as a function called `empty`.

Here’s its (in my opinion, not-too-helpful) signature:

``````empty :: Monoid m => () -> m
``````

Far more useful, I think, are the laws for how `empty` must act for a type to be a valid `Monoid`. We call these the identity laws:

``````// Right identity
MyType(x).concat(MyType.empty()) === MyType(x)

// Guess what this one's called?
MyType.empty().concat(MyType(x)) === MyType(x)
``````

Whichever side of `concat` we put our `empty`, it must make no difference to the value. Let’s look at some examples of `empty` values for our favourite semigroups. Try them on the laws above if you’re unsure of why they’re valid `empty` values:

``````// ''.concat('hello')
//   === 'hello'.concat('')
//   === 'hello'
String.empty  = () => ''

// [].concat([1, 2, 3])
//   === [1, 2, 3].concat([])
//   === [1, 2, 3]
Array.empty   = () => []

// And so on...
Sum.empty     = () => Sum(0)
Product.empty = () => Product(1)
Max.empty     = () => Max(-Infinity)
Min.empty     = () => Min(Infinity)
All.empty     = () => All(true)
Any.empty     = () => Any(false)

// BUT not every semigroup is a monoid...
First.empty = () => // ???
Last.empty  = () => // ???
``````

Eek, got a bit stuck at the end… `First` and `Last` are not monoids; see if you can work out why!

Ok, so, `First` and `Last` actually are monoids in Haskell. This cheat is done by sneaking in an inner `Maybe` type, where `Nothing` becomes the `empty` value. This actually works for any semigroup that you want to turn into a monoid, but don’t let Connor McBride catch you doing it…

This is all very interesting, but what’s the point? I’m glad you asked, imaginary reader! With a `Semigroup` type, you can combine one or more values to make another, right? All a monoid does is let us upgrade that to zero or more. This is actually a Pretty Big Deal™, as we can take any array (including an empty array!) of monoids and `reduce` them to one value.

… Wait, what?

As a surprisingly good intuition, monoids encapsulate the logic of `Array.reduce`. That’s what they do. That’s what they’re for. That’s it right there. If you know how to reduce lists, then congratulations, you’re now a monoid warrior:

``````// A friendly neighbourhood monoid fold.
// fold :: Monoid m => (a -> m) -> [a] -> m
const fold = M => xs => xs.reduce(
(acc, x) => acc.concat(M(x)),
M.empty())

// We can now use our monoids for (almost) all
// our array reduction needs!
fold(Sum)([1, 2, 3, 4, 5]).val // 15
fold(Product)([1, 2, 3]).val   // 6
fold(Max)([9, 7, 11]).val      // 11
fold(Sum)([]).val              // 0 - ooer!
``````

We actually get a double win here. Not only do we now have a generic way to `fold` any reducible structure (arrays, trees, etc) in our app with any `Monoid` type (`Sum`, `Max`, etc), we also have an opportunity to do some really cool optimisations:

The thing that we didn’t explicitly mention about the semigroup laws is that associativity gives us an opportunity to parallelise. If we split a list of semigroups into chunks, `concat` the elements of each chunk in parallel, and then `concat` the results, we’re guaranteed to get the same result!

``````// In practice, you'd want a generator here...
// Non-tail-recursion is expensive in JS!
const chunk = xs => xs.length < 5000
? [xs] : [ xs.slice(0, 5000)
, ... chunk(xs.slice(5000)) ]

// ... You get the idea.
const parallelMap = f => xs => xs.map(x =>

// Chunk, fold in parallel, fold the result.
// In practice, this would probably be async.
const foldP = M => xs =>
parallelMap(fold(M))(chunk(xs))
.reduce(
(xs, ys) => xs.concat(ys),
M.empty())

// With all that in place...

// Numbers from 0 to 999,999...
const bigList = [... Array(1e6)].map((_, i) => i)

// ... Ta-da! 499999500000
// Parallel-ready map/reduce; isn't it *neat*?
foldP(Sum)(bigList).val
``````

Thanks, associativity! By being certain that the `Semigroup` and `Monoid` laws hold for our type, we can write functions to optimise for different data sets, and other developers can use our API with no idea of the wizardry underneath!

So, monoids let us write easily-optimised and expressive `reduce` operations. Pretty neat, huh? There is a tiny downside, though…

The fiddly part about monoids in JavaScript is that we have to pass in type representations (what we called `M`). The Fantasy Land spec puts these in signatures as `TypeRep` values, in case you’ve wondered what they were. These have to be here because JavaScript, unlike other languages, can’t deduce the type we’re working with, so we have to give it a friendly nudge. For example:

``````// How do we know which `empty` we want? In
// Haskell, the correct `empty` would be used
// because the type would be checked to find the
// right monoid instance in the context.
const concatAll = xs => xs.reduce(concat, empty)

// In JS, the TypeRep avoids this issue.
const concatAll_ = M => xs =>
xs.reduce(concat, M.empty())
``````

This becomes more apparent when we get onto composed monoids. Just as we saw with semigroups, let’s imagine we want to make `Pair` a monoid:

``````const Pair = daggy.tagged('Pair', ['a', 'b'])

Pair.empty = () => // ???
``````

Remember: the `empty` value must work for all cases, and a Pair could be made of any of our monoids. The solution? Pass in the `TypeRep`s:

``````// We now have a kind of "Pair factory"!
// Pair_ :: (Monoid a, Monoid b) =>
//   (TypeRep a, TypeRep b) -> (a, b) -> Pair a b
const Pair_ = (typeA, typeB) => {
const Pair = daggy.tagged('Pair', ['a', 'b'])

Pair.empty = () => Pair(typeA.empty(),
typeB.empty())

// You could write `concat` here and include
// some type-checking in its logic!

return Pair
}

// We can partially apply to get Pair
// constructors for specific types...
const MyPair = Pair_(Sum, Any)

// ... and these have valid empty() values!
// Pair(Sum(0), Any(False))
MyPair.empty()

// We can also call it directly.
// Pair(All(True), Max(-Infinity))
Pair_(All, Max).empty()
``````

Some extra ugly boilerplate, but we do end up with the same result. We’re going to see a lot more of these `TypeRep` values floating about, and it is unfortunate. Still, if you want to write type-safe JavaScript without all this hassle, check out PureScript!

There are loads of weird and wonderful monoids that we haven’t covered. For example, an `a -> b` function is a monoid if `b` is a monoid:

``````// concat :: (Semigroup b) =>
//   (a -> b) ~> (a -> b) -> (a -> b)
Function.prototype.concat = function (that) {
return x => this(x).concat(that(x))
}

// Are you fed up of TypeReps yet? If you _did_
// want to implement this, you're probably better
// off setting it manually for the functions you
// are likely to concat... Sigh.
Function.prototype.empty = // result.empty()
``````

Effectively, we just concatenate the results of calling both functions with a given argument. If this seems useless, check out Hardy Jones’ post on implementing FizzBuzz with monoids! They are really clever structures that, with a bit of imagination, can be spotted everywhere in the wild. We’ll actually come back to them time and time again in the articles to come, so get used to them!

Again, this post only touches the surface of what monoids can do, and I’m surprised by new examples all the time. Keep researching, keep looking for examples, see whether you could replace some of your code’s `Array.reduce` calls with monoid folds, and start to build up a library of reusable `Monoid` types to encapsulate your logic. Exciting times!

Next time, we’ll look at `Functor` - our first step on the road to the magical `Monad`. Until then, Fantasists,

Take care ♥