(Mostly) Useless Lessons From Doing Math With TypeScript Types

Throughout my experience using TypeScript, I have constantly been finding new features in the type system that I had no idea existed. At some point, I discovered that the type system was turing complete! (If we ignore the infinite memory requirement)

Many interesting projects have been made in the TypeScript type system, such as a SQL database and an assembly interpreter.

Knowing the power of the type system and that people have made far more complex things in the past, I decided to delve into the humble task of creating types for simple calculations in TypeScript.

Can’t be too hard, right?

Without further ado, here are my findings:

Encoding numbers

To do calculations in the TypeScript type system, we must first define how we represent numbers. Our first instinct may be to use the built-in number literal types, where numbers are represented as follows:

type MyValue = 5;

This representation is undoubtedly simple, not to mention readable. However, it complicates further calculations as TypeScript doesn’t support many operations on these numbers (Pretty much only equality). Instead, we may consider another option: the humble tuple. To encode a natural number¹, we can use a tuple of length n ≥ 0 where n is the number we wish to represent.

While unintuitive, using a tuple based representation unlocks more operations such as tuple destructuring, concatenation and property access that are not available on number literals. This will make it easier to implement our math operations.

Under this representation, we can represent the number zero as an empty tuple:

type Zero = [];

The following numbers as tuples of length n:

type One = [unknown];
type Two = [unknown, unknown];
type Three = [unknown, unknown, unknown];

Now that we have a representation for natural numbers, we can create a base type for these numbers. Remember that in our system, types and values are indistinguishable, so by convention in this article, we can use the letter T as a postfix to type definitions that are data types as opposed to values.

In this case, we know that all numbers extend an array of unknown types, so we can call this type NaturalT.

type NaturalT = unknown[];

Conversion Operations

Before doing math with this representation, it is helpful to create helpers to convert back and forth between our tuple representation and TypeScript number literals.

First and most simply, we can convert our tuple representation by getting the type of the length property for that tuple:

type ToNumber<T extends NaturalT> = T["length"];

type ThreeToNumberResult = ToNumber<Three>;
// type ThreeToNumberResult = 3

Converting TypeScript numbers to the tuple representation is a bit more complicated as we must use recursive types to generate the correct tuple.

The basic algorithm is to start with an empty tuple (zero) and add one to our value until its length equals our target number, after which we return it.

Since no mutable variables exist in the TypeScript type system, we must write our algorithm in a functional programming style, using tail recursion² to emulate mutability. We can do pattern matching using conditional types to check if the length of our array is equal to our target number, then return an accumulated value created by prepending to the original tuple.

Here, we use the type parameter N to represent our target number, and Res is our accumulator, which starts at zero. We can then check if Res represents our target number using the predicate Res["length"] extends N. We can add one to our result number by concatenating it using the spread operator: [unknown, ...Res].

Put together, our completed type looks like this:

type ToNatural<N extends number, Res extends NaturalT = Zero> =
  Res["length"] extends N ? Res
  : ToNatural<N, [unknown, ...Res]>;

type FiveToNaturalResult = ToNatural<5>;
// type FiveToNaturalResult = [unknown, unknown, unknown, unknown, unknown]

With that, we have a basic way of representing natural numbers and converting between that representation and a more human-readable number literal. Up next, we should implement some operators to start doing useful computations!

Addition

Now begins the part where I convince you it was a good idea to use this odd tuple encoding to represent numbers.

The easiest operation to start with is the addition operation, which we can achieve simply by concatenating the two tuple inputs:

type Add<A extends NaturalT, B extends NaturalT> = [...A, ...B];

type AddFiveAndEightResult = ToNumber<Add<ToNatural<5>, ToNatural<8>>>;
// type AddFiveAndEightResult = 13

Subtraction

After addition comes subtraction. We can implement a type to subtract one from a number by employing more conditional types using pattern matching with inferred types.

