第 26 章

类型级算法：Filter/Zip/BinaryAdd — 图灵完备的边界

第26章：类型级算法：Filter、Zip、BinaryAdd — 探索图灵完备的边界

理解类型级算法是掌握 TypeScript 类型系统的关键一步。

本章核心问题：如何在实际项目中正确使用Filter、Zip、BinaryAdd — 探索图灵完备的边界？关键的设计决策和陷阱是什么？

读完本章你将理解：

TypeScript 类型系统是图灵完备的
1. Filter：按类型谓词过滤元组
1. ZipWith：将两个元组拼成对

Level 1 · 你需要知道的（1-3年经验）

TypeScript 类型系统是图灵完备的

这不是夸张。TypeScript 的类型系统支持递归条件类型，意味着你可以在类型层面实现任何可计算的函数——代价是编译时间和递归深度限制（约 1000 层）。

本章实现真实的算法：列表操作、数字运算、字符串解析。理解这些不只是"炫技"——它帮助你理解 TypeScript 类型推断的底层计算模型，以及在库类型定义中遇到复杂递归类型时如何阅读它们。

1. Filter：按类型谓词过滤元组

实现

// 过滤出元组中 assignable to Pred 的元素
type Filter<T extends any[], Pred> =
  T extends [infer Head, ...infer Tail]
    ? Head extends Pred
      ? [Head, ...Filter<Tail, Pred>]   // 保留 Head
      : Filter<Tail, Pred>              // 丢弃 Head
    : [];                               // 空元组，终止

// 测试
type Mixed = [string, number, string, boolean, string, null];

type Strings = Filter<Mixed, string>;
// [string, string, string]  ✓

type Numbers = Filter<Mixed, number | boolean>;
// [number, boolean]  ✓

type NonNullable2<T extends any[]> = Filter<T, {}>;
type CleanMixed = NonNullable2<[string, null, number, undefined, boolean]>;
// [string, number, boolean]  ✓

拆解：

T extends [infer Head, ...infer Tail]：把元组拆成头元素和剩余部分
Head extends Pred：测试头元素是否满足谓词
递归处理 Tail，然后用展开运算符重新拼接

2. ZipWith：将两个元组拼成对

// 把 A 和 B 的同位置元素配成 [A[i], B[i]] 对
type ZipWith<A extends any[], B extends any[]> =
  A extends [infer AHead, ...infer ATail]
    ? B extends [infer BHead, ...infer BTail]
      ? [[AHead, BHead], ...ZipWith<ATail, BTail>]
      : []
    : [];

// 测试
type Keys = ["id", "name", "email"];
type Values = [number, string, string];

type Pairs = ZipWith<Keys, Values>;
// [["id", number], ["name", string], ["email", string]]  ✓

// 从对转回对象
type PairsToObject<T extends [PropertyKey, any][]> = {
  [K in T[number] as K[0]]: K[1]
};

type Reconstructed = PairsToObject<Pairs>;
// { id: number; name: string; email: string }  ✓

变体：ZipToObject

// 更直接：两个平行的键值元组合并成对象类型
type ZipToObject<
  Keys extends readonly PropertyKey[],
  Values extends readonly any[]
> = {
  [K in Keys[number] as K]: K extends Keys[number]
    ? Values[Extract<Keys[number], K> extends never ? never : {
        [I in keyof Keys]: Keys[I] extends K ? I : never
      }[number]]
    : never
};

// 实际上更简单的方式：用 infer 模式
type Zip<K extends PropertyKey[], V extends any[]> =
  { [I in keyof K]: I extends keyof V ? { key: K[I]; value: V[I] } : never }[number];

type Zipped = Zip<["a", "b", "c"], [1, 2, 3]>;
// { key: "a"; value: 1 } | { key: "b"; value: 2 } | { key: "c"; value: 3 }

3. Reverse：反转元组

type Reverse<T extends any[], Acc extends any[] = []> =
  T extends [infer Head, ...infer Tail]
    ? Reverse<Tail, [Head, ...Acc]>   // 尾递归：用 Acc 积累结果
    : Acc;

// 测试
type Rev = Reverse<[1, 2, 3, 4, 5]>;
// [5, 4, 3, 2, 1]  ✓

type Rev2 = Reverse<["a", "b", "c"]>;
// ["c", "b", "a"]  ✓

注意 Acc 参数——这是尾递归优化的关键模式。不用 Acc 的版本需要在回溯时重建结果，深度更大；用 Acc 的版本把结果携带在参数里，TypeScript 编译器可以优化（实际上 TS 编译器对尾递归类型有特殊处理）。

Level 2 · 它是怎么运行的（3-5年经验）

4. Flatten：深度展开嵌套元组

