rkrupinski.com

Unions, intersections, monoids, and capybaras

Capybara

This article constitutes a largely futile endeavour to draw parallels between TypeScript constructs and abstract algebra structures. While it is unlikely to significantly impact anyone's life, a small subset of the population may find it mildly intriguing.

ℹ️ Why capybaras? Well... while it's pretty hard to visualise a monoid, the internet is brimming with capybara pictures.

In the previous article on type-safe routing (make sure to read it first!) there are two rather interesting types:

What makes them particularly noteworthy is their monoid vibe. If you happen to see that too, high five! If you're confused, please read along. It will all become clear shortly. Or at least a bit less blurry.

Let's start with the basics: what is a monoid? Scientifically speaking, it's a semigroup with the concept of an empty value. In simpler terms, it's a value capable of combining with another value of the same type. Additionally, there exists a special variant of it that, when combined with, produces a value identical to the original one; in other words, the operation has no effect. There are also a couple of extra constraints that such a value must satisfy to be considered a monoid:

  • A set of values must exist such that the result of combining any two values from that set is also an element of that set.
  • The order in which values are combined should not affect the result.

How is that useful though? We can imagine someone wanting to merge two values into one, but what's the empty value for? The answer is rather simple: reduction, which is a fancy term for turning a collection into a single value. Let's take numbers, for instance. Smart books say that the set of all natural numbers forms a monoid under addition with the identity element of 0. Wait, what? There's a lot going on here, so let's maybe unpack it:

  • "Under addition" means that the values are combined using the + operator. Considering our set, not all operations will yield a monoid; for example, multiplication is fine, but division is not - fractions are not natural numbers, which violates the monoid constraint.
  • "Identity element of 0" specifies which "empty" value to use. Not every value will yield a monoid; let's try 42. While 1 + 42 is still a natural number, it's no longer 1, which violates the monoid constraint.

All good, but let's now try illustrating that:

const emptyAdd = 0;
 
1 + 2; // 3
(1 + 2) + 3 === 1 + (2 + 3); // true
1 + emptyAdd; // 1
[1, 2, 3].reduce((acc, curr) => acc + curr, emptyAdd); // 6
 
const emptyMul = 1;
 
2 * 3; // 6
(1 * 2) * 3 === 1 * (2 * 3); // true
2 * emptyMul; // 2;
[1, 2, 3].reduce((acc, curr) => acc * curr, emptyMul); // 6

View source

What's important here is that none of the code blocks above would describe a monoid if we were to:

  • Change the operators (e.g., to subtraction or division).
  • Change the empty values. There's only a single value that makes sense as the beginning of an addition sequence (0), and there's only a single value that makes sense as the beginning of a multiplication sequence (1).

Okay, so far we've covered some definitions and elementary school-level math; now what? Let's take our considerations to the type system level. For starters - TypeScript, out of the box, is incapable of arithmetic operations, hence instead of + and * we'll use union (|) and intersection (&) operators.

type EmptyUnion = never;
 
type T1 = 1 | 2; // 1 | 2
type T2 = Equals<(1 | 2) | 3, 1 | (2 | 3)>; // true
type T3 = 1 | EmptyUnion; // 1
 
type EmptyIntersection = unknown;
 
type T4 = { 1: true; } & { 2: true; }; // { 1: true; } & { 2: true; }
type T5 = Equals<({ 1: true; } & { 2: true; }) & { 3: true; }, { 1: true; } & ({ 2: true; } & { 3: true; })>; // true
type T6 = { 1: true; } & EmptyIntersection; // { 1: true; }

View source

There's a slight modification we had to make. Due to the way the intersection operator works (intersecting 1 and 2 doesn't make sense), we're using records with a single property corresponding to the numerical value.

Similarly to + & 0 and * & 1 (as long as natural numbers are concerned), their type system counterparts, | & never and & & unknown, form a monoid. There's one subtle difference, though: never & unknown are not limited to any particular type, thus they can be considered "universal empty values".

Now, to the point. The claim at the very beginning was that if one really squints, they can see a monoid in the two aforementioned types. Armed in all the necessary theory, and the examples above, we can now verify that.

type Paths<TRoute, TPath extends string = ""> = TRoute extends [
  infer THead,
  ...infer TTail,
]
  ? Paths<THead, TPath> | Paths<TTail, TPath>
  : TRoute extends NonIndexRouteObject
  ? PathJoin<
      TPath,
      TRoute["path"] extends string ? TRoute["path"] : ""
    > extends infer P extends string
    ? Paths<TRoute["children"], P> | P
    : never
  : TRoute extends IndexRouteObject
  ? TPath
  : never;

Note the highlighted lines. Indeed, the result of type Paths (a string) kinda forms a monoid under union (|) with the empty value of never.

type PathFns<TRoute, TPath extends string = ''> = TRoute extends [
  infer THead,
  ...rest: infer TTail,
]
  ? PathFns<THead, TPath> & PathFns<TTail, TPath>
  : TRoute extends NonIndexRouteObject
  ? PathJoin<
      TPath,
      TRoute['path'] extends string ? TRoute['path'] : ''
    > extends infer P extends string
    ? PathFns<TRoute['children'], P> & PathFnFor<TRoute['slug'], P>
    : never
  : TRoute extends IndexRouteObject
  ? PathFnFor<TRoute['slug'], TPath>
  : unknown;

Similarly, the result of type PathFns (a Record<S, PathFn<P>>) kinda forms a monoid under intersection (&) with the empty value of unknown.

Thanks to that, we were able to combine the values together as we traversed the route graph, resulting in types containing all the information collected along the way.

Capybaras!

Read more:

Photo by Tioni Oliv on Unsplash.