This article is a translation of its Chinese version.
TypeScript supports tuple types, and the
length property of a tuple can be used to obtain the tuple’s length as a
numeric literal. By using this, we
can define a tuple of length n to represent the number n, allowing us to perform arithmetic operations.
All code examples in this article can be found in TS Playground to play with. 😃
The element type within the tuple should be arbitrary, such as unknown or any. Here, we denote it as E.
type E = unknown;
type Num = E[];
type Zero = [];
For any given tuple, we can prepend an E to get its successor. Similarly, we can remove the first E to get its
predecessor. Since tuple lengths are non-negative, negative numbers cannot be represented, so the predecessor of [] is
defined as never.
type Next<X extends Num> = [E, ...X];
type Prev<X extends Num> = X extends [E, ...infer R] ? R : never;
type One = Next<Zero>; // [E]
type _1 = Prev<Next<One>>; // [E]
The following ToLit and FromLit types are used to convert between numeric literals and tuples. When converting a
tuple to a numeric literal, we simply read the tuple’s length property. When converting a numeric literal to a tuple,
we start with an empty tuple and recursively take its successor until the tuple’s length matches the input numeric
literal.
type ToLit<X extends Num> = X["length"];
type FromLit<N extends number, R extends Num = Zero> =
R["length"] extends N ? R :
FromLit<N, Next<R>>;
type _2 = ToLit<[E, E]>; // 2
type _3 = FromLit<3>; // [E, E, E]
Addition and subtraction operations are similar to successor and predecessor operations:
type Add<X extends Num, Y extends Num> = [...X, ...Y];
type Sub<X extends Num, Y extends Num> = X extends [...Y, ...infer R] ? R : never;
type _4 = ToLit<Add<FromLit<3>, FromLit<1>>>; // 4
type _5 = ToLit<Sub<FromLit<7>, FromLit<2>>>; // 5
Comparison operators are also similar to subtraction, but they don’t require knowing the exact result. It should be enough if the compiler can infer the relationship:
type Eq<X extends Num, Y extends Num> = X extends Y ? true : false;
type Ne<X extends Num, Y extends Num> = X extends Y ? false : true;
type Lt<X extends Num, Y extends Num> = X extends [...Y, ...Num] ? false : true;
type Ge<X extends Num, Y extends Num> = X extends [...Y, ...Num] ? true : false;
type Gt<X extends Num, Y extends Num> = Y extends [...X, ...Num] ? false : true;
type Le<X extends Num, Y extends Num> = Y extends [...X, ...Num] ? true : false;
type _6 = Eq<FromLit<6>, FromLit<6>>; // true
type _7 = Eq<FromLit<6>, FromLit<7>>; // false
type _8 = Lt<FromLit<8>, FromLit<9>>; // true
type _9 = Lt<FromLit<9>, FromLit<9>>; // false
With these tools, we can use tail recursion to implement multiplication, division, modulo, exponentiation, factorial, and even primality testing:
type Mul<X extends Num, Y extends Num, R extends Num = Zero> =
Y extends Zero ? R :
Mul<X, Prev<Y>, Add<R, X>>;
type _10 = ToLit<Mul<FromLit<2>, FromLit<5>>>; // 10
type Div<X extends Num, Y extends Num, R extends Num = Zero> =
Lt<X, Y> extends true ? R :
Div<Sub<X, Y>, Y, Next<R>>;
type Mod<X extends Num, Y extends Num> =
Lt<X, Y> extends true ? X :
Mod<Sub<X, Y>, Y>;
type _11 = ToLit<Div<FromLit<11>, FromLit<5>>>; // 2
type _12 = ToLit<Mod<FromLit<11>, FromLit<5>>>; // 1
type Pow<X extends Num, Y extends Num> =
X extends Zero ? Zero :
_Pow<X, Y, One>;
type _Pow<X extends Num, Y extends Num, R extends Num> =
Y extends Zero ? R :
_Pow<X, Prev<Y>, Mul<R, X>>;
type _13 = ToLit<Pow<FromLit<2>, FromLit<13>>>; // 8192
type Fact<X extends Num, R extends Num = One> =
X extends Zero ? R :
Fact<Prev<X>, Mul<R, X>>;
type _14 = ToLit<Fact<FromLit<7>>>; // 5040
type IsPrime<X extends Num> =
X extends Zero ? false :
X extends One ? false :
_IsPrime<X, Next<One>>;
type _IsPrime<X extends Num, I extends Num> =
Lt<X, Mul<I, I>> extends true ? true :
Mod<X, I> extends Zero ? false :
_IsPrime<X, Next<I>>;
type _15 = IsPrime<FromLit<13>>; // true
type _16 = IsPrime<FromLit<16>>; // false
Beyond single-number operations, we might also want to manipulate entire arrays of numbers…
type Rest<A extends any[]> =
A extends [any, ...infer R] ? R : [];
type _17 = Rest<["a", "b", "c"]>; // ["b", "c"]
type FromLitArr<A extends number[]> =
A extends [] ? [] :
[FromLit<A[0]>, ...FromLitArr<Rest<A>>];
type ToLitArr<A extends Num[]> =
A extends [] ? [] :
[ToLit<A[0]>, ...ToLitArr<Rest<A>>];
type _18 = FromLitArr<[3, 6]>; /* [ [E, E, E],
[E, E, E, E, E, E] ] */
type _19 = ToLitArr<_18>; // [3, 6]
…which allows us to implement prime factorization…
type Factor<X extends Num, I extends Num = Next<One>, R extends Num[] = []> =
X extends One ?
R :
Lt<X, Mul<I, I>> extends true ?
[...R, X] :
Mod<X, I> extends Zero ?
Factor<Div<X, I>, Next<One>, [...R, I]> :
Factor<X, Next<I>, R>;
type _20 = ToLitArr<Factor<FromLit<20>>>; // [2, 2, 5]
…or even insertion sort:
type Insert<A extends Num[], X extends Num, R extends Num[] = []> =
A extends [] ? [...R, X] :
Lt<X, A[0]> extends true ?
[...R, X, ...A] :
Insert<Rest<A>, X, [...R, A[0]]>;
type _21 = ToLitArr<Insert<FromLitArr<[1, 3, 4]>, FromLit<2>>>; // [1, 2, 3, 4]
type Sort<A extends Num[]> =
A extends [] ? [] :
A extends [Num] ? A :
Insert<Sort<Rest<A>>, A[0]>;
type _22 = ToLitArr<Sort<FromLitArr<[3, 5, 1, 2, 4]>>>; // [1, 2, 3, 4, 5]
Tuples aren’t just for arithmetic. They can also be used in more practical ways, such as converting an ArrayLike
object with consecutive but distinct elements into a tuple:
type Mapper<T, R extends any[] = []> =
R["length"] extends keyof T ?
Mapper<T, [...R, T[R["length"]]]> :
R;
type Original = { 0: number, 1: string, 2: boolean };
type Mapped = Mapper<Original>; // [number, string, boolean];
Final Notes
When this article was first drafted, TypeScript only supported 50 levels of type instantiation recursion. Exceeding this limit would produce the following error:
error TS2589: Type instantiation is excessively deep and possibly infinite.
The following two PRs increased the type instantiation depth limit to 500 and added tail recursion support for conditional types:
Now we can compute much larger numbers happily!
type _23 = ToLit<Mul<FromLit<23>, FromLit<422>>>; // 9706