Y 组合子

定义

Y 组合子(Y Combinator)是 λ 演算中最著名的不动点组合子,由 Haskell Curry 发现,定义为 Y = λf.(λx.f (x x)) (λx.f (x x))。它满足 Y f = f (Y f),即能求出任意函数的不动点。

意义

纯 λ 演算中函数都是匿名的,无法通过名字调用自身。Y 组合子解决了这一问题:把"递归体"作为参数传入,由组合子自动完成自我引用,从而证明无名函数系统同样能表达一切递归计算,这是 λ 演算图灵完备性的关键一环。

变体

上述形式只在惰性求值下可用;在严格求值语言中会无限展开,需改用 η-展开后的 Z 组合子。用 JavaScript、Python 等语言手写 Y 组合子是经典的函数式编程练习。

文化影响

Paul Graham 创办的著名创业孵化器 Y Combinator 即以此命名,取"帮助创业者启动自举"的隐喻。