Domain Modeling with Abstract Algebra
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. 1 + 2 = 3 "hello " + "world" = "hello world"
Associativity — We can place parenthesis anywhere we’d like in a sequence of combinations (1 + 2) + 3 = 1 + (2 + 3) ("a" + "b") + "c" = "a" + ("b" + "c")
Identity — There is a special value we can apply that has no affect on the outcome 0 + n = n = n + 0
Commutativity — The order of the elements doesn’t matter 1 + 2 = 2 + 1
Idempotence — Receiving the same message multiple times has no affect after the first time Math.max(1, 2) = Math.max(Math.max(1, 2), 2)
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 lastName ordering with a firstName ordering that we receive a lastName then firstName 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, (lastName then firstName) then age is the same as lastName then (firstName then age) 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 a -> a -> EQ | LT | GT. If we take that version of sorting then we can indeed specify an identity element of the form const noSort = (x: A, y: A) => EQ. 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. lastName then lastName is the same thing as lastName as far as the end result is concerned.
Is sorting Commutative?
No, and that’s a good thing. We wouldn’t want lastName then firstName to be the same thing as firstName then lastName 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 btn + btn-primary = btn btn-primary
Is it Associative?
Sure, we can place parenthesis anywhere within a series of combinations.(btn + btn-primary) + btn-large is the same thing as btn + (btn-primary + btn-large)
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. "" + selector = selector = selector + ""
Is it Idempotent?
At first glance it appears that it isn’t because btn + btn = "btn btn" and we would expect an idempotent operation to look more like btn + btn = btn. 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 .btn it will apply equally to <button class="btn" /> as it will to <button class="btn btn" />. 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 btn + btn-primary = btn-primary + btn.
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.