对于Y组合子的理解

前言

这周闲来无事,狠狠研究了一把lambda演算,不可避免的涉及到对Y组合子的理解。因为是从“解决匿名递归函数 的定义” 引起的,看了网上很多帖子,感觉绕来绕去容易被搞糊涂。今天又翻了一下wiki,算是真正理解了,特地在此提炼一下。

第一件事:我们要定义f (f指一个匿名递归函数,比如阶乘 power(n))

为了定义power(n),我们先定义一个函数:

fact(n)=lambda n . n*fact(n-1)
//这个定义是不能通过的,因为等号右侧的fact未定义,即:我们不能直接描述fact!!

那么,间接的,我们描述一个以 fact作为其中一个函数特例的高阶函数(即以函数为参数)

G(x)(n)=lambda x n . n* x(n -1)  //这个定义是合法的。OK

Y组合字的作用是:

我们应用Y组合子,即可得到合法定义的power。而避免直接定义fact。

我偷个懒,不具体推导,下面直接看Wiki中的例子(这里Y组合子即为fix()):

####例子 考虑阶乘函数(使用邱奇数)。平常的递归数学等式

fact(n) = if n=0 then 1 else n * fact(n-1)

可以用 lambda 演算把这个递归的一个“单一步骤”表达为

F = λf. λx. (ISZERO x) 1 (MULT x (f (PRED x)))

这里的 “f” 是给阶乘函数的占位参数,用于传递给自身。 函数 F 进行求值递归公式中的一个单一步骤。 应用 fix 算子得到

fix(F)(n) = F(fix(F))(n)
fix(F)(n) = λx. (ISZERO x) 1 (MULT x (fix(F) (PRED x)))(n)
fix(F)(n) = (ISZERO n) 1 (MULT n (fix(F) (PRED n)))

我们可以简写 fix(F) 为 fact,得到

fact(n) = (ISZERO n) 1 (MULT n (fact(PRED n)))

所以我们见到了不动点算子确实把我们的非递归的“阶乘步骤”函数转换成满足预期等式的递归函数。


关键在于:F 是定义好的,fix 是定义好的

fix(F)=F(fix(F))(n)
	=(ISZERO n) 1 (MULT n (fix(F) (PRED n)))//即是目标函数

原先同样形式中的fact为未定义,而现在这个形式中的fix(F) 却是已经定义了的! F的定义:

F = λf. λx. (ISZERO x) 1 (MULT x (f (PRED x)))

fix即Y组合子,定义:

Y = lambda y . (lambda x . y ( x x) ) (lambda x . y ( x x ) )

感谢:http://blog.csdn.net/pongba/article/details/1336028
还有:http://blog.csdn.net/g9yuayon
wiki:http://zh.wikipedia.org/wiki/不动点组合子

Published: January 17 2013

prize
微信扫一扫,支持一下!