什么是 Y 组合器？ [关闭]

上面的大多数答案都描述了 Y 组合器的用途，但没有描述它的用途。

Fixed point combinators 用于表明 lambda calculus 是 turing complete。这是计算理论中一个非常重要的结果，为functional programming提供了理论基础。

学习定点组合器也帮助我真正理解了函数式编程。不过，我在实际编程中从未发现它们有任何用途。

---

对于没有深入接触过函数式编程的程序员，也不想从现在开始，但有点好奇：

组合子是一个公式，它允许您在函数不能有名称但可以作为参数传递、用作返回值以及在其他函数中定义的情况下实现递归。

它通过将函数作为参数传递给自身来工作，因此它可以调用自身。

它是 lambda 演算的一部分，它实际上是数学，但实际上是一种编程语言，对于计算机科学尤其是函数式编程非常基础。

Y 组合器的日常实用价值是有限的，因为编程语言倾向于让您命名函数。

如果您需要在警察阵容中识别它，它看起来像这样：

Y = λf.(λx.f (xx)) (λx.f (xx))

由于重复的 (λx.f (x x))，您通常可以发现它。

λ 符号是希腊字母 lambda，它给出了 lambda 演算的名称，并且有很多 (λx.t) 样式术语，因为这就是 lambda 演算的样子。

---

JavaScript 中的 y 组合器：

var Y = function(f) {
  return (function(g) {
    return g(g);
  })(function(h) {
    return function() {
      return f(h(h)).apply(null, arguments);
    };
  });
};

var factorial = Y(function(recurse) {
  return function(x) {
    return x == 0 ? 1 : x * recurse(x-1);
  };
});

factorial(5)  // -> 120

编辑：我从查看代码中学到了很多东西，但是如果没有一些背景，这有点难以接受 - 对此感到抱歉。借助其他答案提供的一些一般知识，您可以开始区分正在发生的事情。

Y 函数是“y 组合器”。现在看一下使用 Y 的 var factorial 行。请注意，您将一个函数传递给它，该函数有一个参数（在本例中为 recurse），该参数稍后也会在内部函数中使用。参数名称基本上成为内部函数的名称，允许它执行递归调用（因为它在其定义中使用 recurse()。）y 组合器执行将其他匿名内部函数与参数名称相关联的魔力传递给 Y 的函数。

有关 Y 如何发挥魔力的完整说明，请查看 linked article（顺便说一句，不是我。）

---

匿名递归

定点组合器是一个高阶函数 fix，根据定义满足等价

forall f.  fix f  =  f (fix f)

fix f 表示定点方程的解 x

               x  =  f x

自然数的阶乘可以证明为

fact 0 = 1
fact n = n * fact (n - 1)

使用 fix，可以在没有匿名自引用的情况下推导出对一般/μ-递归函数的任意建设性证明。