If we assert that a number extends [unknown, ...SomeType], we know that SomeType must be a natural number as well, and it will be the result of subtracting one from that number (e.g. [unknown] extends [unknown, ...[]]). If the given number is zero, the subtraction operation fails, as 0 − 1 results in a negative number, which we cannot represent in our current system. In that case, we can return the never type to represent a failed operation.

Here is how we implement our subtract one operation:

type Sub1<A extends NaturalT> =
  A extends [unknown, ...infer APrime] ? APrime : never;

type Sub1FromFiveResult = ToNumber<Sub1<ToNatural<5>>>;
// type Sub1FromFiveResult = 4

type Sub1FromZeroResult = Sub1<Zero>;
// type Sub1FromZeroResult = never

To expand this into a generic subtraction operation, we can employ the right-hand side of our operation in the pattern matching. If we call our right-hand side B, we can match on the pattern [...B, ...infer APrime]. For example, if B is [unknown, unknown], the pattern becomes [unknown, unknown, ...infer APrime] and results in subtracting two from A

Here is the process implemented:

type Sub<A extends NaturalT, B extends NaturalT> =
  A extends [...B, ...infer APrime] ? APrime : never;

type SubFiveFromEightResult = ToNumber<Sub<ToNatural<8>, ToNatural<5>>>;
// type SubFiveFromEightResult = 3

type SubTenFromEightResult = ToNumber<Sub<ToNatural<8>, ToNatural<10>>>;
// type SubTenFromEightResult = never

Multiplication

Now, the next operation is the multiplication operation. We already have an addition operation, and what is multiplication but a series of addition operations!

We can implement that process again using tail recursion, terminating when the left-hand value is zero, and subtracting one from it each time:

type Mul<A extends NaturalT, B extends NaturalT, Acc extends NaturalT = Zero> =
  A extends [unknown, ...infer A] ? Mul<A, B, Add<Acc, B>>
  : Acc;

Comparison

Before implementing division, the final of the four basic arithmetic operations, we must take a tangent to implement basic comparison operations.

We will start by defining a boolean representation, which will simply be the built-in boolean literal types! Our representation will then represent true with true, and false with false.

Next we can implement an operation that returns true if and only if the left-hand side is less than or equal to the right-hand side.

Using A to represent the left-hand side and B to represent the right-hand side, the algorithm for computing less than or equal to is as follows:

While both A and B are non-zero, subtract one from both of them. If B is zero, then A must be greater than B, so return false. Otherwise, return true

We can implement that algorithm recursively as follows:

type Leq<A extends NaturalT, B extends NaturalT> =
  [A, B] extends [[unknown, ...infer A], [unknown, ...infer B]]
    ? Leq<A, B>
  : [A, B] extends [[unknown, ...NaturalT], []]
    ? false
  : true;

Now that we have the less than or equal to operator, the other operators are simple enough to implement:

type Not<A extends boolean> = A extends true ? false : true;

type Geq<A extends NaturalT, B extends NaturalT> = Leq<B, A>;
type Lt<A extends NaturalT, B extends NaturalT> = Not<Geq<A, B>>;
type Gt<A extends NaturalT, B extends NaturalT> = Not<Leq<A, B>>;

Division

Now that we have some basic comparison operations, we can implement division.

One simple algorithm is to subtract the denominator from the numerator until the numerator is less than the denominator, keeping track of the number of times we subtracted. This result becomes our quotient, and the remainder will be stored in the numerator.

quotient = 0;
while (denominator <= numerator) {
  numerator -= denominator;
  quotient += 1;
}

Using N as the numerator, D as the denominator, and Q as the quotient, we can implement this algorithm for both division and remainder as follows:

type Div<N extends NaturalT, D extends NaturalT, Q extends NaturalT = Zero> =
  Leq<D, N> extends true ? Div<Sub<N, D>, D, Add<Q, One>>
  : Q;

type Rem<N extends NaturalT, D extends NaturalT, Q extends NaturalT = Zero> =
  Leq<D, N> extends true ? Rem<Sub<N, D>, D, Add<Q, One>>
  : N;

