Codifying Common structures of Abstract Algebra in Typescript

In several articles now I’ve hinted at the idea of structures within Abstract Algebra and how they have an almost inheritance based relationship. In this article we’ll codify these structures in Typescript.

Magma

The base of Algebraic structures. They are binary operations that preserve Closure (given two As another A is returned). Generically they’d look like (x: A, y: A) => A. It is rare to see Magmas used in code because there aren’t enough constraints around Magmas for them to be very useful by themselves. Said another way, most structures we code against have Closure and some other properties so there are usually better, more specific structures we’ll use.

Semigroup

Semigroups build on Magmas in that they are still binary operations with Closure, but they also add Associativity. An example of Associativity can be seen with (1 + 2) + 3 = 1 + (2 + 3). We can pair the terms however we want as long as we don’t change the order of the terms. Semigroups can be modeled within Typescript and they’re quite useful.

We’ve defined a Semigroup<A> interface and provided two instances of the interface; one for number and another for string. So what can we do with those instances once they’re defined?

We can create a foldSemigroup function that will take a starting A value and an array of A values and will use the append function from whatever Semigroup instance we provide. Notice that in the function signature the A must be the same throughout, so in the first example case the sumSemigroup instance is a Semigroup<number> so the start and as (many a values) parameters must also be numbers or the code will not compile.

In the second case we use an instance of Semigroup<string> so the start and as parameters must be strings.

Monoid

Monoids are a subset of Semigroups in that they’re Semigroups that also have the Identity property. The Identity property is just a special value that can be passed to append that does not change the result. For instance, we can add 0 to any number to return the same number: n + 0 = n = 0 + n. Let’s look at what that looks like in code.

Once again we define a generic interface, but this time we encode the subset concept by defining extends Semigroup<A>. To define an instance for our sumMonoid we’ve already done part of the work with our sumSemigroup, so we use the spread operator to include its definition next to our empty property which is 0 for summing numbers.

Armed with a Monoid instance, we can write a more generic version of fold than what we could write with just a Semigroup instance.

Wow, our Monoid instance satisfies all arguments required by reduce! That means we can now have a type safe way of reusing code that aggregates values which is a huge win. Even cooler is that if we wanted to provide a different starting value for some reason we could still use the foldSemigroup function because our Monoid<A> is a Semigroup<A>.

If you’ve ever used reduce you likely had an implicit Monoid instance defined as a lambda function.

A note about fold

Technically speaking, the implementation of fold I wrote earlier is tragically limited to only work with Arrays. It would be great if we could make that parameter more polymorphic so that we can use our Monoid instances on more than just Arrays.

Here we create a new interface called Foldable which mimics the reduce function already found on the Array prototype. Doing so allows us to rely upon our abstraction rather than forcing callers to use Array. While that may seem orthogonal to our cause of showing algebraic structures, this refactoring means that we can more easily use the codified structures we have which means we can use them in more places!

Further into the fold (catamorphism puns ftw!)

Let’s look at a more real world situation that you’ve likely run into when aggregating things. Let’s say you have an array of people objects and you’d like to know the total age of all of them.

One way we could do that is to create a Monoid instance for our Person type.

Ugh, that’s going to result in a lot of duplicate code, and how do we combine the firstName and lastName properties? Realistically we’ve just redefined our sumMonoid with some additional, leaky property access. Wouldn’t it be nice to be able to reuse our primitive Monoid<number> to sum the ages?

We can write a function called foldMap that takes a Monoid<A> and a function from B to A and a Foldable<B>. We call reduce as we did with fold, but before we append the current value to the accumulator, we apply our mapping function to turn the B into an A ( Person -> number ).

Now we can use our simple Monoid<number> instance to aggregate a property of a more complex object! For bonus points, we can also write fold in terms of foldMap by simply passing the identity function ( x => x ) as the second argument. For those keeping track, I’m pretty sure that’s reusable code reusing reusable code :)

Like what you read? Give Reid Evans a round of applause.

From a quick cheer to a standing ovation, clap to show how much you enjoyed this story.