首页 > 代码库 > Racket中使用Y组合子

Racket中使用Y组合子

关于Y组合子,网上已经介绍很多了,其作用主要是解决匿名lambda的递归调用自己。

首先我们来看直观的递归lambda定义,

假设要定义阶乘的lambda表达,C#中需要这么定义

Func<int, int> fact = null;fact = x => x <= 1 ? 1 : x * fact(x - 1);

这种方法非常简单直接,当然问题也存在,因为这里fact其实是一个委托对象,当这个对象改变后,可能就得不到阶乘的效果了。

在scala中则是这样,

def F: Int => Int = (n:Int) => if(n == 0) 1 else  n* F(n - 1)

嗯,在本文的主打语言Racket中,则变成这样

(define F  (lambda (n) (if (equal? n 0)                  1                  (* n (F (- n 1))))))

由于这个函数F定义中使用了F自身,那么如何修改可以去掉这个F?

现在变化一下,增加一个函数参数f,以使的我们调用F时,可以把自身传递进去,那样就解决了前面F的定义中使用了F自身的问题,修好后如下

(define FF  (lambda (f) (lambda (n) (if (equal? n 0)                              1                              (* n ((f f) (- n 1)))))))

这样调用((FF FF) 5)就能得到120这个结果了。

当然这里我们甚至可以不用define这个关键字来给这个lambda定义一个名字,直接上lambda本体,如下

(((lambda (f) (lambda (n) (if (equal? n 0)                              1                              (* n ((f f) (- n 1)))))) (lambda (f) (lambda (n) (if (equal? n 0)                              1                              (* n ((f f) (- n 1))))))) 5)

同意可以得到正确结果120。

上面这个方法算是比较直接,一个更加优雅的解决方法当然就是本文的主jiao:Y组合子

Y组合子

Y = λf. (λx. f (x x)) (λx. f (x x))

未完待续

 

Racket中使用Y组合子