跳到主要内容

第 17 章 · 类型层的数学与逻辑

读完本章你会
  • 用「元组长度」模拟数字：加减、比较、判断整除
  • 理解元组法的边界，以及什么时候该换「字符串算术」
  • 在类型层实现 MinusOne、Sum、GreaterThan、TwoSum、FizzBuzz
  • 理解类型层算法的「复杂度」与深度限制
本章是全书的高光

前 16 章学的都是「类型系统怎么描述数据」，本章把它当成计算设备——用类型做数学、做逻辑题。这些题的工程价值不大，但它们是把前面所有招式融会贯通的终极练兵场。

17.1 数字的类型级表示​

TS 没有「数字运算」，但有三种表示法，各有边界：

表示做法边界
元组长度数字 N = 长度为 N 的元组递归深度上限（约几千）
字符串'123' 逐位算任意长度，但要写进位/借位逻辑
模板取数${T} 转字符串只读，不能算

17.1.1 数字 ⇄ 元组（第 14 章复习）​

type BuildTuple<N extends number, T extends any[] = []> =
  T['length'] extends N ? T : BuildTuple<N, [...T, any]>

type NumToArr = BuildTuple<3>       // [any, any, any]
type ArrToNum = [any, any, any]['length'] // 3

17.1.2 数字 ⇄ 字符串​

type NumToStr<N extends number> = `${N}`      // 3 → '3'
type StrToNum<S extends string> = S extends `${infer N extends number}` ? N : never
type Back = StrToNum<'42'> // 42
元组 vs 字符串，怎么选
  • 小数字、需要比较/加减：元组法直观（Add、Subtract、GreaterThan）
  • 大数字（2^53 级）、要进位借位：字符串法（Sum、MinusOne 的大数版）
  • 只要读、不算：${T} 模板取数

第 5-8 章讲过，MinusOne<9007199254740992> 用元组法会直接撑爆——这就是换字符串法的信号。

17.2 加减法​

17.2.1 Subtract：元组法​

第 14 章已实现：长的元组吞掉短的，剩下的是差。

type BuildTuple<N extends number, T extends any[] = []> = /* 17.1.1 */

type Subtract<M extends number, S extends number> =
  BuildTuple<M> extends [...BuildTuple<S>, ...infer R] ? R['length'] : never

type A = Subtract<5, 2> // 3
type B = Subtract<1, 2> // never（减不了，返回 never）
为什么 07561 Subtract 是 extreme

它的测试里有一行 // @ts-expect-error Expect<Equal<Subtract<1000, 999>, 1>>——故意期望 Subtract<1000, 999> 算不对。因为元组法在 1000 附近开始触发递归深度限制，算不出来（返回异常类型），正好被 @ts-expect-error 接住。这道题在考你：知道元组法的边界在哪。

17.2.2 MinusOne 大数版：字符串借位​

MinusOne<9007199254740992> 必须用字符串逐位减 1（含借位）。骨架如下：

// 反转字符串（低位在前，方便借位从个位开始）
type Reverse<S extends string> = S extends `${infer F}${infer R}` ? `${Reverse<R>}${F}` : S

// 单个数字减 1，返回 `${digit}${borrow}`，borrow 为 '0'|'1'
// '0' → '91'（0-1=9 且借位）；'3' → '20'；……；'9' → '80'
type DecDigit<D extends string> = /* 数字 → 减 1 的查找表 */

// 对反转串逐位减 1（带借位）
type DecRev<S extends string> =
  S extends `${infer Last}${infer Rest}`
    ? DecDigit<Last> extends `${infer NLast}${infer Borrow}`
      ? Borrow extends '0' ? `${NLast}${Rest}` : `${NLast}${DecRev<Rest>}`
      : never
    : '0'

// 去前导零
type TrimZeros<S extends string> = S extends `0${infer R}` ? (R extends '' ? '0' : TrimZeros<R>) : S

type MinusOneStr<S extends string> = TrimZeros<Reverse<DecRev<Reverse<S>>>>

type MinusOne<T extends number> = MinusOneStr<`${T}`> extends `${infer N extends number}` ? N : never

type A = MinusOne<100>                      // 99
type B = MinusOne<9_007_199_254_740_992>    // 9_007_199_254_740_991（元组法做不到）
字符串算术的套路

「反转 → 从个位开始带借位逐位算 → 反转回来 → 去前导零」。借位（Borrow）就是「上一位减不够，向更高位借 1」——和小学列竖式一模一样。Sum 的进位、Subtract 的借位，都是这个套路。

17.3 比较与查找​

17.3.1 GreaterThan：先比位数，再逐位比​

大数不能建元组，用字符串比：位数长的更大；位数相同，逐位比。

// 位数（元组法，只数「几位」，位数很小）
type StrLen<S extends string, T extends any[] = []> =
  S extends `${infer F}${infer R}` ? StrLen<R, [...T, any]> : T['length']

// 同位数逐位比
type DigitGt<A extends string, B extends string> = /* '9'>'8' 之类的单字符比较表 */

type CompareStr<A extends string, B extends string> =
  StrLen<A> extends StrLen<B>
    ? A extends `${infer DA}${infer RA}`
      ? B extends `${infer DB}${infer RB}`
        ? DA extends DB ? CompareStr<RA, RB> : DigitGt<DA, DB>
        : false
      : false
    : /* 位数不同：谁长谁大（用 StrLen 元组比较） */

type GreaterThan<T extends number, U extends number> = CompareStr<`${T}`, `${U}`>

