55

有人对“组合器”（Y-组合器等而不是 公司）有很好的解释吗？

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

（注意：我说的是这些东西）

4

8 回答 8

34

Unless you're deeply into theory, you can regard the Y combinator as a neat trick with functions, like monads.

Monads allow you to chain actions, the Y combinator allows you to define self-recursive functions.

Python has built-in support for self-recursive functions, so you can define them without Y:

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

> fun()
bla
bla
bla
...

fun is accessible inside fun itself, so we can easily call it.

But what if Python were different, and fun weren't accessible inside fun?

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

The solution is to pass fun itself as an argument to fun:

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

And Y makes that possible:

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

> Y(fun)
bla
bla
bla
...

All it does it call a function with itself as argument.

(I don't know if this definition of Y is 100% correct, but I think it's the general idea.)

于 2008-09-19T13:45:20.113 回答
22

Reginald Braithwaite（又名 Raganwald）在他的新博客homoiconic上写了一个关于 Ruby 组合子的精彩系列。

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

以及一些关于如何使用它们 的帖子。

于 2008-11-13T00:57:14.443 回答
15

引用维基百科：

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

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

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

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

这o是一个组合器，它接收 2 个函数f和g，并返回一个函数作为其结果，即fwith的组合。gf o g

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

请注意所有关于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

这可以概括为程序员在 Haskell 等函数式语言中使用的所谓Maybemonad，但我不会去那里。

于 2010-02-06T23:45:52.997 回答
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是有界的，因此整个函数是一个组合子。

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

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

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

于 2010-02-07T00:09:12.567 回答
2

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

于 2010-02-23T19:20:18.957 回答
2

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

于 2008-09-18T22:47:13.167 回答
1

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

希望你了解 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 的 Types and Programming Languages 中复制出来）

于 2008-11-13T01:22:09.413 回答
0

简而言之，Y 组合器是一个高阶函数，用于在 lambda 表达式（匿名函数）上实现递归。查看 Mike Vanier 的文章How to Succeed at Recursion without Being Recursing - 这是我见过的对这个问题的最佳实用解释之一。

此外，扫描 SO 档案：

于 2010-02-06T23:59:38.237 回答