TypeScript中如何计算泛型类型函数的类型不动点

问题背景 #

假设我们有一个类型函数F<T>，想要计算它的不动点，即满足type X = F<X>的类型X。

• 当类型函数返回纯对象类型时，利用interface的延迟求值特性可以直接实现：

interface Tree1<T> { left: T; right: T }
interface Tree extends Tree1<Tree> {}
declare const t: Tree;
const r = t.left.right; // 类型校验通过

• 当类型函数返回联合类型等非纯对象类型时，直接用interface extends会报错：

type Tree1<T> = null | { left: T; right: T }
interface Tree extends Tree1<Tree> {} // 报错：接口不能扩展非对象类型

• 手动写延迟计算逻辑会触发类型实例化深度超限错误：

interface Tree1<T> { left: T; right: T }
type Temp1<T> = { a: null | [T[keyof T], T[keyof T]] }
interface Temp2 extends Temp1<Temp2> {}
declare const t: Temp2;
const r = t.a; // 报错：Type instantiation is excessively deep

• 引入额外包装节点、直接手写递归类型定义的方案都不符合需求：

// 方案1：额外包装节点，多了ref字段，不符合结构要求
type Tree = Tree1<{ref: Tree}>
// 方案2：直接手写递归，没有通用性，不符合不动点计算的要求
type Tree = null | { left: Tree, right: Tree }

核心诉求 #

对给定类型函数Tree1<T> = null | { left: T; right: T }，通过通用不动点计算方式得到Tree类型，满足：

1. 不引入额外的值层面包装节点
2. 不直接手写递归类型定义
3. 赋值语句const t: Tree = {left: null, right: {left: null, right: null}}可以正常通过类型校验

实现方案 #

利用TypeScript的两个核心特性实现通用不动点组合子：

1. interface的递归引用是惰性求值的，不会触发即时无限实例化
2. 递归条件类型可以在访问属性时按需展开类型，不会一次性递归到最大深度

// 虚拟锚点接口，仅用于类型层面标记递归位置，不会出现在最终值类型中
interface Fix<F> {
  _f: F
}
// 递归解包类型：遇到Fix锚点就展开一层F，对象类型递归解包所有属性，基础类型直接返回
type Eval<T> =
  T extends Fix<infer F> ? Eval<F<Fix<F>>> :
  T extends object ? { [K in keyof T]: Eval<T[K]> } :
  T;
// 通用不动点类型，传入类型函数F即可得到其不动点
type FixF<F> = Eval<F<Fix<F>>>

// 测试场景实现
type Tree1<T> = null | { left: T; right: T }
type Tree = FixF<Tree1>

// 用例校验
const t: Tree = {left: null, right: {left: null, right: null}}; // 校验通过
const r = t.right.left; // 推导类型为 null | { left: Tree; right: Tree }，符合预期

方案说明 #

• Fix<F>是纯类型层面的虚拟标记，不存在于最终的Tree类型结构中，赋值时不需要添加任何额外字段
• 该方案是通用的，支持任意返回联合类型、对象类型、基础类型的类型函数的不动点计算，不需要针对特定场景修改逻辑
• 类型展开是按需进行的，只有访问具体属性时才会递归解包对应层级，不会触发类型实例化深度超限错误

内容的提问来源于stack exchange，提问作者polkovnikov.ph