type A = GreaterThan<111, 11>               // true（位数多）
type B = GreaterThan<4, 5>                  // false（同位数逐位比）
type C = GreaterThan<1234567891011, 1234567891010> // true
位数比较的巧劲

比位数不用真的「数到多少」，把两位数字符串各自的 StrLen 元组比一下即可（A extends [...B, ...any[]] 判断 A 更长）。位数最多十几位，元组法毫无压力。

17.3.2 TwoSum：减法 + 查找​

TwoSum<T, U> 判断「元组里有没有两个数相加等于 U」。思路：对每个元素 F，若 U - F 出现在剩余元素里，则 true：

type SubtractT<M extends number, S extends number> = /* 17.2.1 */
type EqualN<X, Y> = X extends Y ? (Y extends X ? true : false) : false
type IsIn<Arr extends any[], U> = /* 第 13 章 Includes 的数值版 */

type TwoSum<T extends number[], U extends number> =
  T extends [infer F extends number, ...infer R extends number[]]
    ? SubtractT<U, F> extends never        // U < F 算不了 → 跳过这个元素
      ? TwoSum<R, U>
      : IsIn<R, SubtractT<U, F>> extends true ? true : TwoSum<R, U>
    : false

type A = TwoSum<[3, 2, 4], 6> // true（2 + 4）
type B = TwoSum<[2, 7, 11, 15], 15> // false
never 的坑

SubtractT<U, F> 在 U < F 时返回 never。千万别写 SubtractT<U, F> extends infer Diff ? ... : ...——never extends infer 会因分发直接短路成 never（第 7 章讲过的坑），整个函数变 never。必须先 extends never 挡一层，再在 else 里用结果。

17.4 逻辑题：FizzBuzz​

FizzBuzz<N> 生成 ['1', '2', 'Fizz', ...]。核心是「判断能否被 3 / 5 整除」——用元组取模：

type BuildTuple<N extends number, T extends any[] = []> = /* 17.1.1 */

// N mod K：用元组反复减 K，减不动的余数就是模
type Mod<N extends number, K extends number> =
  BuildTuple<N> extends [...BuildTuple<K>, ...infer R]
    ? R['length'] extends 0 ? 0 : Mod<R['length'], K>
    : N

type IsDiv0<N extends number, K extends number> = Mod<N, K> extends 0 ? true : false

type Convert<N extends number> =
  IsDiv0<N, 3> extends true
    ? IsDiv0<N, 5> extends true ? 'FizzBuzz' : 'Fizz'
    : IsDiv0<N, 5> extends true ? 'Buzz' : `${N}`

type FizzBuzz<N extends number, T extends any[] = [], R extends string[] = []> =
  T['length'] extends N
    ? R
    : FizzBuzz<N, [...T, any], [...R, Convert<[...T, any]['length']>]>

type A = FizzBuzz<5> // ['1', '2', 'Fizz', '4', 'Buzz']
FizzBuzz 的三层结构
  1. Mod 判整除（元组反复减 K）
  2. Convert 把数字转成对应的 Fizz/Buzz/数字
  3. FizzBuzz 用累积元组从 1 一路生成到 N

生成一个序列 = 累积参数 + 每步转换——和 Unique、Join 是同一套手法。

17.5 复杂度与边界​

类型层算法的「性能」和运行时完全不同：

因素影响
递归深度元组法上限约几千；超了报「excessively deep」
联合大小每分发一次都可能指数膨胀（如 Permutation）
字符串长度字符串算术和「位数」成正比，可控
三条实战经验
  1. 小数字用元组，大数字用字符串——MinusOne、Sum、GreaterThan 的大数测试是信号
  2. 能累积就累积（尾递归），别靠递归栈往下传
  3. 知道边界，但不被边界吓住——本书题库里 Sum<1_000_000_000_000n> 都能算，靠的是字符串算术，不是蛮力

本章小结​

  • 数字三表示：元组长度（可算但浅）、字符串（可算且深）、模板取数（只读）
  • Subtract 元组法 + 借位字符串法；MinusOne 大数靠字符串借位
  • GreaterThan 先比位数再逐位比；TwoSum = 减法 + 查找（注意 never 陷阱）
  • FizzBuzz = 取模判整除 + 累积生成
  • 类型层有复杂度边界：递归深度、联合膨胀；选对表示法才是关键

本章练习​

挑战题​

题号题目难度考察点
02257MinusOnemedium元组或字符串减 1
07561Subtractextreme元组法 + 边界
00476Sumextreme字符串进位加法
04425Greater Thanmedium位数 + 逐位比
08804两数之和hard减法 + 查找
14080FizzBuzzhard取模 + 累积生成

代码练习

  1. BuildTuple 与 Add：实现 BuildTuple 和 Add<A, B>（元组拼接取长度），验证 Add<7, 5> 是 12。

  2. Subtract 边界：实现 Subtract，验证 Subtract<1, 2> 是 never，并试 Subtract<50, 49>，感受元组法在大数附近的表现。

  3. Mod 判整除：实现 Mod 和 IsDiv0，验证 IsDiv0<9, 3> 是 true、IsDiv0<10, 3> 是 false。

  4. FizzBuzz 简化：实现 FizzBuzz<15>，对照答案验证 15 处是 'FizzBuzz'（既是 3 倍数又是 5 倍数）。

  5. TwoSum 修 never 坑：先写出「用 extends infer Diff 直接拿结果」的错误版本，观察 TwoSum<[1, 2], 3> 意外变 never；再改成「先 extends never 挡一层」的正确版本，验证通过。