type DivTenByTwoResult = ToNumber<Div<ToNatural<10>, ToNatural<2>>>;
// type DivTenByTwoResult = 5
type RemTenByTwoResult = ToNumber<Rem<ToNatural<10>, ToNatural<2>>>;
// type RemTenByTwoResult = 0

type DivFiveByTwoResult = ToNumber<Div<ToNatural<5>, ToNatural<2>>>;
// type DivFiveByTwoResult = 2
type RemFiveByTwoResult = ToNumber<Rem<ToNatural<5>, ToNatural<2>>>;
// type RemFiveByTwoResult = 1

Generating the fibonacci sequence

Now for the obligatory fibonacci sequence generator.

For this implementation, we will generate a tuple of n fibonacci numbers using our number representation.

For this we will use a recursive algorithm, starting with a base case of [1, 1], then adding our next number by taking the sum of the previous two values in our sequence.

Here is the algorithm in JavaScript:

 let res = [1, 1];
 while (n > 2) {
   res = [res[0] + res[1], ...res]
   n -= 1
 }

Now, we can implement that same algorithm using tail recursion:

type Fib<N extends NaturalT, Res extends NaturalT[] = [One, One]> =
  Gt<N, Two> extends true ? Fib<Sub1<N>, [Add<Res[0], Res[1]>, ...Res]>
  : Res;

type FibRawResult = Fib<ToNatural<4>>;
// type FibRawResult = [[unknown, unknown, unknown], [unknown, unknown], One, One]

However, we now have an array of our hard to read tuple representation, and it’s reversed on top of that! But do not fear! With the power of types, we can map the result of this type to a reversed list of numbers:

type FormatFibResult<Ns extends NaturalT[], Res extends number[] = []> =
  Ns extends [infer V extends NaturalT, ...infer NsPrime extends NaturalT[]]
    ? FormatFibResult<NsPrime, [ToNumber<V>, ...Res]>
  : Res;

type FibResult = FormatFibResult<Fib<ToNatural<20>>>;
// type FibResult = [1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765]

Now, you may wonder: what happens if we try to get a sequence of length 21? Well, we then hit our first limitation of our tuple representation:

error TS2799: Type produces a tuple type that is too large to represent.

    type FibResult = FormatFibResult<Fib<ToNatural<21>>>;
                                     ~~~~~~~~~~~~~~~~~~

As it turns out, there is a hard limit on the size of tuple types: TypeScript doesn’t allow tuples of size 10,000 or greater. On top of that, there is a tail recursion depth limit of 1,000, so operations such as Mul or Div will fail on numbers over 999.³

Conclusions

Now, the question you may have been asking this whole time: Is this useful?

…no

But also, yes! While it isn’t particularly useful to do arithmetic using types, understanding of how to use types in TypeScript can help create well-typed code with complex and dynamic behavior.

Many well known TypeScript libraries make extensive use of conditional types, pattern matching, among other advanced TypeScript features for example:

• Prisma, a type safe TypeScript ORM
• Kysely, a query builder that uses string literal types to check queries at compile-time
• The type definitions for Lodash
• Tye type definitions for the JavaScript standard library

One final thing to remember is that with great power comes great responsibility. We should always careful not to let ourselves get out of hand and create unreadable code for no good reason.

With that said, here are the operations for integers and rational numbers:

Integers

type IntegerT = [boolean, NaturalT];

type INegTwo = [true, Two];
type INegOne = [true, One];
type IZero = [false, Zero];
type IOne = [false, One];
type ITwo = [false, Two];

type IToString<A extends IntegerT> = A[0] extends true
  ? `-${ToNumber<A[1]>}`
  : `${ToNumber<A[1]>}`

type ToInteger<A extends string> =
  A extends `-${infer X extends number}` ? [true, ToNatural<X>]
  : A extends `${infer X extends number}` ? [false, ToNatural<X>]
  : never;

type INeg<A extends IntegerT> = [Not<A[0]>, A[1]];


