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

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

以下是对尼古拉斯·曼库索(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有一个很好的解释。长话短说，它允许您在一种不一定支持递归的语言中实现递归。

不动点组合子(或不动点运算符)是一种高阶函数，用于计算其他函数的一个不动点。此操作与编程语言理论相关，因为它允许以重写规则的形式实现递归，而不需要语言的运行时引擎的显式支持。(src维基百科)

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

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

它的工作原理是将函数作为参数传递给自己，这样它就可以调用自己。

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

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

如果你需要在警察的队列中识别它，它看起来是这样的:

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

你通常可以发现它，因为重复的(λx。F (x x))

λ符号是希腊字母，这是λ演算的名字，有很多(λx.t)风格的术语因为这就是λ演算的样子。