Domain Modeling with Abstract Algebra

Reid Evans
Jun 21, 2018 · 5 min read
Photo by Darren Bockman on Unsplash

In this post, we’ll look at several problem domains and see how we can model them with Abstract Algebra. While we’ll look at a few specific domains, the intent is to help you form an intuition for applying this approach to any problem domain.

Properties

Modeling with Abstract Algebra is all about finding the properties that our domain holds. In this case I’m using the term “properties” the same way someone talking about “Property Based Testing” is. The idea being that our specific values don’t matter as much as the properties that arise when viewing inputs and outputs to our domain at a more abstract level. Let’s take a quick look at some properties that will help us (this is by no means an exhaustive list).

Closure — Given two elements of the same type, we combine them to produce another element of the same type.

Associativity — We can place parenthesis anywhere we’d like in a sequence of combinations

Identity — There is a special value we can apply that has no affect on the outcome

Commutativity — The order of the elements doesn’t matter

Idempotence — Receiving the same message multiple times has no affect after the first time

Now that you’ve seen some properties, let’s look at a few different problem domains and determine whether the domains uphold any or all of these properties.


Ordering

Let’s say that our domain is “the domain of ordering things”. What sort of properties does this domain uphold?

Is it Closed?

We can easily say that if we combine a ordering with a ordering that we receive a ordering so the domain of Ordering is closed.

Is it Associative?

If we had 3 orderings and didn’t change their order, could we add parenthesis wherever we wanted?

Sure, is the same as so the domain of Ordering is Associative.

Does it have an Identity element?

This one requires we define a bit. In my previous post on creating composable sorting hierarchies we defined sorting in terms of a function that takes two elements and returns EQ, LT, or GT . If we take that version of sorting then we can indeed specify an identity element of the form . In that case we always say that the two elements are equal which has the result of not adjusting the sorting.

Is sorting Idempotent?

Sure! we can sort by the same thing as many times as we want without adjusting the order of the items. is the same thing as as far as the end result is concerned.

Is sorting Commutative?

No, and that’s a good thing. We wouldn’t want to be the same thing as because we would severely limit what we were able to express in this domain.

So what have we learned?

Because Ordering is Closed, Associative, and has an Identity element it’s a Monoid. Because it is also Idempotent we can say that it’s an Idempotent Monoid.

Perhaps more importantly, it means that there are coding concerns that are merely optimizations! While the code will run a bit longer if we sort by the same thing multiple times, we’ll still get the correct answer.


CSS Classes

What can we say about the domain of CSS classes? Which properties does this domain uphold?

Is it Closed?

Sure, because for any two class names we can combine them

Is it Associative?

Sure, we can place parenthesis anywhere within a series of combinations. is the same thing as

Does it have an Identity?

Sure, we can say that the empty string is the identity because it has no affect when added to either side of an existing class name.

Is it Idempotent?

At first glance it appears that it isn’t because and we would expect an idempotent operation to look more like . But if we look further we’ll see that the domain actually makes no distinction as to how many times the same class is applied to an element, only whether the element has the class.

If a style rule targets it will apply equally to as it will to . In my mind that’s Idempotent.

Is it Commutative?

Can we change the order of elements in a sequence of combinations?

As we saw with the idempotent example, the thing we’re interested in is what external result happens, and style rules do not target the order of class names so .

So what sort of structure is this?

Because it’s Closed, Associative, Commutative, and Idempotent it’s a Semilattice. Because it has an identity it’s a Bounded Semilattice.

It turns out the Semilattice is a really powerful structure for distributed computing as well. Because it’s commutative the order we receive messages doesn’t matter, and because it’s Idempotent we can receive the same message multiple times without affecting the output!

Summary

When modeling a domain with Abstract Algebra, start by asking yourself which properties the domain upholds. In both examples we saw there were several situations where we might have written code to account for a situation that was merely an optimization rather than a necessity.

If you’re working in a language like Haskell or Purescript that already has functions built to use these abstractions, then defining instances of the Algebraic structures for your type means you get additional functionality for free.

If you’re working in a language like Typescript, it turns out that you can write your own functions with very little code. You can also just profit from knowing what things you absolutely must handle in your code and which things are merely optimizations.

Reid Evans

Written by

Functional programmer, conference speaker, cofounder of Functional Knox Inc, senior consultant with ResultStack. @ReidNEvans