TypeScript 支持元组类型,而且可以从元组的 length 属性获取到数字字面量形式的元组的长度。利用这一点,定义长度为 n 的元组为数字 n,就可以进行数学运算了。

本文中的全部代码可以在 TS Playground 打开并玩耍 😃

元组内元素的类型应该是可以任取的,比如 unknownany,在这里记为 E

type E = unknown;

type Num = E[];

type Zero = [];

对于任意一个元组,可以在它前面添加一个 E 得到它的后继数。同样地,也可以在它前面去除一个 E 得到它的前驱数。因为元组的长度非负,无法表示负数,所以定义 [] 的前驱为 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]

下面定义的 ToLitFromLit 用来在数字字面量和元组之间转换。元组转换为数字字面量时直接读取元组的 length 属性。数字字面量转换为元组时从空元组开始,每次用尾递归取元组的后继,直到元组的长度与传入的数字字面量相同时返回当前的元组。

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]

加法、减法操作和后继、前驱的操作是类似的:

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

各种比较运算符和减法操作是类似的,但比较时不需要知道运算结果的具体值,只要知道编译器能否推断出运算结果就好了:

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

有了以上工具,就可以用尾递归写出乘、除、取模、乘方、阶乘、判断一个数是否为质数等更多操作了:

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

除了只操作一个数,我们还会想操作一整个数组里的所有数……

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]

……就可以实现质因数分解……

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]

……或者插入排序:

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]

元组除了用来算数,还可以用类似的方法做一些更实际的事情,比如把一个类似 ArrayLike 的,连续的,但其中每个元素都不同的对象转换为元组:

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];

写在最后:这篇文章刚刚被写成初稿的时候 TypeScript 还只支持 50 层的类型实例化递归。超出这个限制后会产生下面的报错:

error TS2589: Type instantiation is excessively deep and possibly infinite.

下面两个 PR 把类型实例化的层数增加到了 500,并且增加了 conditional types 的尾递归支持:

现在可以愉快地计算更大的数了!

type _23 = ToLit<Mul<FromLit<23>, FromLit<422>>>; // 9706