欢迎到来。若想注册,请私信知乎 王霄池。
多知乎(取自 孰为汝多知乎),一个意见强烈,观点极端的问答社区。解放知识,让人们认识世界、改造世界。

分类

最新提问 分类:自然科学 | 用户: (490 分)
重新分类 用户:

1个回答

0 投票
Y组合子的用处是使得 lambda 表达式不需要名字

如你所说,阶乘函数可以这样定义:
let F = lambda n. n==0 ? 1 : n*(F n-1)
当我们需要调用的时候,我们只需要这样写就可以了:
F 4
但你有没有想过,如果我们没有 let 这个关键字怎么办?没有 let,就不能对一个 lambda 表达式命名。实际上,在 lambda 演算里确实没有 let,换句话说,let 只是个语法糖,让我们写起来更加舒适而已。没有 let,并没有对lambda表达式造成什么实质性的伤害。

数学家们推崇:
如无必要,勿增实体
是的。所以,你不能对任何lambda表达式命名。这就像你中了一个沉默魔法一样。

我们先来看看如果没有递归,无名 lambda 表达式是如何使用的。
我们来写一个求平方的lambda:
lambda x. x * x
这个lambda是无名的。如果要调用,我们只能这么调用:
( lambda x. x * x ) 3
结果自然是返回 9 了。

看来没有名字,lambda 世界还是可以正常运转的。且慢,我们不要忘记递归。递归函数,似乎真的是个问题——如果没有名字,自身如何调用自身?其实也不是啥大问题。不过,要解决这个问题,我们先假设我们可以使用名字。别担心,这只是前进途中的曲折。最后,我们会去掉名字的,大家先不要着急。

我们以阶乘函数为例,先看看我们现阶段的成果:
let F = lambda n. n==0 ? 1 : n*(F n-1)
首先我们先设法消除掉 lambda 函数体中的函数名称(对不起,一激动就用上了函数这个说法,如果你不知道什么叫函数,那么你就可以理解为函数就是 lambda,二者是等同的)。方法就是将函数作为参数传进去。
let F = lambda f. lambda n. n==0 ? 1 : n*((f f) (n-1))
这个函数的接受一个参数,返回一个函数,这个返回的函数才是真正做计算的阶乘函数。
调用此函数的方法如下:
F F 4
将会返回24。

接下来的一步将是至关重要的。我们现在就抛弃let关键字。我们将F的名字换成F的定义,于是调用阶乘函数的的方式将变成如下的样子:
( lambda f. lambda n. n==0 ? 1 : n*((f f) (n-1)) ) ( lambda f. lambda n. n==0 ? 1 : n*((f f) (n-1)) ) 4
看到了没,这里的所有 lambda 都没有名字,不过,这丝毫没有影响 lambda 表达式的威力。

如果你看到这里,就会发现,我们可以用类似的方法定义所有的递归函数,而用不着Y组合子。是的。你是对的。上面这种方法叫做穷人的Y组合子。但Y组合子的作用就是提供了一个通用的方法来定义递归函数。

让我们来看一下Y的定义:
lambda f. (lambda x. (f(x x)) lambda x. (f(x x)))
要讲清楚Y的来龙去脉,可是非常难(大家可以去看我的博文重新发明 Y 组合子 Python 版)。事实上,连发现它的哈斯卡大神也感慨不已,觉得自己捡了个大便宜,还因此将Y纹在了自己的胳膊上。我现在就只讲Y的用处了。


我们用Y来定义一下递归函数
let F = Y ( lambda f. lambda n. n==0 ? 1 : n*(f n-1) )

大家有没有发现,定义变得比以前的特定方法更加优美了。在之前的特定方法中 f 需要应用于自身,但现在,f 是由 Y 提供的,是一个纯阶乘函数。

不只是定义更加优雅,连调用也像有名字的lambda一样优美了。我们现在就优雅的调用阶乘函数:
F 4
而去掉F的名字,我们有:
( Y ( lambda f. lambda n. n==0 ? 1 : n*(f n-1) ) ) 4
再去掉Y的名字:
( ( lambda f. (lambda x. (f(x x)) lambda x. (f(x x))) )
  ( lambda f. lambda n. n==0 ? 1 : n*(f n-1) )
) 4
看,这里没有任何名字,但我们定义并且调用了阶乘函数。再次强调一下,阶乘函数是个递归函数哦。

任何一阶递归函数都可以用Y来定义,就像我们定义阶乘函数那样:
Y (lambda f. < 真正的函数体,在内部用f指代自身 >)

多说一句,可以在 JavaScript 中实现Y算子,如果用上 CoffeScript 提供的语法糖,将非常优雅(这里我原写错了,感谢 @Liu Martin ):
Y = (g) ->
  h = (f) ->
    g(n) -> f(f) n
  h h

Y算子真是人见人爱。但除了证明lambda只需要alpha/beta/eta三条规则而不需要命名之外,它主要用自身的优美供大家感叹。在真实的世界中,不论是数学家,还是函数式编程的 coder,都需要给事物命名。

====
更新:函数不动点在编程中的应用 lfcs.inf.ed.ac.uk/repor
最新回答 用户: (510 分)
...