Y组合器从事物的功能方面讲是一种计算机科学概念。 大多数程序员对组合器一无所知，即使他们听说过它们也是如此。
-
什么是Y组合器？
-
组合器如何工作？
-
它们有什么用？
-
它们在程序语言中有用吗？
Y组合器是一种"功能"(在其他功能上运行的功能)，当您不能从自身内部引用该功能时，它可以启用递归。在计算机科学理论中，它概括了递归，抽象了其实现，从而将其与所讨论功能的实际工作区分开。递归函数不需要编译时名称的好处是一种好处。 =)
这适用于支持lambda函数的语言。 Lambda的基于表达式的性质通常意味着它们不能通过名称引用自己。通过声明该变量，对其进行引用，然后为该变量分配lambda来完成自引用循环，可以解决此问题。可以复制lambda变量，并重新分配原始变量，这会破坏自引用。
Y组合器在静态类型的语言(通常是过程语言)中实现和使用起来很麻烦，因为通常类型限制要求在编译时就知道该函数的参数数量。这意味着必须为需要使用的任何参数计数编写一个y-combinator。
以下是在C＃中如何使用和使用Y-Combinator的示例。
使用Y组合器涉及构造递归函数的"异常"方式。首先，您必须将您的函数编写为一段调用预先存在的函数的代码，而不是本身：
1
2
| // Factorial, if func does the same thing as this bit of code...
x == 0 ? 1: x * func(x - 1); |
然后，将其转换为需要调用一个函数的函数，并返回执行此操作的函数。之所以称为功能函数，是因为它接受一个功能，并对其执行操作，从而产生另一个功能。
1
2
3
4
5
6
| // A function that creates a factorial, but only if you pass in
// a function that does what the inner function is doing.
Func<Func<Double, Double>, Func<Double, Double>> fact =
(recurs) =>
(x) =>
x == 0 ? 1 : x * recurs(x - 1); |
现在，您有了一个接受一个函数的函数，并返回了另一个看起来像阶乘的函数，但是它不调用自身，而是调用传递给外部函数的参数。您如何使其成为阶乘？将内部函数传递给自身。 Y-Combinator通过使用具有永久名称的函数来做到这一点，它可以引入递归。
1
2
3
4
5
6
7
8
9
10
11
| // One-argument Y-Combinator.
public static Func<T, TResult> Y<T, TResult>(Func<Func<T, TResult>, Func<T, TResult>> F)
{
return
t => // A function that...
F( // Calls the factorial creator, passing in...
Y(F) // The result of this same Y-combinator function call...
// (Here is where the recursion is introduced.)
)
(t); // And passes the argument into the work function.
} |
除了阶乘调用本身之外，发生的事情是阶乘调用阶乘生成器(由对Y-Combinator的递归调用返回)。并且，根据t的当前值，从生成器返回的函数将再次使用t-1调用生成器，或者仅返回1，终止递归。
它是复杂且神秘的，但是在运行时都会彻底消失，其工作的关键是"延迟执行"，以及拆分递归以覆盖两个功能的过程。内部F作为参数传递，仅在必要时在下一次迭代中调用。
如果您准备长时间阅读，Mike Vanier会提供一个很好的解释。长话短说，它允许您使用不一定本地支持的语言来实现递归。
我已经从http://www.mail-archive.com/boston-pm@mail.pm.org/msg02716.html取消了此操作，这是我几年前写的一个解释。
在此示例中，我将使用JavaScript，但是许多其他语言也可以使用。
我们的目标是能够编写1的递归函数
变量仅使用1个变量的函数而没有
作业，通过名称定义事物等(为什么这是我们的
目标是另一个问题，让我们将此作为
挑战我们。)似乎不可能，是吧？如
例如，让我们实现阶乘。
好吧，第一步就是说，如果我们
被骗了一点。使用2个变量的函数和
分配，我们至少可以避免使用
设置递归。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| // Here's the function that we want to recurse.
X = function (recurse, n) {
if (0 == n)
return 1;
else
return n * recurse(recurse, n - 1);
};
// This will get X to recurse.
Y = function (builder, n) {
return builder(builder, n);
};
// Here it is in action.
Y(
X,
5
); |
现在让我们看看是否可以减少作弊。首先，我们正在使用
作业，但我们不需要。我们可以写X和
Y内联。
1
2
3
4
5
6
7
8
9
10
11
12
| // No assignment this time.
function (builder, n) {
return builder(builder, n);
}(
function (recurse, n) {
if (0 == n)
return 1;
else
return n * recurse(recurse, n - 1);
},
5
); |
但是我们使用2个变量的函数来得到1的函数
变量。我们可以解决这个问题吗？好吧，一个聪明人的名字
Haskell Curry有一个巧妙的窍门，如果您有较高的阶数
函数，那么您只需要1个变量的函数。的
证明您可以从2的函数中获得(或在
一般情况)将变量转换为1个变量
机械文本转换是这样的：
1
2
3
4
5
6
7
8
9
10
11
| // Original
F = function (i, j) {
...
};
F(i,j);
// Transformed
F = function (i) { return function (j) {
...
}};
F(i)(j); |
...保持完全相同。 (这个技巧叫做
发明者"狂奔"。 Haskell语言也是
以Haskell Curry的名字命名。将其归档为无用的琐事。)
现在只要将这种转换应用于任何地方，我们就可以
我们的最终版本。
1
2
3
4
5
6
7
8
9
10
11
12
| // The dreaded Y-combinator in action!
function (builder) { return function (n) {
return builder(builder)(n);
}}(
function (recurse) { return function (n) {
if (0 == n)
return 1;
else
return n * recurse(recurse)(n - 1);
}})(
5
); |
随时尝试。返回的alert()，将其绑定到按钮，无论如何。
该代码无需递归即可递归计算阶乘
2个变量的赋值，声明或函数。 (但
试图追踪其工作方式可能会使您的头部旋转。
并在没有派生的情况下将其重新格式化
将会导致代码令人困惑和困惑。)
您可以将递归定义阶乘的4行替换为
您想要的任何其他递归函数。
我不知道尝试从头开始构建它是否有用。让我们来看看。这是一个基本的递归阶乘函数：
1
2
3
| function factorial(n) {
return n == 0 ? 1 : n * factorial(n - 1);
} |
让我们重构并创建一个名为fact的新函数，该函数将返回一个匿名阶乘计算函数，而不是自己执行计算：
1
2
3
4
5
6
7
| function fact() {
return function(n) {
return n == 0 ? 1 : n * fact()(n - 1);
};
}
var factorial = fact(); |
有点奇怪，但是没错。我们只是在每个步骤中生成一个新的阶乘函数。
此阶段的递归仍然相当明确。 fact函数需要知道其自己的名称。让我们参数化递归调用：
1
2
3
4
5
6
7
8
9
10
11
| function fact(recurse) {
return function(n) {
return n == 0 ? 1 : n * recurse(n - 1);
};
}
function recurser(x) {
return fact(recurser)(x);
}
var factorial = fact(recurser); |
很好，但是recurser仍然需要知道它自己的名称。我们也将其参数化：
1
2
3
4
5
6
7
| function recurser(f) {
return fact(function(x) {
return f(f)(x);
});
}
var factorial = recurser(recurser); |
现在，让我们创建一个返回其结果的包装函数，而不是直接调用recurser(recurser)：
1
2
3
4
5
6
7
| function Y() {
return (function(f) {
return f(f);
})(recurser);
}
var factorial = Y(); |
现在，我们可以完全摆脱recurser名称；它只是Y的内部函数的一个参数，可以用函数本身替换：
1
2
3
4
5
6
7
8
9
10
11
| function Y() {
return (function(f) {
return f(f);
})(function(f) {
return fact(function(x) {
return f(f)(x);
});
});
}
var factorial = Y(); |
唯一仍引用的外部名称是fact，但是现在应该很容易地对其进行参数化，以创建完整的通用解决方案：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| function Y(le) {
return (function(f) {
return f(f);
})(function(f) {
return le(function(x) {
return f(f)(x);
});
});
}
var factorial = Y(function(recurse) {
return function(n) {
return n == 0 ? 1 : n * recurse(n - 1);
};
}); |
上面的大多数答案都描述了Y组合器是什么，但没有描述它的用途。
定点组合器用于显示lambda演算已完成。这在计算理论中是非常重要的结果，并为函数式编程提供了理论基础。
学习定点组合器还帮助我真正地了解了函数编程。不过，我从未在实际编程中发现它们的任何用途。
JavaScript中的y-combinator：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| 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如何做魔术的完整解释，请查看链接文章(不是我本人)。
对于尚未深入了解函数式编程并且不关心立即开始的程序员，但有些好奇：
Y组合器是一个公式，使您可以在函数没有名称但可以作为参数传递，用作返回值以及在其他函数中定义的情况下实现递归。
它通过将函数作为参数传递给自身来工作，因此可以调用自身。
它是lambda微积分的一部分，它实际上是数学，但实际上是一种编程语言，并且对于计算机科学，尤其是函数式编程非常重要。
Y组合器的日常实用价值受到限制，因为编程语言倾向于让您命名函数。
如果您需要在警察队伍中识别它，它看起来像这样：
Y = λf.(λx.f (x x)) (λx.f (x x))
由于重复(λx.f (x x))，通常可以发现它。
λ符号是希腊字母lambda，它使lambda微积分具有其名称，并且有很多(λx.t)样式术语，因为这就是lambda微积分的外观。
其他答案对此提供了非常简洁的答案，没有一个重要事实：您不需要以任何复杂的方式以任何实际语言实现定点组合器，并且这样做没有任何实际目的("我知道Y组合器是什么，除了是")。它是重要的理论概念，但实用价值很小。
匿名递归
定点组合器是根据定义满足等价关系的高阶函数fix
1
| forall f. fix f = f (fix f) |
fix f表示定点方程的解x
自然数的阶乘可以通过以下方式证明
1
2
| fact 0 = 1
fact n = n * fact (n - 1) |
使用fix，可以在没有非一致的自引用的情况下得出关于一般/μ递归函数的任意构造证明。
哪里
1
2
3
| fact' rec n = if n == 0
then 1
else n * rec (n - 1) |
这样
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| 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 |
这种形式上的证明
有条不紊地使用定点组合器等效项进行重写
1
| fix fact' -> fact' (fix fact') |
λ演算
未类型化的lambda演算形式主义在于上下文无关的语法
1
2
3
| E ::= v Variable
| λ v. E Abstraction
| E E Application |
其中v覆盖变量，以及beta和eta减少规则
1
2
| (λ x. B) E -> B[x := E] Beta
λ x. E x -> E if x doesn’t occur free in E Eta |
Beta减少将表达式("参数")E替换为抽象("函数")主体B中变量x的所有自由出现。减少Eta消除了多余的抽象。有时从形式主义中将其省略。不适用归约规则的不可归约表达式为正则或规范形式。
是的简写
(抽象多元性)，
是的简写
(应用程序左关联)，
和
是与alpha等效的。
抽象和应用是lambda演算的两个唯一的"语言原语"，但是它们允许对任意复杂的数据和操作进行编码。
教堂数字是自然数的编码，类似于Peano-axiomatic自然数。
1
2
3
4
5
6
7
8
9
10
| 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
. . . |
正式证明
使用beta减少的重写规则：
1
2
3
4
5
6
7
8
9
| 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演算中，组合器是不包含自由变量的抽象。最简单：I，身份组合器
身份函数同构
这样的组合器是像SKI系统一样的组合器结石的原始运算符。
1
2
3
| S = λ x y z. x z (y z)
K = λ x y. x
I = λ x. x |
Beta减少并未强烈归一化；并非所有可还原的表达式" redexes"在beta还原下都收敛为正常形式。一个简单的例子是omega ω组合器的不同应用
对自己：
1
2
3
4
| (λ x. x x) (λ y. y y)
= (λ y. y y) (λ y. y y)
. . .
= _|_ Bottom |
优先考虑最左边子表达式(" heads")的减少。应用顺序在替换之前将参数标准化，而正常顺序则不会。这两种策略类似于热切的评估，例如C和惰性评估，例如哈斯克尔。
1
2
| K (I a) (ω ω)
= (λ k l. k) ((λ i. i) a) ((λ x. x x) (λ y. y y)) |
在急切的应用顺序Beta减少下产生分歧
1
2
3
4
5
| = (λ 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))
. . .
= _|_ |
因为严格的语义
但收敛于懒惰的正序beta减少
1
2
3
| = (λ l. ((λ i. i) a)) ((λ x. x x) (λ y. y y))
= (λ l. a) ((λ x. x x) (λ y. y y))
= a |
如果表达式具有正常形式，则可以找到正常顺序的beta减少形式。
?
Y定点组合器的基本属性
1
| λ f. (λ x. f (x x)) (λ x. f (x x)) |
是(谁)给的
1
2
3
4
5
6
| 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))
. . . . . . |
等价
同构
未类型化的lambda演算可以对通用/μ递归函数上的任意构造性证明进行编码。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| 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 |
(乘法延迟，合流)
对于丘吉尔式无类型lambda演算，除Y外，还存在定点组合器的递归可枚举无穷大。
1
2
3
4
5
| 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中，定点组合器可以轻松实现
1
2
| fix :: forall t. (t -> t) -> t
fix f = f (fix f) |
在评估所有子表达式之前，Haskell的懒惰会归一化为无穷大。
1
2
3
4
5
6
| primes :: Integral t => [t]
primes = sieve [2 ..]
where
sieve = fix (\ rec (p : ns) ->
p : rec [n | n <- ns
, n `rem` p /= 0]) |
-
大卫·特纳(David Turner)：丘奇的论文和函数式编程
-
阿隆佐·丘奇：基本数论的一个无法解决的问题
-
λ演算
-
丘奇-罗瑟定理
Y组合器是磁通电容器的另一个名称。
这是Y-Combinator和Factorial函数的JavaScript实现(摘自Douglas Crockford的文章，网址为：http://javascript.crockford.com/little.html)。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| 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); |
我已经在Clojure和Scheme中为Y-Combinator编写了一种"白痴指南"，以帮助自己掌握它。他们受到"小策划者"中材料的影响
在方案中：
https://gist.github.com/z5h/238891
或Clojure：
https://gist.github.com/z5h/5102747
这两篇教程的代码都散布着注释，应该剪切并粘贴到您喜欢的编辑器中。
以下是根据尼古拉斯·曼库索(Nicholas Mancuso)的答案中提到的文章(总计值得一读)汇编的原始问题的答案，以及其他答案：
What is a Y-combinator?
Y组合器是一个"函数"(或一个高阶函数，即在其他函数上运行的函数)，它带有一个参数(该函数不是递归的)，并返回该函数的一个版本，即递归的。
有点递归=)，但更深入的定义：
组合器-只是没有自由变量的lambda表达式。
自由变量—是不是绑定变量的变量。
绑定变量-包含在以该变量名作为其自变量之一的lambda表达式内的变量。
考虑这种情况的另一种方法是，combinator是这样的lambda表达式，您可以在其中找到其定义的地方替换其名称，并使一切仍然正常工作(如果combinator可能会陷入无限循环)在lambda体内包含对自身的引用)。
Y组合器是定点组合器。
函数的不动点是函数域的元素，该域由函数映射到自身。
也就是说，如果f(c) = c，c是函数f(x)的固定点
这意味着f(f(...f(c)...)) = fn(c) = c
How do combinators work?
下面的示例假定使用强类型+动态类型：
惰性(常规)Y组合器：
此定义适用于具有延迟(也称为：延迟，按需调用)评估的语言-评估策略，该评估策略将对表达式的评估延迟到需要其值为止。
1
| 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组合器：
此定义适用于具有严格(也包括：急切，贪婪)评估的语言-一种评估策略，在该策略中，将表达式绑定到变量后立即对其进行评估。
1
| 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的身体评估。我问了另一个问题，与这个话题有些相关。
What are they good for?
克里斯·阿默曼(Chris Ammerman)从答案中借来的 Stolen ：Y-combinator概括了递归，将其实现抽象化，从而将其与相关功能的实际工作区分开。
尽管Y-combinator有一些实际应用，但它主要是一个理论概念，对它的理解将扩大您的总体视野，并有可能增加您的分析和开发技能。
Are they useful in procedural languages?
正如Mike Vanier所说：可以用许多静态类型的语言定义Y组合器，但是(至少在我所看到的示例中)这样的定义通常需要一些非显而易见的类型的黑客，因为Y组合器本身不需要具有简单的静态类型。这超出了本文的范围，因此我不再赘述
就像克里斯·阿默曼(Chris Ammerman)提到的那样：大多数程序语言都具有静态类型。
因此，请回答这个问题-并非如此。
作为组合器的新手，我发现Mike Vanier的文章(感谢Nicholas Mancuso)确实很有帮助。除了记录我的理解之外，我还想写一个摘要，如果对其他人有帮助，我将非常高兴。
好。
从胡扯到少胡扯
以阶乘为例，我们使用以下almost-factorial函数来计算数字x的阶乘：
好。
1
2
3
| 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接受了cr脚版本的阶乘函数(只能计算直到编号x - 1)，并返回了-脚程度较低的阶乘函数(计算到数量x)。以这种形式：
好。
1
| almost-factorial crappy-f = less-crappy-f |
如果我们反复将不那么糟糕的阶乘传递给almost-factorial，我们最终将获得所需的阶乘函数f。可以认为是：
好。
定点
almost-factorial f = f表示f的事实是功能almost-factorial的固定点。
好。
这是查看上面函数之间关系的一种非常有趣的方式，对我来说这是一个愚蠢的时刻。 (如果没有，请阅读Mike关于定点的文章)
好。
三种功能
概括地说，我们有一个非递归函数fn(就像我们的几乎阶乘)，我们有它的定点函数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来获得结果
Y fn = fr，Y返回函数的固定点，Y将几乎有用的函数fn转换为有用的fr
好。
导出Y(不包括)
我将跳过Y的派生，然后去理解Y。 Mike Vainer的帖子有很多细节。
好。
Y的形式
Y定义为(以lambda演算格式)：
好。
1
| Y f = λs.(f (s s)) λs.(f (s s)) |
如果我们替换函数左侧的变量s，我们得到
好。
1
2
3
| 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)仅采用一个参数，例如阶乘函数。
好。
1
| def fn fr x = accumulate x (fr (- x 1)) |
从fn fr = fr开始，我们继续
好。
1
2
3
| => 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：
好。
1
2
| fr = Y fn = λs.(fn (s s)) λs.(fn (s s))
=> fn (λs.(fn (s s)) λs.(fn (s s))) |
所以
好。
1
| 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定义了真正的业务逻辑。 Y基于fn创建fr(一种特定形式的辅助函数)，以递归的方式简化对fn的计算。
好。
它现在帮助我以这种方式理解Y，希望对您有所帮助。
好。
顺便说一句，我还发现《通过Lambda微积分进行函数式编程入门》一书非常好，我只是其中一部分，而我无法理解Y一书的事实促使我撰写了这篇文章。
好。
好。
y-combinator实现匿名递归。所以代替
1
| function fib( n ){ if( n<=1 ) return n; else return fib(n-1)+fib(n-2) } |
你可以做
1
| function ( fib, n ){ if( n<=1 ) return n; else return fib(n-1)+fib(n-2) } |
当然，y-combinator仅适用于按名字呼叫的语言。如果要以任何普通的按值调用语言使用此功能，则需要相关的z组合器(y组合器将发散/无限循环)。
该操作员可以简化您的生活：
1
2
3
4
5
6
7
8
9
| var Y = function(f) {
return (function(g) {
return g(g);
})(function(h) {
return function() {
return f.apply(h(h), arguments);
};
});
}; |
然后，避免使用额外的功能：
1
2
3
| var fac = Y(function(n) {
return n == 0 ? 1 : n * this(n - 1);
}); |
最后，您调用fac(5)。
定点组合器(或定点运算符)是计算其他函数的定点的高阶函数。此操作与编程语言理论有关，因为它允许以重写规则的形式实现递归，而无需该语言的运行时引擎的明确支持。 (src维基百科)
我认为回答这个问题的最好方法是选择一种语言，例如JavaScript：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| 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解决的问题。
