本节目标：用条件类型、
infer与递归搭出类型级的数组、链表与字典，实现类型级算术、比较与排序，理解 TypeScript 类型系统的计算能力边界（图灵完备）以及这种能力在工程上的真实代价。
2.3 类型级数据结构与图灵完备
前两节我们有了判断（2.1 条件类型与分发
）与提取（2.2 infer 与递归
），这一节把二者拼成数据结构与算法。理解了这一层，再读 type-challenges 或者 zod、tRPC 这类库的类型定义，就不会觉得像天书了。
一、元组就是类型级数组
类型级编程里，元组承担数组角色：[] 是空数组，[H, ...R] 是「头 + 尾」，T['length'] 是长度。
type Head<T extends unknown[]> = T extends [infer H, ...unknown[]] ? H : never;
type Tail<T extends unknown[]> = T extends [unknown, ...infer R] ? R : never;
type Len<T extends unknown[]> = T['length'];
type H = Head<['a', 'b']>; // 'a'
type Tl = Tail<['a', 'b']>; // ['b']
type N = Len<[1, 2, 3]>; // 3（字面量类型，不是 number）
T['length'] 返回的是字面量类型 3 而非 number，这是元组区别于数组的关键。正因为长度是字面量，才能拿它做数值运算。
增删与拼接同样直接：
type Push<T extends unknown[], V> = [...T, V];
type Concat<A extends unknown[], B extends unknown[]> = [...A, ...B];
type P = Push<[1, 2], 3>; // [1, 2, 3]
type C = Concat<[1], ['a']>; // [1, 'a']
二、类型级算术
没有类型级整数，就用「元组长度」当计数器。加法等于拼接两个元组后取长度：
type BuildTuple<N extends number, Acc extends unknown[] = []> =
Acc['length'] extends N ? Acc : BuildTuple<N, [...Acc, unknown]>;
type Add<A extends number, B extends number> =
[...BuildTuple<A>, ...BuildTuple<B>]['length'];
type Sum = Add<3, 4>; // 7
减法等于从元组里逐个移除，直到长度匹配：
type Subtract<A extends number, B extends number> =
BuildTuple<A> extends [...BuildTuple<B>, ...infer Rest] ? Rest['length'] : never;
type Diff = Subtract<10, 4>; // 6
乘法等于把 A 重复 B 次拼接：
type MultiplyTuples<A extends unknown[], B extends unknown[], Acc extends unknown[] = []> =
B extends [unknown, ...infer Rest]
? MultiplyTuples<A, Rest, [...Acc, ...A]>
: Acc['length'];
type Multiply<A extends number, B extends number> =
MultiplyTuples<BuildTuple<A>, BuildTuple<B>>;
type Product = Multiply<3, 4>; // 12
到这一步，代码已经明显难读了——这是类型级编程的固有代价：没有循环语句、没有局部变量、没有函数体，一切靠递归与参数传递。工程实践中，超过两三层的算术组合就该考虑改用代码生成，而不是硬写类型。
这里有个性能细节：先构造两个输入元组，再消耗乘数元组并增长累加器。TS 5.9.3 下 Multiply<20, 20> 可以通过，但更大的乘积仍会增加元组大小与实例化开销；输入应限制为非负整数字面量，不能承诺任意规模。
三、类型级比较与排序
比较大小靠元组包含关系，语义是「A 是否严格大于 B」：
type GreaterThan<A extends number, B extends number> =
BuildTuple<A> extends [...BuildTuple<B>, ...infer Rest]
? Rest extends [] ? false : true
: false;
type G1 = GreaterThan<5, 3>; // true
type G2 = GreaterThan<3, 5>; // false
type G3 = GreaterThan<3, 3>; // false
有了比较，就能写求最大值与插入排序。注意这里用了 2.1 节讲过的元组包裹技巧 [M] extends [never] 来避免 never 参与分发：
type Max<A extends number, B extends number> = GreaterThan<A, B> extends true ? A : B;
type MaxOf<T extends number[], M extends number = never> =
T extends [infer H extends number, ...infer R extends number[]]
? MaxOf<R, [M] extends [never] ? H : Max<M, H>>
: M;
type Mx = MaxOf<[3, 9, 2, 7]>; // 9
插入排序是同一套递归的叠加——先用 Insert 把元素插到正确位置，再用 Sort 逐个插入：
type Insert<T extends number[], V extends number> =
T extends [infer H extends number, ...infer R extends number[]]
? GreaterThan<V, H> extends true ? [H, ...Insert<R, V>] : [V, ...T]
: [V];
type Sort<T extends number[], Acc extends number[] = []> =
T extends [infer H extends number, ...infer R extends number[]]
? Sort<R, Insert<Acc, H>>
: Acc;
type Sorted = Sort<[3, 1, 2]>; // [1, 2, 3]
十几行类型代码换来一个 O(n²) 的类型级排序。能用，但几乎不值得用——这段代码的调试成本远高于它带来的类型安全收益。
四、类型级字典与查找
对象类型就是类型级字典：keyof 是键集合，T[K] 是索引访问。
type Schema = {
user: { id: number; name: string };
post: { id: number; title: string };
};
type Get<T, K extends keyof T> = T[K];
type User = Get<Schema, 'user'>; // { id: number; name: string }
type Keys = keyof Schema; // 'user' | 'post'
要在字典里「按值反查键」，用 as 子句加条件类型：
type FindKey<T, V> = {
[K in keyof T]: T[K] extends V ? K : never;
}[keyof T];
type Key = FindKey<Schema, { id: number; name: string }>; // 'user'
{ ... }[keyof T] 这个「先建对象、再索引所有键」的写法，等价于把对象所有值合并成联合，是类型级编程里最常见的聚合手法。它也可以反过来用：从对象的所有键生成一个「键 → 描述」的映射表。
type Describe<T> = { [K in keyof T]: { key: K; type: T[K] } }[keyof T];
type D = Describe<{ a: number; b: string }>;
// { key: 'a'; type: number } | { key: 'b'; type: string }
五、类型级链表：把元组当递归结构
用「头 + 尾」的视角看，元组就是单链表。下面实现成员测试与去重：
type IsEqual<A, B> =
(<T>() => T extends A ? 1 : 2) extends (<T>() => T extends B ? 1 : 2) ? true : false;
type Includes<T extends unknown[], V> =
T extends [infer Hd, ...infer R]
? IsEqual<Hd, V> extends true ? true : Includes<R, V>
: false;
type Unique<T extends unknown[], Seen extends unknown[] = []> =
T extends [infer Hd, ...infer R]
? Includes<Seen, Hd> extends true ? Unique<R, Seen> : Unique<R, [...Seen, Hd]>
: Seen;
type U = Unique<[1, 2, 1, 3, 2]>; // [1, 2, 3]
这里的 IsEqual 是 2.1 节给过的严格相等判定（用两个函数类型的兼容性做中介）。整段代码的模式值得记住：Seen 是累积器，Includes 是成员测试，递归调用自身且在尾部位置——这就是类型级的尾递归，也是它能支撑较长输入的原因。
六、联合即集合
把联合类型当集合看，集合运算就是标准工具类型的组合：
type Union<A, B> = A | B; // 并集
type Intersect<A, B> = Extract<A, B>; // 交集
type Difference<A, B> = Exclude<A, B>; // 差集
type U = Union<'a' | 'b', 'c'>; // 'a' | 'b' | 'c'
type I = Intersect<'a' | 'b' | 'c', 'b' | 'c' | 'd'>; // 'b' | 'c'
type D = Difference<'a' | 'b' | 'c', 'b'>; // 'a' | 'c'
子集判定则要小心分发。要利用分发做「每个成员都满足」的检查，要关闭分发才能得到干净的布尔值：
type IsSubsetEach<A, B> = A extends B ? true : false; // 分发：逐成员检查
type IsSubset<A, B> = [A] extends [B] ? true : false; // 关闭分发：整体判定
type R1 = IsSubsetEach<'a' | 'b', 'a' | 'b' | 'c'>; // true
type R2 = IsSubsetEach<'a' | 'd', 'a' | 'b' | 'c'>; // boolean（部分满足，无法直接判断）
type R3 = IsSubset<'a' | 'd', 'a' | 'b' | 'c'>; // false（干净的布尔值）
R2 是 boolean 而不是 false，这正是 2.1 节「坑 2」的重演。做集合判定时，默认用元组包裹的版本，除非确实需要逐成员的结果。
七、从联合到元组：把集合变成序列
联合类型是无序的，但有时需要顺序。经典做法是用「函数参数 + 逆变」把顺序固定下来：
type UnionToIntersection<U> =
(U extends unknown ? (x: U) => void : never) extends (x: infer I) => void ? I : never;
type LastOfUnion<U> =
UnionToIntersection<U extends unknown ? () => U : never> extends () => infer R ? R : never;
type UnionToTuple<U, Last = LastOfUnion<U>> =
[U] extends [never] ? [] : [...UnionToTuple<Exclude<U, Last>>, Last];
type Tup = UnionToTuple<'a' | 'b' | 'c'>; // ['a', 'b', 'c']
UnionToIntersection 是这段的枢纽：把联合的每个成员放到函数参数的逆变位置，多个候选参数会被合并成交叉，再用 infer 把交叉取出来。这是 2.2 节讲过的逆变合并规则最著名的应用，也是很多「把联合类型当集合运算」工具的基础。
有了联合转元组，就能把「键的联合」变成真正的可遍历序列，进而做类型级的键排序、按联合顺序生成客户端方法：
type Api = 'getUser' | 'listPosts' | 'deletePost';
type Client = { [K in Api]: (...args: unknown[]) => Promise<unknown> };
type ClientKeys = UnionToTuple<keyof Client>; // 顺序固定下来的键元组
顺带一提，交叉类型在对象上的合并语义常被用来「覆盖字段」：
type Override<T, U> = Omit<T, keyof U> & U;
type Base = { id: number; name: string };
type Patched = Override<Base, { name: string | null }>;
// { id: number } & { name: string | null }
八、图灵完备意味着什么
把上面的能力列成一张对照表：
| 计算要素 | 类型系统里的对应物 |
|---|---|
| 变量 | 类型参数 |
| 条件分支 | 条件类型 T extends U ? X : Y |
| 循环 | 递归类型引用 |
| 数据结构 | 元组、对象类型 |
| 整数 | 元组 ['length'] |
| 函数抽象 | 泛型类型别名 |
| 字符串处理 | 模板字面量类型 + infer |
条件类型（分支）加递归（循环）加无限结构（模板字面量、变长元组），三者齐备就足以模拟任意图灵机。事实上社区已经有人用 TS 类型实现了 Brainfuck 解释器与正则引擎。但这不等于你应该这么做。
代价有三条：
- 编译时间。类型级计算在
tsc里是同步执行的，深度递归会让编译从毫秒级涨到秒级。它和运行时的 JIT 优化完全是两回事——类型只在编译期存在，1.2 类型擦除与运行时边界 已经讲清了这条边界。 - 错误信息。深度递归出错时，报错是展开后的一长串类型，且常以
TS2589收尾，几乎无法定位到源头。 - 可维护性。类型级代码没有调试器、没有运行时单测，可读性远低于普通代码，团队里能维护它的人也更少。
工程判据是：若一个类型工具需要超过约 30 行、或递归深度超过约 20 层，优先考虑代码生成（5.3 AST 与代码生成 ）而不是硬写类型。
九、真实库里的应用
主流库对类型级编程的使用都很克制：
zod用条件类型加infer，从 schema 对象推导出静态类型（z.infer<typeof schema>）；tRPC用递归加模板字面量类型，把路由路径变成类型；type-fest提供了大量类型级工具（Split、CamelCase、Merge），但每个都控制在很小的递归深度内。
它们的共同点是：类型级计算只用来「把已有信息重新排列」，不用来做真正的业务计算。 这是库作者的边界感。若你对「类型系统能表达多少约束」这个话题感兴趣，可以对比看 C++ 模板与泛型编程 与 编译器中的约束求解与类型类 ，两者的表达能力与代价取舍与 TS 高度相似；类型推导与类型检查 则从编译器内部视角解释了「为什么深度递归会变慢」。
十、性能与可读性的取舍
给类型工具做一次「预算」是个好习惯。类型级代码唯一的回归手段是类型测试：
type Assert<T extends true> = T;
type _1 = Assert<IsEqual<Add<1, 2>, 3>>;
type _2 = Assert<IsEqual<Head<[1, 2]>, 1>>;
type _3 = Assert<IsEqual<Unique<[1, 1, 2]>, [1, 2]>>;
type _4 = Assert<IsEqual<Sort<[3, 1, 2]>, [1, 2, 3]>>;
这些断言在 tsc 通过时静默，失败时报错。把它们放进一个不进产物的 *.test-d.ts 文件，配合 CI 里的类型检查即可。若类型工具真的成了瓶颈，测量方法见 3.1 类型实例化开销与测量
，编译期性能的整体优化思路还可以参考 TypeScript 编译性能优化
。
递归本身是个通用话题，若你想从算法角度复习「递归 + 回溯」的写法（用运行时代码而非类型），递归与回溯 是一篇合适的延伸阅读。
小结
- 类型级数据结构以元组为核心：
[infer Hd, ...infer R]是链表遍历，T['length']是唯一的数值来源。 - 类型级算术（加减乘除、比较、排序）全部绕道元组长度实现，代码密度高、可读性差，是不得已才用的手段。
- 对象类型即类型级字典；
{ [K in keyof T]: ... }[keyof T]是最常见的聚合手法，UnionToIntersection是逆变合并的经典应用。 - 联合类型即集合：并集用
|、交集用Extract、差集用Exclude；子集判定默认用[A] extends [B]关闭分发，避免得到boolean。 - TypeScript 类型系统图灵完备，但代价是编译时间、错误可读性与可维护性。
- 工程判据：能用代码生成就不要硬写类型；类型工具应有深度与行数预算，并用
IsEqual断言做类型测试。
至此第二章「类型级编程」结束。下一章我们从「能不能算」转向「算得多贵」——3.1 类型实例化开销与测量 开始量化类型实例化的成本，把本章学到的工具放进真实的性能预算里。
阅读导航：上一节：2.2 infer 与递归 · 下一节：3.1 类型实例化开销与测量 。
继续阅读
探索更多技术文章
浏览归档，发现更多关于系统设计、工具链和工程实践的内容。