是否可以实现TypeScript泛型版本的Y-combinator？

结论 #

完全可以实现TypeScript泛型版本的Y组合子，分为类型层面的Y组合子（对应你提问的type Y<F>）和带类型标注的运行时Y组合子函数两类实现，具体如下：

一、类型层面的Y组合子 #

TypeScript 3.7+ 支持递归类型别名，结合高阶类型（HKT）的模拟方案即可实现：

// 1. 先定义高阶类型(HKT)的基础约束，用于模拟TS原生不支持的泛型参数传递
type HKT = { type: unknown }
type Apply<F extends HKT, T> = (F & { type: T })['type']

// 2. Y组合子类型实现：返回泛型F的不动点，满足 Y<F> = F<Y<F>>
type Y<F extends HKT> = Apply<F, Y<F>>

使用示例

用Y组合子定义递归的链表类型：

// 定义链表的类型构造器
interface ListF<T> extends HKT {
  type: null | { head: T; tail: this['type'] }
}
// 用Y组合子生成递归的List类型，等价于 type List<T> = null | { head: T; tail: List<T> }
type List<T> = Y<ListF<T>>

二、带类型标注的运行时Y组合子函数 #

和你给出的JavaScript版本逻辑完全一致，仅补充了递归类型定义满足TS的类型检查：

// 定义递归函数类型，解决x(x)调用的类型标注问题
type RecursiveFunc<F> = (x: RecursiveFunc<F>) => F
const Y = <F,>(f: (g: F) => F): F => {
  const g = (x: RecursiveFunc<F>): F => f(x(x))
  return g(g)
}

使用示例

用Y组合子实现阶乘函数：

// 阶乘工厂函数
const factFactory = (fact: (n: number) => number) => {
  return (n: number) => n <= 1 ? 1 : n * fact(n - 1)
}
// 生成无外部引用的递归阶乘函数
const fact = Y(factFactory)
console.log(fact(5)) // 输出 120

内容的提问来源于stack exchange，提问作者aztack