logo标签列表

“组合子”（非数学家的好解释）的良好解释

functionlambdacombinatorsy-combinator
57

有谁能给出“组合子”（如 Y-组合子等，而不是指该公司）的良好解释吗？

我正在寻找一位为实用程序员提供解释的人，他们了解递归和高阶函数，但并没有很强的理论或数学背景。

（注：我在谈论这些东西）

8个回答
36

除非你对理论有深入了解，否则可以将 Y combinator 视为一种有趣的函数技巧，就像单子（monads）一样。

单子允许您链接动作，而 Y combinator 允许您定义自递归函数。

Python 内置支持自递归函数，因此您可以在不使用 Y 的情况下定义它们：

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

> fun()
bla
bla
bla
...

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%正确，但我认为这是一般的想法。)

16
技术上那是Omega组合子——实际上Y组合子也允许函数带参数 :) - Josh Lee
2
在 Stack Overflow 上搜索了半个小时后，终于理解了 Y 组合子。SO 上最好的答案是简短明了，使用日常语言的那些。 - user3917838
23

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

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

此外，他还发表了几篇关于如何使用它们的文章。

是的，我也注意到那个系列了。我需要更仔细地研究这些例子，因为我对Ruby不太熟悉，但它很棒。 - interstar
15

引用自维基百科：

组合子（combinator）是一个高阶函数，它仅使用函数应用和先前定义的组合子来从其参数定义结果。

那这是什么意思呢？这意味着组合子是一个函数（输出完全由其输入决定），其输入包括函数作为参数。

这样的函数看起来像什么，用于什么？以下是一些例子：

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

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

组合子可用于隐藏逻辑。假设我们有一个数据类型 NumberUndefined，其中 NumberUndefined 可采用数值 Num x 或值 Undefined，其中 x 是一个 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)

请注意，它们在处理Undefined输入值时都有相同的逻辑。只有除法多做了一些事情。解决方法是通过将其作为组合器提取出逻辑。

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

这可以推广为程序员在函数式语言中使用的所谓Maybe monad，但我不会深入讨论。

6

组合子是没有自由变量的函数。这意味着，除了函数参数之外，组合子不依赖于函数外部的其他内容。

使用 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
3
sum 的定义中加号 + 怎么处理？它没有被绑定。 - Matt Fenwick
@MattFenwick 在某个时候，你需要与硬件进行交流。这种假设在理论讨论中经常被提出；但它比其他任何东西都更像是一个误导。+ 无法以完全组合的方式进行定义，因为在某个时候，您需要向底层实现发出加号指令。即使是SKI演算法也没有真正了解数字，并且一元实现也需要一些对实现的调用。 - jellies
2

这是一篇不错的文章。 代码示例使用Scheme编写，但它们应该很容易理解。

我希望有比dreamsongs更基础一些的东西。也许可以更加详细地解释它们所解决的问题并提供更多动机。 - interstar
1

我对理论了解不多，但我可以给你一个让我兴奋的例子，也许对你有所帮助。最简单且有趣的组合器可能是“test”。

希望你懂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'

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

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

整个系统可以从几个基本组合子构建起来。
（这个例子或多或少是从Benjamin C. Pierce的《类型与编程语言》中复制出来的）
0
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接