有人对"组合器"(Y组合器等，而不是公司)有很好的解释吗？

我正在为了解递归和高阶函数但又没有扎实的理论或者数学背景的实用程序员寻找一个。

(注意：我在谈论这些事情)

解决方案

这是一篇好文章。
代码示例处于计划中，但不难理解。

除非我们深入理论，否则可以考虑使用Y组合器
作为诸如monad之类的功能的巧妙技巧。

Monad使我们可以链接动作，Y组合器使我们可以
定义自递归函数。

Python内置了对自递归函数的支持，因此我们可以
可以不使用Y来定义它们：

> def fun():
>  print "bla"
>  fun()

> fun()
bla
bla
bla
...

在fun内部可以访问fun，因此我们可以轻松地调用它。

但是，如果Python与众不同，并且无法访问fun，该怎么办？
在"有趣"里面？

> def fun():
>   print "bla"
>   # what to do here? (cannot call fun!)

解决的办法是将fun本身作为参数传递给fun：

> def fun(arg): # fun receives itself as argument
>   print "bla"
>   arg(arg) # to recur, fun calls itself, and passes itself along

Y使这成为可能：

> def Y(f):
>   f(f)

> Y(fun)
bla
bla
bla
...

它所做的全部工作就是调用一个以自身为参数的函数。

(我不知道Y的这种定义是否100％正确，但是我认为这是普遍的想法。)

雷金纳德·布雷思韦特(Reginald Braithwaite，又名Raganwald)在他的新博客homoiconic上撰写了有关Ruby中组合器的系列文章。

虽然他(据我所知)没有查看Y组合器本身，但确实查看了其他组合器，例如：

• 红est
• 鹅口疮
• 红衣主教
• 顽固的茶est
• 其他古怪的鸟

以及有关如何使用它们的几篇文章。

我在理论上还很短，但是我可以举个例子，使我的想象力浮出水面，这可能对我们有所帮助。最简单有趣的组合器可能是"测试"。

希望你知道Python

tru = lambda x,y: x
fls = lambda x,y: y 

test = lambda l,m,n: l(m,n)

用法：

>>> test(tru,"goto loop","break")
'goto loop'
>>> test(fls,"goto loop","break")
'break'

如果第一个参数为true，则test计算第二个参数，否则为第三个。

>>> x = tru
>>> test(x,"goto loop","break")
'goto loop'

整个系统可以由几个基本的组合器组成。

(本示例或者多或者少地由Benjamin C. Pierce从类型和编程语言中复制而来)

引用维基百科：

A combinator is a higher-order function that uses only function application and earlier defined combinators to define a result from its arguments.

现在这是什么意思？这意味着组合器是一个函数(输出仅由其输入确定)，其输入包括一个函数作为参数。

这些功能是什么样的？它们的作用是什么？这里有些例子：

((f o g)(x)= f(g(x))`

这里的o是一个组合器，它接受两个函数f和g，并返回一个函数作为结果，即f与g的组合，即f o g。

组合器可用于隐藏逻辑。假设我们有一个数据类型" NumberUndefined"，其中" NumberUndefined"可以采用数值" Num x"或者值" Undefined"，其中" x" a是" Number"。现在，我们要为这种新的数字类型构造加，减，乘和除法。语义与Number的语义相同，不同之处在于，如果输入Undefined，则输出也必须Undefined，当除以数字0时其输出也为Undefined。

可以编写如下乏味的代码：

Undefined +' num = Undefined
num +' Undefined = Undefined
(Num x) +' (Num y) = Num (x + y)

Undefined -' num = Undefined
num -' Undefined = Undefined
(Num x) -' (Num y) = Num (x - y)

Undefined *' num = Undefined
num *' Undefined = Undefined
(Num x) *' (Num y) = Num (x * y)

Undefined /' num = Undefined
num /' Undefined = Undefined
(Num x) /' (Num y) = if y == 0 then Undefined else Num (x / y)

注意所有关于"未定义"输入值的逻辑如何相同。只有除法多了一点。解决方案是通过使其成为组合器来提取逻辑。

comb (~) Undefined num = Undefined
comb (~) num Undefined = Undefined
comb (~) (Num x) (Num y) = Num (x ~ y)

x +' y = comb (+) x y
x -' y = comb (-) x y
x *' y = comb (*) x y
x /' y = if y == Num 0 then Undefined else comb (/) x y

可以将其概括为程序员可能在诸如Haskell之类的功能语言中使用的所谓的"也许是"单子，但是我不会去那里。

简而言之，Y组合器是一个高阶函数，用于对lambda表达式执行递归(匿名函数)。请参阅Mike Vanier的文章"如何在没有真正递归的情况下成功进行递归"，这是我所见过的对此问题的最佳实用解释之一。

另外，扫描SO档案：

• 什么是y组合器？
• Y组合器实例

组合器是没有自由变量的函数。这意味着，除其他外，组合器不依赖于函数之外的事物，而仅依赖于函数参数。

使用Fthis是我对组合器的理解：

let sum a  b = a + b;; //sum function (lambda)

在上述情况下，sum是组合器，因为a和b都绑定到函数参数。

let sum3 a b c = sum((sum a b) c);;

上面的函数不是组合器，因为它使用的是sum，它不是绑定变量(即它不是来自任何参数)。

通过简单地将sum函数作为参数之一，我们可以使sum3成为组合器：

let sum3 a b c sumFunc = sumFunc((sumFunc a b) c);;

这样，sumFunc被绑定，因此整个函数是一个组合器。

因此，这就是我对组合器的理解。另一方面，它们的重要性仍然让我无法理解。正如其他人指出的那样，定点组合器允许人们表达一种递归函数而无需"显式"递归。 IE。重新调用函数不会调用自身，而是调用作为参数之一传入的lambda。

这是我发现的最容易理解的组合器派生之一：

http://mvanier.livejournal.com/2897.html

这看起来不错：http：//www.catonmat.net/blog/derivation-of-ycombinator/