Hidden Algebraic Structures in Everyday Imperative Code

Photo by Stefan Steinbauer on Unsplash

Throughout my time as a software developer one of the things I’ve developed is the ability to identify and find an increasing amount of patterns. Some patterns are obvious while others have taken me years to stumble upon and then identify. In this article I’ll start with some imperative code and we’ll tease out a very common pattern.

As you can probably tell, this code finds the total age of all Persons in the people array. It makes use of a mutable variable totalAge and a for..of loop to achieve the effect. Chances are you’ve seen or even written code just like it. It’s the way I did this sort of calculation for the better part of a decade.

A few years ago I started learning about functional programming. I realized that the intent of the code is easily lost in even slightly more involved imperative loop. Fortunately there are an abundance of libraries for dealing with arrays in a functional way, and a common approach is known as map reduce.

In this case we first transform our array of Person objects into an array of numbers with our call to map. We then turn our Array<number> into a number by providing a way to combine two numbers p + c and a starting point 0.

Once you understand what map does it’s easy to see that the only property we care about is the age property. And once you understand what reduce does it’s pretty easy to see that we’re just summing all the numbers.

This approach worked really well for me for a few years. It was easier to determine what was happening at a glance and I wasn’t using mutable variables anymore. But there are a few problems with this code:

1. I can’t tell you how many times I’ve written the .reduce((p: number, c: number) => p + c, 0) line.
2. We’re looping through that array twice. Once for the map and again for the reduce.

One of the characteristics of a pattern is that it is something that is repeatable. Because I had written that reduce line so many times I knew there had to be a pattern. Let’s look at how we can solve the first problem…

It turns out that almost every time you write a reduce you have implicitly defined a pattern known as a Monoid. Let me show you:

See, a Monoid is something that has an empty value and a way to combine 2 things into 1. Notice how the properties of the interface align perfectly with the arguments to reduce.

Once we have the interface defined we can provide an instance of the interface.

And now that we can talk about what it means to combine numbers with a single type we can write a new function to take advantage of our new abstraction. The way I like to think of the following function is that the M: Monoid<A> argument is proof that we can combine A[] values into a single A.

Fantastic, so the issue of writing the same reduce over and over has been solved by the Monoid pattern, but our original example still has the issue of double iteration because sum knows how to deal with numbers and to get from Person[] to number[] we have to call map.

Fortunately this pattern of map reduce has another common extension to the fold function called foldMap which we can implement like so.

In this case we have proof that we can combine multiple A values into a single A because we have a Monoid<A>, but we have an array of B values. Because we only know how to combine A values we also force the caller to provide a bToA function that will convert a B into an A.

While that may sound and look complicated, there’s only one way to make those types align, and that’s to run the bToA function on each B before performing the append function which knows how to combine two A values into a single A.

Also you can see that once we have foldMap defined we can rewrite fold in terms of foldMap by simply providing the x => x (identity) function.

The final result now means that we can aggregate numbers on any structure while only iterating through the array once. It also means we no longer have to copy and paste our call to reduce across our codebase.