type IAdd<A extends IntegerT, B extends IntegerT> =
  A[0] extends B[0]
    ? [A[0], Add<A[1], B[1]>]
  : Leq<A[1], B[1]> extends true
    ? [B[0], Sub<B[1], A[1]>]
  : [A[0], Sub<A[1], B[1]>];


type ISub<A extends IntegerT, B extends IntegerT> = IAdd<A, INeg<B>>;


type IMul<A extends IntegerT, B extends IntegerT> =
  A[0] extends B[0]
    ? [false, Mul<A[1], B[1]>]
  : [true, Mul<A[1], B[1]>];


type IDiv<A extends IntegerT, B extends IntegerT> =
  A[0] extends B[0]
    ? [false, Div<A[1], B[1]>]
  : [true, Div<A[1], B[1]>];

Examples

type INegResult = IToString<INeg<ToInteger<"-5">>>;
// type INegResult = "5"

type IAddResult = IToString<IAdd<ToInteger<"-20">, ToInteger<"16">>>
// type IAddResult = "-4"

type ISubResult = IToString<ISub<ToInteger<"-20">, ToInteger<"16">>>
// type ISubResult = "-36"

type IMulResult = IToString<IMul<ToInteger<"35">, ToInteger<"-8">>>
// type IMulResult = "-280"

type IDivResult = IToString<IDiv<ToInteger<"-35">, ToInteger<"8">>>
// type IDivResult = "-4"

Rationals

type RationalT = [IntegerT, NaturalT];

type RNegTwo = [INegTwo, One];
type RNegOne = [INegOne, One];
type RNegHalf = [INegOne, Two];
type RZero = [IZero, One];
type RHalf = [IOne, Two];
type ROne = [IOne, One];
type RTwo = [ITwo, One];

type RToString<A extends RationalT> = `${IToString<A[0]>}/${ToNumber<A[1]>}`

type ToRational<A extends string> = 
  A extends `-${infer N extends number}/${infer D extends number}` ? [[true, ToNatural<N>], ToNatural<D>]
  : A extends `${infer N extends number}/${infer D extends number}` ? [[false, ToNatural<N>], ToNatural<D>]
  : never

type Gcd<A extends NaturalT, B extends NaturalT> =
  B extends Zero ? A
  : Gcd<B, Rem<A, B>>;

type RSimplify<A extends RationalT, D extends NaturalT = Gcd<A[0][1], A[1]>> =
  [[A[0][0], Div<A[0][1], D>], Div<A[1], D>];


type RNeg<A extends RationalT> = [INeg<A[0]>, A[1]]

type RAdd<A extends RationalT, B extends RationalT> =
  A[1] extends B[1]
    ? [IAdd<A[0], B[0]>, A[1]]
  : RSimplify<[IAdd<IMul<A[0], [false, B[1]]>, IMul<B[0], [false, A[1]]>>, Mul<A[1], B[1]>]>;

type RSub<A extends RationalT, B extends RationalT> =
  RAdd<A, RNeg<B>>

type RMul<A extends RationalT, B extends RationalT> =
  RSimplify<[IMul<A[0], B[0]>, Mul<A[1], B[1]>]>;

type RReciprocal<A extends RationalT> = [[A[0][0], A[1]], A[0][1]];

type RDiv<A extends RationalT, B extends RationalT> =
  RMul<A, RReciprocal<B>>;

Examples

type RSimplifyResult = RToString<RSimplify<ToRational<"456/93">>>
// type RSimplifyResult = "152/31"

type RNegResult = RToString<RNeg<ToRational<"-123/12">>>
// type RNegResult = "123/12"

type RAddResult = RToString<RAdd<ToRational<"-20/15">, ToRational<"16/23">>>
// type RAddResult = "-44/69"

type RSubResult = RToString<RSub<ToRational<"-20/15">, ToRational<"16/23">>>
// type RSubResult = "-140/69"

type RMulResult = RToString<RMul<ToRational<"35/8">, ToRational<"-8/12">>>
// type RMulResult = "-35/12"

type RDivResult = RToString<RDiv<ToRational<"-35/8">, ToRational<"8/12">>>
// type RDivResult = "-105/16"