为了帮助自己掌握Y-Combinator，我在Clojure和Scheme中都写了一份关于Y-Combinator的“傻瓜指南”。他们受到了《小阴谋家》的影响

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

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

这两个教程都是代码中穿插的注释，应该剪切和粘贴到您最喜欢的编辑器。

作为一个组合子的新手，我发现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，这让我想到了这篇文章。

如果你准备好长篇大论，Mike Vanier有一个很好的解释。长话短说，它允许您在一种不一定支持递归的语言中实现递归。

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

其他答案对此提供了相当简洁的答案，但没有一个重要的事实:你不需要用任何实用语言以这种令人费解的方式实现定点组合子，这样做没有任何实际目的(除了“看，我知道y组合子是什么”)。这是一个重要的理论概念，但没有什么实际价值。