fact n = (fix fact') n

在哪里

fact' rec n = if n == 0
                then 1
                else n * rec (n - 1)

这样

   fact 3
=  (fix fact') 3
=  fact' (fix fact') 3
=  if 3 == 0 then 1 else 3 * (fix fact') (3 - 1)
=  3 * (fix fact') 2
=  3 * fact' (fix fact') 2
=  3 * if 2 == 0 then 1 else 2 * (fix fact') (2 - 1)
=  3 * 2 * (fix fact') 1
=  3 * 2 * fact' (fix fact') 1
=  3 * 2 * if 1 == 0 then 1 else 1 * (fix fact') (1 - 1)
=  3 * 2 * 1 * (fix fact') 0
=  3 * 2 * 1 * fact' (fix fact') 0
=  3 * 2 * 1 * if 0 == 0 then 1 else 0 * (fix fact') (0 - 1)
=  3 * 2 * 1 * 1
=  6

这个正式的证明

fact 3  =  6

有条不紊地使用定点组合器等价进行重写

fix fact'  ->  fact' (fix fact')

Lambda演算

无类型 lambda 演算形式主义包括上下文无关文法

E ::= v        Variable
   |  λ v. E   Abstraction
   |  E E      Application

其中 v 涵盖变量，以及 beta 和 eta 缩减 规则

(λ x. B) E  ->  B[x := E]                                 Beta
  λ x. E x  ->  E          if x doesn’t occur free in E   Eta

Beta 减少将抽象（“函数”）主体 B 中变量 x 的所有自由出现替换为表达式（“参数”）E。 Eta 减少消除了冗余抽象。它有时会从形式主义中省略。一个 irreducible 表达式（不适用任何归约规则）是 normal 或 canonical 形式。

λ x y. E

是简写

λ x. λ y. E

（抽象多元性），

E F G

是简写

(E F) G

（应用程序左关联性），

λ x. x

和

λ y. y

是 alpha 等效的。

抽象和应用是 lambda 演算中仅有的两个“语言原语”，但它们允许对任意复杂的数据和操作进行编码。

Church 数字是自然数的编码，类似于 Peano-axiomatic naturals。

   0  =  λ f x. x                 No application
   1  =  λ f x. f x               One application
   2  =  λ f x. f (f x)           Twofold
   3  =  λ f x. f (f (f x))       Threefold
    . . .

SUCC  =  λ n f x. f (n f x)       Successor
 ADD  =  λ n m f x. n f (m f x)   Addition
MULT  =  λ n m f x. n (m f) x     Multiplication
    . . .

正式证明

1 + 2  =  3

使用 beta 减少的重写规则：

   ADD                      1            2
=  (λ n m f x. n f (m f x)) (λ g y. g y) (λ h z. h (h z))
=  (λ m f x. (λ g y. g y) f (m f x)) (λ h z. h (h z))
=  (λ m f x. (λ y. f y) (m f x)) (λ h z. h (h z))
=  (λ m f x. f (m f x)) (λ h z. h (h z))
=  λ f x. f ((λ h z. h (h z)) f x)
=  λ f x. f ((λ z. f (f z)) x)
=  λ f x. f (f (f x))                                       Normal form
=  3

组合器

在 lambda 演算中，combinators 是不包含自由变量的抽象。最简单的：I，身份组合子

λ x. x

与恒等函数同构

id x = x

这样的组合子是组合子演算的原始算子，如 SKI 系统。

S  =  λ x y z. x z (y z)
K  =  λ x y. x
I  =  λ x. x

Beta 减少不是强标准化；并非所有可约表达式，“redexes”，在 beta 约简下都收敛到范式。一个简单的例子是 omega ω 组合子的不同应用

λ x. x x

对自己：

   (λ x. x x) (λ y. y y)
=  (λ y. y y) (λ y. y y)
. . .
=  _|_                     Bottom

优先减少最左边的子表达式（“头”）。应用顺序在替换之前规范化参数，正常顺序不会。这两种策略类似于急切求值（例如 C）和惰性求值（例如 Haskell）。

   K          (I a)        (ω ω)
=  (λ k l. k) ((λ i. i) a) ((λ x. x x) (λ y. y y))

在急切的应用阶贝塔减少下发散

=  (λ k l. k) a ((λ x. x x) (λ y. y y))
=  (λ l. a) ((λ x. x x) (λ y. y y))
=  (λ l. a) ((λ y. y y) (λ y. y y))
. . .
=  _|_

因为在严格的语义中

forall f.  f _|_  =  _|_

但在惰性正态贝塔归约下收敛

=  (λ l. ((λ i. i) a)) ((λ x. x x) (λ y. y y))
=  (λ l. a) ((λ x. x x) (λ y. y y))
=  a

如果表达式具有范式，则正常阶的 beta 归约会找到它。

是

Y 定点组合子的基本属性

λ f. (λ x. f (x x)) (λ x. f (x x))

是（谁）给的

   Y g
=  (λ f. (λ x. f (x x)) (λ x. f (x x))) g
=  (λ x. g (x x)) (λ x. g (x x))           =  Y g
=  g ((λ x. g (x x)) (λ x. g (x x)))       =  g (Y g)
=  g (g ((λ x. g (x x)) (λ x. g (x x))))   =  g (g (Y g))
. . .                                      . . .

等价性

Y g  =  g (Y g)

同构于

fix f  =  f (fix f)

无类型的 lambda 演算可以对一般/μ-递归函数的任意建设性证明进行编码。

 FACT  =  λ n. Y FACT' n
FACT'  =  λ rec n. if n == 0 then 1 else n * rec (n - 1)

   FACT 3
=  (λ n. Y FACT' n) 3
=  Y FACT' 3
=  FACT' (Y FACT') 3
=  if 3 == 0 then 1 else 3 * (Y FACT') (3 - 1)
=  3 * (Y FACT') (3 - 1)
=  3 * FACT' (Y FACT') 2
=  3 * if 2 == 0 then 1 else 2 * (Y FACT') (2 - 1)
=  3 * 2 * (Y FACT') 1
=  3 * 2 * FACT' (Y FACT') 1
=  3 * 2 * if 1 == 0 then 1 else 1 * (Y FACT') (1 - 1)
=  3 * 2 * 1 * (Y FACT') 0
=  3 * 2 * 1 * FACT' (Y FACT') 0
=  3 * 2 * 1 * if 0 == 0 then 1 else 0 * (Y FACT') (0 - 1)
=  3 * 2 * 1 * 1
=  6

（乘法延迟，汇合）

对于 Churchian 无类型 lambda 演算，除了 Y 之外，已经证明存在递归可枚举的无穷大定点组合子。

 X  =  λ f. (λ x. x x) (λ x. f (x x))
Y'  =  (λ x y. x y x) (λ y x. y (x y x))
 Z  =  λ f. (λ x. f (λ v. x x v)) (λ x. f (λ v. x x v))
 Θ  =  (λ x y. y (x x y)) (λ x y. y (x x y))
  . . .

正常阶 beta 减少使未扩展的无类型 lambda 演算成为图灵完备的重写系统。

在 Haskell 中，定点组合器可以优雅地实现

fix :: forall t. (t -> t) -> t
fix f = f (fix f)

在评估所有子表达式之前，Haskell 的惰性规范化为一个有限值。

primes :: Integral t => [t]
primes = sieve [2 ..]
   where
      sieve = fix (\ rec (p : ns) ->
                     p : rec [n | n <- ns
                                , n `rem` p /= 0])

David Turner：Church 的论文和函数式编程

Alonzo Church：初等数论的一个无法解决的问题

Lambda演算

Church-Rosser 定理

---

其他答案对此提供了非常简洁的答案，但没有一个重要的事实：您不需要以这种复杂的方式以任何实用语言实现定点组合器，这样做没有任何实际目的（除了“看，我知道 Y 组合器是”）。这是一个重要的理论概念，但没有什么实用价值。

---

这是 Y-Combinator 和 Factorial 函数的 JavaScript 实现（来自 Douglas Crockford 的文章，可在：http://javascript.crockford.com/little.html 获得）。

function Y(le) {
    return (function (f) {
        return f(f);
    }(function (f) {
        return le(function (x) {
            return f(f)(x);
        });
    }));
}

var factorial = Y(function (fac) {
    return function (n) {
        return n <= 2 ? n : n * fac(n - 1);
    };
});

var number120 = factorial(5);

---

Y-Combinator 是磁通电容器的另一个名称。

---

我已经在 Clojure 和 Scheme 中为 Y-Combinator 编写了一种“白痴指南”，以帮助自己掌握它。他们受到“小阴谋家”中材料的影响

在方案中：https://gist.github.com/z5h/238891

或 Clojure：https://gist.github.com/z5h/5102747

这两篇教程都是代码中散布着注释，应该剪切和粘贴到你最喜欢的编辑器中。

---

作为组合器的新手，我发现 Mike Vanier's article（感谢 Nicholas Mancuso）非常有帮助。我想写一个总结，除了记录我的理解之外，如果它可以帮助其他人，我会很高兴。

从蹩脚到不那么蹩脚

以阶乘为例，我们使用下面的 almost-factorial 函数来计算数 x 的阶乘：

def almost-factorial f x = if iszero x
                           then 1
                           else * x (f (- x 1))

在上面的伪代码中，almost-factorial 接受函数 f 和数字 x（almost-factorial 是柯里化的，因此可以看作是接受函数 f 并返回一个 1-arity 函数）。

当 almost-factorial 计算 x 的阶乘时，它将 x - 1 的阶乘计算委托给函数 f 并将结果与 x 累加（在这种情况下，它将 (x - 1) 的结果与X）。

可以看作 almost-factorial 接受了一个 crappy 版本的阶乘函数（只能计算到数字 x - 1）并返回一个 less-crappy 版本的阶乘（计算直到数字 x）。如这种形式：

almost-factorial crappy-f = less-crappy-f

如果我们反复将 less-crappy 版本的阶乘传递给 almost-factorial，我们最终将获得所需的阶乘函数 f。它可以被认为是：

almost-factorial f = f

固定点

almost-factorial f = f 表示 f 的事实是函数 almost-factorial 的fix-point。

这是查看上述函数关系的一种非常有趣的方式，这对我来说是一个惊喜时刻。 （如果你还没有，请阅读 Mike 关于定点的帖子）

三个功能

概括地说，我们有一个非递归函数fn（就像我们的几乎阶乘），我们有它的fix-point函数fr（就像我们的f） ，那么 Y 所做的就是当你给 Y fn 时，Y 返回 fn 的不动点函数。

所以总而言之（通过假设 fr 只接受一个参数来简化；x 在递归中退化为 x - 1、x - 2...）：

我们将核心计算定义为 fn： def fn fr x = ...accumulate x with result from (fr (- x 1))，这是几乎有用的函数 - 虽然我们不能直接在 x 上使用 fn，但它会是很快有用。这个非递归 fn 使用一个函数 fr 来计算它的结果

fn fr = fr，fr 是 fn 的不动点，fr 是有用的函数，我们可以在 x 上使用 fr 来得到我们的结果

fn = fr，Y 返回函数的不动点，Y 将我们几乎有用的函数 fn 变成有用的 fr

推导 Y（不包括在内）

我将跳过 Y 的推导并去理解 Y。 Mike Vainer 的帖子有很多细节。

Y的形式

Y 定义为（lambda 演算 格式）：

Y f = λs.(f (s s)) λs.(f (s s))

如果我们替换函数左侧的变量 s，我们得到

Y f = λs.(f (s s)) λs.(f (s s))
=> f (λs.(f (s s)) λs.(f (s s)))
=> f (Y f)

所以确实，(Y f) 的结果是 f 的不动点。

为什么 (Y f) 有效？

根据 f 的签名，(Y f) 可以是任意元的函数，为了简化，我们假设 (Y f) 只接受一个参数，就像我们的阶乘函数一样。

def fn fr x = accumulate x (fr (- x 1))

从 fn fr = fr 开始，我们继续

=> accumulate x (fn fr (- x 1))
=> accumulate x (accumulate (- x 1) (fr (- x 2)))
=> accumulate x (accumulate (- x 1) (accumulate (- x 2) ... (fn fr 1)))

当最里面的 (fn fr 1) 是基本情况并且 fn 在计算中不使用 fr 时，递归计算终止。

再次查看 Y：

fr = Y fn = λs.(fn (s s)) λs.(fn (s s))
=> fn (λs.(fn (s s)) λs.(fn (s s)))

所以

fr x = Y fn x = fn (λs.(fn (s s)) λs.(fn (s s))) x

对我来说，这个设置的神奇部分是：

fn 和 fr 相互依赖：fr 在内部“包裹”fn，每次使用 fr 计算 x 时，它都会“生成”（“提升”？）一个 fn 并将计算委托给该 fn（传入 fr 和 x );另一方面，fn 依赖于 fr 并使用 fr 来计算较小问题 x-1 的结果。

在使用 fr 定义 fn 时（当 fn 在其操作中使用 fr 时），尚未定义真正的 fr。

是 fn 定义了真正的业务逻辑。在 fn 的基础上，Y 创建了 fr - 一个特定形式的辅助函数 - 以方便以递归方式计算 fn。

它帮助我目前以这种方式理解 Y，希望它有所帮助。

顺便说一句，我还发现这本书 An Introduction to Functional Programming Through Lambda Calculus 非常好，我只是参与其中，而且我无法理解书中 Y 的事实导致我写了这篇文章。

---

以下是从 answer by Nicholas Mancuso 中提到的 the article（完全值得一读）编译而来的 original questions 的答案以及其他答案：

什么是 Y 组合器？

Y-combinator 是一个“函数式”（或高阶函数——一个对其他函数进行操作的函数），它接受一个参数，这是一个非递归函数，并返回该函数的一个版本递归的。

有点递归=），但更深入的定义：

组合器——只是一个没有自由变量的 lambda 表达式。自由变量——是一个不是绑定变量的变量。绑定变量 — 包含在 lambda 表达式主体内的变量，该变量名称作为其参数之一。

另一种思考方式是，combinator 就是这样一个 lambda 表达式，在其中你可以在任何地方用它的定义替换组合器的名称，并且一切仍然有效（如果组合器会包含对自身的引用，在 lambda 主体内）。

Y-combinator 是一个定点组合器。

函数的不动点是函数域中由函数映射到自身的元素。
也就是说c是函数f(x)的一个不动点如果f(c) = c
这意味着f(f(...f(c)...)) = fn(c) = c

组合器如何工作？

下面的示例假设强+动态类型：

惰性（正常顺序）Y 组合器：此定义适用于具有惰性（也：延迟，按需调用）评估的语言 - 一种评估策略，它将表达式的评估延迟到需要它的值为止。

Y = λf.(λx.f(x x)) (λx.f(x x)) = λf.(λx.(x x)) (λx.f(x x))

这意味着，对于给定的函数f（它是一个非递归函数），可以通过计算λx.f(x x)，然后将这个lambda表达式应用到自身来获得对应的递归函数。

严格（应用顺序）Y 组合器：此定义适用于具有严格（也：急切、贪婪）评估的语言——其中表达式一绑定到变量就被评估的评估策略。

Y = λf.(λx.f(λy.((x x) y))) (λx.f(λy.((x x) y))) = λf.(λx.(x x)) (λx.f(λy.((x x) y)))

它本质上与惰性相同，只是有一个额外的 λ 包装器来延迟 lambda 的主体评估。我问过 another question，与此主题有些相关。

它们有什么用？

Stolen 借自 answer by Chris Ammerman：Y-combinator 泛化递归，抽象其实现，从而将其与相关函数的实际工作分离。

尽管 Y-combinator 有一些实际应用，但它主要是一个理论概念，对它的理解将扩大您的整体视野，并可能提高您的分析和开发技能。

它们在程序语言中有用吗？

作为 stated by Mike Vanier： 可以在许多静态类型语言中定义 Y 组合子，但是（至少在我见过的示例中）这样的定义通常需要一些不明显的类型骇客，因为Y 组合器本身没有简单的静态类型。这超出了本文的范围，所以我不再赘述

正如 mentioned by Chris Ammerman：大多数过程语言都有静态类型。

所以回答这个问题 - 不是真的。

---

定点组合器（或定点运算符）是计算其他函数的不动点的高阶函数。此操作与编程语言理论相关，因为它允许以重写规则的形式实现递归，而无需语言运行时引擎的明确支持。 （来源维基百科）

---

y-combinator 实现匿名递归。所以而不是

function fib( n ){ if( n<=1 ) return n; else return fib(n-1)+fib(n-2) }

你可以做

function ( fib, n ){ if( n<=1 ) return n; else return fib(n-1)+fib(n-2) }

当然，y-combinator 仅适用于按名称调用的语言。如果您想在任何普通的按值调用语言中使用它，那么您将需要相关的 z-combinator（y-combinator 将发散/无限循环）。

---

this-operator 可以简化你的生活：

var Y = function(f) {
    return (function(g) {
        return g(g);
    })(function(h) {
        return function() {
            return f.apply(h(h), arguments);
        };
    });
};

然后你避免额外的功能：

var fac = Y(function(n) {
    return n == 0 ? 1 : n * this(n - 1);
});

最后，您调用 fac(5)。

---

我认为回答这个问题的最好方法是选择一种语言，比如 JavaScript：

function factorial(num)
{
    // If the number is less than 0, reject it.
    if (num < 0) {
        return -1;
    }
    // If the number is 0, its factorial is 1.
    else if (num == 0) {
        return 1;
    }
    // Otherwise, call this recursive procedure again.
    else {
        return (num * factorial(num - 1));
    }
}

现在重写它，使它不使用函数内部的函数名，但仍然递归调用它。

唯一应该看到函数名称 factorial 的地方是调用站点。

提示：不能使用函数名，但可以使用参数名。

解决问题。不要查。一旦你解决了它，你就会明白 y-combinator 解决了什么问题。

---