有人对"组合器"(Y组合器等，而不是公司)有很好的解释吗？
我正在为了解递归和高阶函数但又没有扎实的理论或数学背景的实用程序员寻找一个。
(注意：我在谈论这些事情)
除非您深入理论，否则可以考虑使用Y组合器
作为诸如monad之类的功能的巧妙技巧。
Monad使您可以链接动作，Y组合器使您可以
定义自递归函数。
Python内置了对自递归函数的支持，因此您可以
可以不使用Y来定义它们：
1
2
3
4
5
6
7
8
9
| > def fun():
> print"bla"
> fun()
> fun()
bla
bla
bla
... |
fun本身内部可以访问fun，因此我们可以轻松地调用它。
但是如果Python不同，并且fun无法访问怎么办
内fun？
1
2
3
| > def fun():
> print"bla"
> # what to do here? (cannot call fun!) |
解决方案是将fun本身作为参数传递给fun：
1
2
3
| > def fun(arg): # fun receives itself as argument
> print"bla"
> arg(arg) # to recur, fun calls itself, and passes itself along |
Y使这成为可能：
1
2
3
4
5
6
7
8
| > def Y(f):
> f(f)
> Y(fun)
bla
bla
bla
... |
它所做的全部工作就是调用一个以自身为参数的函数。
(我不知道Y的这种定义是否100％正确，但是我认为这是普遍的想法。)
雷金纳德·布雷思韦特(Reginald Braithwaite，又名Raganwald)在他的新博客homoiconic上撰写了有关Ruby中组合器的系列文章。
虽然他(据我所知)没有查看Y组合器本身，但确实查看了其他组合器，例如：
-
红est
-
鹅口疮
-
红衣主教
-
顽固的茶est
-
其他古怪的鸟
以及有关如何使用它们的几篇文章。
引用维基百科：
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。
可以编写如下乏味的代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| 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) |
注意所有关于Undefined输入值的逻辑如何相同。只有除法多了一点。解决方案是通过使其成为组合器来提取逻辑。
1
2
3
4
5
6
7
8
| 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之类的功能语言中使用的所谓的Maybe monad，但我不会去那里。
组合器是没有自由变量的函数。这意味着，除其他事项外，组合器不依赖于函数之外的事物，而仅依赖于函数参数。
使用F＃，这是我对组合器的理解：
1
| let sum a b = a + b;; //sum function (lambda) |
在上述情况下，sum是组合器，因为a和b都绑定到功能参数。
1
| let sum3 a b c = sum((sum a b) c);; |
上面的函数不是组合器，因为它使用sum，它不是绑定变量(即它不是来自任何参数)。
通过简单地将sum函数作为参数之一，我们可以使sum3成为组合器：
1
| let sum3 a b c sumFunc = sumFunc((sumFunc a b) c);; |
通过这种方式绑定sumFunc，因此整个函数是组合器。
因此，这就是我对组合器的理解。另一方面，它们的重要性仍然让我难以忘怀。正如其他人指出的那样，定点组合器允许人们表达递归函数而无需explicit递归。即重新调用函数不会调用自身，而是调用作为参数之一传入的lambda。
这是我发现的最容易理解的组合器派生之一：
http://mvanier.livejournal.com/2897.html
这看起来不错：http://www.catonmat.net/blog/derivation-of-ycombinator/
这是一篇好文章。
代码示例处于计划中，但不难理解。
我在理论上还很短，但是我可以举个例子，使我的想象力浮出水面，这可能对您有所帮助。最简单有趣的组合器可能是"测试"。
希望你知道Python
1
2
3
4
| tru = lambda x,y: x
fls = lambda x,y: y
test = lambda l,m,n: l(m,n) |
用法：
1
2
3
4
| >>> test(tru,"goto loop","break")
'goto loop'
>>> test(fls,"goto loop","break")
'break' |
如果第一个参数为true，则test计算第二个参数，否则为第三个。
1
2
3
| >>> x = tru
>>> test(x,"goto loop","break")
'goto loop' |
整个系统可以由几个基本的组合器组成。
(此示例或多或少地由Benjamin C. Pierce从类型和编程语言中复制而来)
不久，Y组合器是一个高阶函数，用于对lambda表达式执行递归(匿名函数)。请参阅Mike Vanier的文章如何在没有真正递归的情况下成功进行递归-这是我所见过的对此问题的最佳实用解释之一。
另外，扫描SO档案：
