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.
The base of Algebraic structures. They are binary operations that preserve Closure (given two
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.
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
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
as parameters must be
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
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
Ugh, that’s going to result in a lot of duplicate code, and how do we combine the
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
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 :)