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

编辑: 通过查看代码，我学到了很多东西，但是如果没有一些背景知识，这个代码有点难以理解——对此我感到抱歉。有了其他答案提供的一些常识，你就可以开始分析正在发生的事情了。

The Y function is the "y-combinator". Now take a look at the var factorial line where Y is used. Notice you pass a function to it that has a parameter (in this example, recurse) that is also used later on in the inner function. The parameter name basically becomes the name of the inner function allowing it to perform a recursive call (since it uses recurse() in it's definition.) The y-combinator performs the magic of associating the otherwise anonymous inner function with the parameter name of the function passed to Y.

关于Y如何变魔术的完整解释，请查看链接文章(顺便说一下，不是我写的)。

以下是对尼古拉斯·曼库索(Nicholas Mancuso)在回答中提到的文章(完全值得一读)中提到的原始问题的回答，以及其他答案:

什么是y组合子?

y组合子是一个“函数”(或高阶函数——一个作用于其他函数的函数)，它接受一个参数，这是一个非递归的函数，并返回该函数的一个递归版本。

---

有点递归=)，但更深入的定义:

一个组合子-就是一个没有自由变量的lambda表达式。 自由变量-是一个变量，不是一个约束变量。 绑定变量—包含在lambda表达式体中的变量，该变量名作为其参数之一。

另一种思考方式是，combinator是这样一个lambda表达式，在其中，你可以在任何地方用它的定义替换一个组合子的名称，并且一切都仍然有效(如果combinator在lambda体中包含对自身的引用，你将进入一个无限循环)。

y组合子是一个定点组合子。

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

组合符是如何工作的?

下面的例子假设强+动态类型:

惰性(正规阶)y组合子: 此定义适用于具有lazy(也称为deferred, call-by-need)求值的语言——该求值策略将表达式的求值延迟到需要它的值时。

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

这意味着，对于给定的函数f(它是非递归函数)，可以通过计算λx得到对应的递归函数。F (x x)然后把这个表达式应用到自身上。

严格(应用阶)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)))

它本质上和lazy一样，只是有一个额外的λ包装器来延迟lambda的体计算。我问了另一个问题，和这个话题有点相关。

它们有什么用?

借用Chris Ammerman的回答:Y-combinator泛化递归，抽象其实现，从而将其与函数的实际工作分离。

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

它们在过程语言中有用吗?

正如Mike Vanier所说:在许多静态类型的语言中都可以定义Y组合子，但是(至少在我看到的例子中)这样的定义通常需要一些不明显的类型技巧，因为Y组合子本身没有直接的静态类型。这超出了本文的范围，所以我不再进一步提及

正如Chris Ammerman所提到的:大多数过程式语言都有静态类型。

所以这个问题的答案是，不是真的。

作为一个组合子的新手，我发现Mike Vanier的文章(感谢Nicholas Mancuso)真的很有帮助。我想写一个总结，除了记录我的理解，如果它能对其他人有所帮助，我将非常高兴。

从糟糕到不那么糟糕

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

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

在上面的伪代码中，almost-阶乘接受函数f和数字x (almost-阶乘是curry的，所以它可以被视为接受函数f并返回一个1-arity函数)。

当almost-factorial计算x的阶乘时，它将x - 1的阶乘计算委托给函数f，并将该结果与x相加(在本例中，它将(x - 1)的结果与x相乘)。

它可以被看作是almost-阶乘接受了一个蹩脚的阶乘函数(它只能计算到数字x - 1)，并返回一个不那么蹩脚的阶乘(计算到数字x)。如下形式:

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

如果我们反复地将阶乘的不那么糟糕的版本传递给almost阶乘，我们最终会得到我们想要的阶乘函数f。其中可以考虑为:

almost-factorial f = f

Fix-point

几乎阶乘f = f意味着f是几乎阶乘函数的定点。

这是一种非常有趣的方式来看待上述函数之间的关系，对我来说是一个顿悟的时刻。(如果你还没读过，请阅读Mike关于fix-point的文章)