type Flatten<T extends any[]> =
  T extends [infer Head, ...infer Tail]
    ? Head extends any[]
      ? [...Flatten<Head>, ...Flatten<Tail>]
      : [Head, ...Flatten<Tail>]
    : [];

// 测试
type Nested = [1, [2, [3, [4]]], 5];
type Flat = Flatten<Nested>;
// [1, 2, 3, 4, 5]  ✓

type Nested2 = [[string, number], [boolean, [null, undefined]]];
type Flat2 = Flatten<Nested2>;
// [string, number, boolean, null, undefined]  ✓

5. 数字运算：类型系统的最深处

这是本章最令人震惊的部分：TypeScript 没有数字类型的加减乘除，但可以通过元组长度做运算。

核心原语：BuildTuple

// 构建长度为 N 的元组
type BuildTuple<N extends number, T extends unknown[] = []> =
  T["length"] extends N
    ? T
    : BuildTuple<N, [...T, unknown]>;

type T3 = BuildTuple<3>;   // [unknown, unknown, unknown]
type T5 = BuildTuple<5>;   // [unknown, unknown, unknown, unknown, unknown]

T["length"] 返回元组的长度作为字面量数字类型——这是整个数字运算的基础。

Add：加法

type Add<A extends number, B extends number> =
  [...BuildTuple<A>, ...BuildTuple<B>]["length"];

type Sum1 = Add<3, 4>;   // 7  ✓
type Sum2 = Add<10, 5>;  // 15 ✓

把两个元组合并，长度相加。

Subtract：减法

// A - B，要求 A >= B
type Subtract<A extends number, B extends number> =
  BuildTuple<A> extends [...BuildTuple<B>, ...infer Rest]
    ? Rest["length"]
    : never;

type Diff1 = Subtract<10, 3>;  // 7  ✓
type Diff2 = Subtract<5, 5>;   // 0  ✓
// type Diff3 = Subtract<3, 5>;  // never（不支持负数）

BuildTuple<A> extends [...BuildTuple<B>, ...infer Rest]：看 A 个元素的元组是否能拆成 B 个元素加上剩余，Rest 就是差值对应的元组。

Multiply：乘法（递归累加）

type Multiply<
  A extends number,
  B extends number,
  Acc extends unknown[] = []
> =
  B extends 0
    ? Acc["length"]
    : Multiply<A, Subtract<B, 1>, [...Acc, ...BuildTuple<A>]>;

type Prod1 = Multiply<3, 4>;   // 12 ✓
type Prod2 = Multiply<5, 6>;   // 30 ✓

IsGreaterThan：大小比较

type IsGreaterThan<A extends number, B extends number> =
  A extends B
    ? false                             // 相等
    : BuildTuple<A> extends [...BuildTuple<B>, ...infer _Rest]
      ? true                            // A > B：A 的元组包含 B 的元组
      : false;                          // A < B

type GT1 = IsGreaterThan<5, 3>;   // true  ✓
type GT2 = IsGreaterThan<3, 5>;   // false ✓
type GT3 = IsGreaterThan<3, 3>;   // false ✓

运算极限与对策

// 这会触发"类型实例化过深"错误
type Overflow = BuildTuple<1001>;  // Type instantiation is excessively deep and possibly infinite

// 实际可用范围：通常 < 100 对性能友好，< 500 勉强可用，> 1000 会超限
// 对于大数运算，改用字符串位运算或放弃在类型层面实现

TypeScript 的递归限制约为 1000 层（不同版本有差异）。超过后报错 Type instantiation is excessively deep and possibly infinite。

6. 字符串解析：类型层面的词法分析

Split：按分隔符拆分字符串字面量

type Split<S extends string, Sep extends string> =
  S extends `${infer Head}${Sep}${infer Tail}`
    ? [Head, ...Split<Tail, Sep>]
    : [S];

// 测试
type Parts = Split<"a,b,c,d", ",">;
// ["a", "b", "c", "d"]  ✓

type PathParts = Split<"foo/bar/baz", "/">;
// ["foo", "bar", "baz"]  ✓

// 分割空字符串（逐字符）
type Chars = Split<"hello", "">;
// ["h", "e", "l", "l", "o"]  ✓

Join：将元组拼接成字符串字面量

type Join<T extends string[], Sep extends string> =
  T extends []
    ? ""
    : T extends [infer Only extends string]
      ? Only
      : T extends [infer Head extends string, ...infer Tail extends string[]]
        ? `${Head}${Sep}${Join<Tail, Sep>}`
        : never;

// 测试
type Joined = Join<["a", "b", "c"], "-">;
// "a-b-c"  ✓

type Path = Join<["foo", "bar", "baz"], "/">;
// "foo/bar/baz"  ✓

实战：类型安全的路径解析

