对"组合者"的好解释(非数学家)

Question

任何人都对"组合器"(Y-combinators等而不是 公司)有很好的解释？

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

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

Answer 1

除非你深入理论,否则你可以将Y组合器视为一个功能齐全的技巧,比如monad.

Monads允许您链接动作,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 2

Reginald Braithwaite(又名Raganwald)在他的新博客homoiconic上撰写了一篇关于Ruby组合器的精彩系列.

虽然他(据我所知)没有看到Y-combinator本身,但他确实看过其他组合器,例如:

• 在红隼
• 该鸫
• 在红衣主教
• 在顽固的红隼
• 其他古怪的鸟类

和你怎么几个职位可以 使用它们.

Answer 3

引用维基百科:

组合子是一个高阶函数,它只使用函数应用程序和早期定义的组合器来定义其参数的结果.

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

这些功能看起来像什么,它们用于什么？这里有些例子:

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

这o是一个组合器,它接收2个函数,f并且g,并返回一个函数作为其结果,即fwith 的组成g,即f 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

这可以推广到Maybe程序员在Haskell等函数式语言中使用的所谓monad,但我不会去那里.

Answer 4

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

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

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

在上面的情况和是因为两者组合子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递归.即不是自称为recusrsive函数,而是调用作为参数之一传入的lambda.

这是我发现的最易理解的组合子派生之一:

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

Answer 5

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