Codes & Waffles

Day 71: on Algebras, part 3

Published 25 Apr 2018

This post is part 3 of a series on Algebras in Software Development. Here are part 1 and part 2

The last time we defined a Monoid as a

Binary associative operation with an identity.

And if something about that sentence still looks weird, then maybe this post can clear it up.

We also constructed a Monoid in Javascript that looks like this:

// Addition :: a -> Addition a
const Addition = x => ({
  take: () => x,
  mappend: y => Addition(x + y.take()),
  inspect: () => `Addition(${x})`,
  toString: () => `Addition(${x})`

By its name, we can assume that it will work with numbers, and we would be right. Addition will work when the x we pass as argument is a number. But, at least in Javascript, it will also work when we pass a string. This is because, + is both the operation sign for addition and string concatenation in JS. If that sounds weird, it’s because it is. But that’s the JS we love, so let’s move on accepting the fact that both number addition and string concatenation can share a Monoid implementation in JS. Now, let’s look at a different one.

In part 1 of this series, we looked at how List concatenation also fulfils the laws of Associativity and Identity. We define Array concatenation in Javascript, as adding the elements inside one array to the end of the other one. That way, the concatenation of [1, 2, 3] and [4, 5, 6] would be [1, 2, 3, 4, 5, 6]. Here’s what that Monoid could look like in Javascript:

// ListConcat :: [a] -> ListConcat [a]
const ListConcat = x => ({
  take: () => x,
  mappend: y => ListConcat(x.concat(y.take())),
  inspect: () => `ListConcat(${x})`,
  toString: () => `ListConcat(${x})`

const listConcatEmpty = ListConcat([]);

You can see how inside of mappend we have to use JS array’s concat function, just as we used the + sign for addition and/or string concatenation. Proving that the laws hold for this Monoid implementation as well is left out as an exercise for the reader ✨.

But the concept behind mappend isn’t really about joining, or adding something up. It’s really about transforming 2 somethings into just one something. In the case of addition, we take 2 numbers and turn them into 1 number by summing the up. On arrays, we turn 2 arrays into 1 by joining them.

Here’s an example of a Monoid that shows that a bit better than the ones we’ve used so far:

// Any :: a -> Any a
const Any = x => ({
  take: () => x,
  mappend: y => x || y.take(),
  inspect: () => `Any(${x})`,
  toString: () => `Any(${x})`

const anyEmpty = Any(false);

Can you guess what this one does just by looking at it? It takes two Boolean values and turns them into one by looking if any of them is truthy. As you can see, we’re not summing or joining anything really, we’re using logical laws to define how two boolean values should be appended to one another. Here’s one that looks very much like it:

// All :: a -> All a
const All = x => ({
  take: () => x,
  mappend: y => x && y.take(),
  inspect: () => `All(${x})`,
  toString: () => `All(${x})`

const allEmpty = All(true);

This one will turn the 2 boolean values into one by looking if all of them are truthy or not.

There’s one last thing I’d like to talk about in the Monoid world before moving on to something else.

Many to One

In Haskell, the Monoid typeclass defines one more function. That function is mconcat and it takes a list of Monoids and turns them into one of the same type. It also needs to fulfil a law of sorts, which looks like:

mconcat = foldr mappend mempty

And here’s how we could create our own mconcat function in Javascript:

// mconcat :: a -> [a] -> a
const mconcat = mempty 
				=> xs 
				=> xs.reduce((acc, cur) => acc.mappend(cur), mempty);

There’s a lot going on there, so let’s unpack it a bit.

  • It’s a curried function. That’s because then it will be easier to create instances of mconcat for each of our Monoid types by partially applying our different mempty values to it.
  • It’s using the fact that Lists in JS are Arrays, and Arrays in Javascript have a reduce function that serves the same purpose as Haskell’s foldr.
  • Inside of the reducing function, it’s using the fact that any Monoid will have a mappend function to join them together, and using the mempty value as initial value to start the operation.

It’s a bit of a hassle to have to write that much code in JS for something that looks so clean in Haskell, isn’t it? But anyway, here’s how we could use it:

// Partial application of the empty value for the Any Monoid
const anyConcat = mconcat(Any(false));

const reducedListOfAnys = anyConcat([Any(false), Any(false), Any(true)]) // Any(true). 

With this, we now know how to reduce 2 Monoids into 1, and how to reduce a list of n Monoids into 1 as well. And, if there was a way to know for sure that the code we’re working with fulfils the 2 laws that Monoids have, then we could arbitrarily use this functions all around, while being confident in the results. Unfortunately, Javascript can’t do that by itself. There are some attempts at it, by using projects like Purescript or Elm. It’s still really fun to play around with it though 🙌.

Haskell on the other hand is built from the ground up to fulfil these kind of structures, which is what makes it so awesome, even if a bit complicated at first. That being said, I don’t believe Javascript and the web really need this, and I actually believe that the web is what it is today exactly because of what it lacks. Wether that’s good or bad is not my responsibility to judge.


Personal Blog of Daniel Bolívar
Writer of Codes for the Webs