对“组合器”的很好的解释 （对于非数学家）

Question

任何人都对“组合器”（Y-组合器等）有很好的解释，并且NOT 公司）？

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

（注意：我正在谈论这些事情）

Answer 1

引用维基百科：

组合器是一个高阶函数，它仅使用函数应用程序和之前定义的组合器来定义其参数的结果。

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

这些函数是什么样的以及它们的用途是什么？ 以下是一些示例：

(fog)(x) = f(g(x))

这里 o 是一个组合器，它接受 2 个函数，f 和 g，并返回一个函数作为其结果，由 f 和 g 组成，即 fo g。

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

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

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 等函数式语言中使用的所谓的 Maybe monad，但我不会去那里。

Answer 2

Reginald Braithwaite（又名 Raganwald）在他的新博客 homoiconic 上撰写了有关 Ruby 组合器的精彩系列文章。

虽然他（据我所知）没有研究 Y 组合器本身，但他确实研究了其他组合器，例如：

• Kestrel
• 画眉
• 红衣主教
• 顽固红隼
• 其他 Quirky Birds

以及一些关于如何可以< /a> 使用它们。

Answer 3

除非你对理论很深入，否则你可以考虑 Y 组合器
作为一个巧妙的函数技巧，比如 monad。

Monad 允许您链接操作，Y 组合器允许您
定义自递归函数。

Python 内置了对自递归函数的支持，因此您可以
可以在没有 Y 的情况下定义它们：

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

> fun()
bla
bla
bla
...

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

但是如果 Python 不同，并且无法访问 fun 该怎么办
在 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%正确，但我认为这是一般的想法。）

Answer 4

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

Answer 5

这是一篇很好的文章。
代码示例在方案中，但它们应该不难理解。

Answer 6

我的理论很短，但我可以给你举一个激发我想象力的例子，这可能对你有帮助。 最简单有趣的组合器可能是“测试”。

希望您知道 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 的《类型和编程语言》中复制而来的）

Answer 7

简而言之，Y 组合器是一个高阶函数，用于实现 lambda 表达式（匿名函数）的递归。 查看 Mike Vanier 的文章如何在没有真正递归的情况下成功实现递归 - 这是最实用的文章之一我见过对这件事的解释。

另外，扫描 SO 档案：

• 什么是 y-combinator？
• Y-Combinator 实际示例

Answer 8

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

使用 F#，这是我对组合器的理解：

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 是绑定的，因此整个函数是一个组合器。

所以，这就是我对组合器的理解。 另一方面，我仍然不明白它们的意义。 正如其他人指出的那样，定点组合器允许人们在没有显式递归的情况下表达递归函数。 即，递归函数不调用自身，而是调用作为参数之一传入的 lambda。

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

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