// 解析路由路径，提取参数名
type ExtractRouteParams<Route extends string> =
  Route extends `${string}:${infer Param}/${infer Rest}`
    ? Param | ExtractRouteParams<`/${Rest}`>
    : Route extends `${string}:${infer Param}`
      ? Param
      : never;

type Params1 = ExtractRouteParams<"/user/:id/posts/:postId">;
// "id" | "postId"  ✓

type Params2 = ExtractRouteParams<"/static/path">;
// never  ✓

// 从参数名构建类型安全的参数对象
type RouteParamObject<Route extends string> = {
  [K in ExtractRouteParams<Route>]: string;
};

type UserParams = RouteParamObject<"/user/:id/posts/:postId">;
// { id: string; postId: string }  ✓

7. 尾递归优化：突破深度限制

TypeScript 4.5 引入了对尾递归条件类型的特殊优化，可以突破部分深度限制：

// 非尾递归版本（需要回溯重建）：深度受限较严
type ReverseNonTail<T extends any[]> =
  T extends [infer H, ...infer R]
    ? [...ReverseNonTail<R>, H]  // 在返回值上做操作——无法优化
    : [];

// 尾递归版本（结果在 Acc 参数中积累）：编译器可优化
type ReverseTail<T extends any[], Acc extends any[] = []> =
  T extends [infer H, ...infer R]
    ? ReverseTail<R, [H, ...Acc]>  // 最后一步是直接返回递归调用——可优化
    : Acc;

// ReverseTail 在实践中可处理更长的元组
type LongReversed = ReverseTail<[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20]>;
// 正确工作  ✓

尾递归优化的条件：条件类型的 true 分支直接是递归调用，不在返回值上做任何额外操作。TypeScript 编译器会将这类调用转换为迭代，从而绕过递归深度限制。

实战：类型安全的 SQL 查询构建器（类型层面）

// 简化版：从 SELECT 字符串提取列名
type ParseSelect<S extends string> =
  S extends `SELECT ${infer Cols} FROM ${string}`
    ? Split<Trim<Cols>, ", ">
    : never;

type Trim<S extends string> =
  S extends ` ${infer R}` ? Trim<R> :
  S extends `${infer L} ` ? Trim<L> :
  S;

type Cols = ParseSelect<"SELECT id, name, email FROM users">;
// ["id", "name", "email"]  ✓

// 基于提取的列名构建结果类型
type QueryResult<
  Schema extends Record<string, any>,
  Cols extends (keyof Schema)[]
> = Pick<Schema, Cols[number]>;

type UserSchema = { id: number; name: string; email: string; password: string };
type SelectedUser = QueryResult<UserSchema, ["id", "name", "email"]>;
// { id: number; name: string; email: string }  ✓

递归深度限制参考

操作	实际可用范围	超限表现
元组索引递归（非尾递归）	~45 层	"excessively deep" 错误
尾递归优化的元组操作	~1000 层	同上，但限制宽松
字符串模板递归	~100 字符	同上
数字运算（BuildTuple）	0~999	>999 超限
条件类型嵌套	~1000	编译器挂起或错误

Level 3 · 规范怎么定义的（资深）

TypeScript 的类型系统是图灵完备的（通过递归条件类型证明），但有约 1000 层的递归深度限制。元组长度技巧（BuildTuple<N> + T["length"]）是类型级数字运算的基础，因为 TypeScript 没有原生的类型级算术。尾递归优化（TS 4.5）对条件类型的 true 分支直接是递归调用的情况做了特殊处理，将递归转换为迭代，显著提升了可处理的深度。模板字面量类型配合 infer 实现了类型级的字符串解析能力。

Level 4 · 边界与陷阱（所有人）

反模式

反模式	问题	替代方案
在生产代码中用类型级数字运算处理大数	超出递归限制，编译极慢	只用于 ≤ 100 的数，或换运行时实现
非尾递归的深层元组处理	迅速达到深度上限	改写为带 Acc 参数的尾递归形式
字符串模板无边界解析	长字符串超出深度	添加长度限制或用运行时解析
过度依赖类型层面算法	编译极慢，错误信息难读	用泛型约束 + 运行时验证分工

总结

算法	核心技术	深度限制
`Filter<T, Pred>`	Head/Tail 解构 + 条件重组	受元组长度限制
`ZipWith<A, B>`	双元组同步解构	较短的元组决定深度
`Reverse<T>`	尾递归 + Acc 参数	尾递归优化后可到 ~1000
`Flatten<T>`	嵌套解构 + 双递归	受总元素数限制
`Add/Subtract<A, B>`	BuildTuple 元组长度	操作数 < 1000
`Split<S, Sep>`	模板字面量 infer	字符串长度 < ~100
`Join<T, Sep>`	模板字面量拼接递归	同上

本章评分

4.6 / 5 (4 评分)