三个函数

概括地说，我们有一个非递归函数fn(就像我们的几乎阶乘)，我们有它的定点函数fr(就像我们的f)然后Y所做的是当你给Y fn, Y返回fn的定点函数。

总之(通过假设fr只有一个参数来简化;X退化为X - 1, X - 2…在递归):

我们将核心计算定义为fn: def fn fr x =…将x与result from (fr (- x1))累加，这是一个几乎有用的函数-尽管我们不能直接在x上使用fn，但它很快就会有用。这个非递归fn使用一个函数fr来计算它的结果 fnfr = fr, fr是Fn的定点，fr是有用的函数，我们可以用fr作用于x来得到结果 Y 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)

所以(yf)的结果就是f的定点。

(yf)为什么成立?

根据f的特征，(Y f)可以是任意arity的函数，为了简化，我们假设(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)))

So

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

对我来说，这种设置的神奇之处在于:

fn and fr interdepend on each other: fr 'wraps' fn inside, every time fr is used to calculate x, it 'spawns' ('lifts'?) an fn and delegates the calculation to that fn (passing in itself fr and x); on the other hand, fn depends on fr and uses fr to calculate result of a smaller problem x-1. At the time fr is used to define fn (when fn uses fr in its operations), the real fr is not yet defined. It's fn which defines the real business logic. Based on fn, Y creates fr - a helper function in a specific form - to facilitate the calculation for fn in a recursive manner.

它帮助我现在这样理解Y，希望有帮助。

顺便说一句，我还发现《通过Lambda微积分介绍函数式编程》这本书非常好，我只读了一部分，事实上，我无法理解书中的Y，这让我想到了这篇文章。

Y-combinator是一个“函数”(一个作用于其他函数的函数)，当你不能从内部引用函数时，它可以实现递归。在计算机科学理论中，它概括了递归，抽象了递归的实现，从而将递归与函数的实际工作分离开来。递归函数不需要编译时名称的好处是一种额外的好处。=）

这适用于支持lambda函数的语言。lambdas基于表达式的特性通常意味着它们不能通过名称引用自己。通过声明变量，引用它，然后赋值给它，来完成自引用循环，是很脆弱的。可以复制lambda变量，并重新分配原始变量，这将破坏自引用。

y组合子在静态类型语言(过程性语言通常如此)中实现起来很麻烦，而且经常使用起来也很麻烦，因为通常类型限制要求在编译时知道函数的参数数量。这意味着必须为需要使用的任何参数count编写y-combinator。

下面是一个在c#中如何使用和工作的Y-Combinator的例子。

使用y组合子涉及到一种构造递归函数的“不寻常”方式。首先，你必须把你的函数写成一段代码，调用一个已经存在的函数，而不是它自己:

// Factorial, if func does the same thing as this bit of code...
x == 0 ? 1: x * func(x - 1);

然后将其转换为一个函数，该函数接受一个要调用的函数，并返回一个这样做的函数。这被称为函数，因为它接受一个函数，并对其执行一个操作，该操作产生另一个函数。

// 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就是这样做的，它是一个具有永久名称的函数，可以引入递归。

// 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作为参数传递，仅在必要时才在下一次迭代中调用。

y组合子实现匿名递归。所以与其

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将发散/无限循环)。

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

编辑: 通过查看代码，我学到了很多东西，但是如果没有一些背景知识，这个代码有点难以理解——对此我感到抱歉。有了其他答案提供的一些常识，你就可以开始分析正在发生的事情了。

The Y function is the "y-combinator". Now take a look at the var factorial line where Y is used. Notice you pass a function to it that has a parameter (in this example, recurse) that is also used later on in the inner function. The parameter name basically becomes the name of the inner function allowing it to perform a recursive call (since it uses recurse() in it's definition.) The y-combinator performs the magic of associating the otherwise anonymous inner function with the parameter name of the function passed to Y.

关于Y如何变魔术的完整解释，请查看链接文章(顺便说一下，不是我写的)。