• 游客,您好! Include社区于2021.5.26迁移至新版社区,用户数据丢失,欢迎注册! 补偿政策

教程 Y组合子 (lambda实现递归调用)

Include社区

Include社区信息发布
管理成员
超级版主
2021/05/26
9
2
101
China

Tips​

以下语言均为scheme语言。

前言

假如我们要写一个计算阶乘的函数f,正常情况下会怎么写呢?
代码:
(define (f n)
  (cond ((= n 0) 1)
        (else (* n (f (- n 1))))))

对吧,那假如我要求使用lambda来定义呢?也许你会写出如下代码:
代码:
(define f
  (lambda (n) (cond ((= n 0) 1)
                    (else (* n (f (- n 1)))))))

对吧,可是这个lambda需要引用外部的别名,当这个名字改变,显然会失效.
那么现在思考,在没有define的情况下,lambda函数可以进行递归调用吗?
答案是可以,使用本文要介绍的Y组合子。

正文​

先考虑构造出一个能生成该函数的函数,我们现在假设这个函数是g。
代码:
(define g
  (lambda (p) (lambda (n) (cond ((= n 0) 1)
                                (else (* n ((p p) (- n 1))))))))

而函数f将变成
代码:
(define (f n) ((g g) n))

我们可以看到,上面是将函数自身作为一个参数传入,根据代换模型可以知道,上面的代码可以等同于以下:
代码:
(define (f n) (((lambda (p) (lambda (n) (cond ((= n 0) 1)
                                (else (* n ((p p) (- n 1)))))))
                (lambda (p) (lambda (n) (cond ((= n 0) 1)
                                (else (* n ((p p) (- n 1)))))))) n))

我们成功的让计算阶乘的实现不在依赖于这个函数的别名,假如我们要计算5!,可以用如下代码实现:
代码:
(print (((lambda (p) (lambda (n) (cond ((= n 0) 1)
                                (else (* n ((p p) (- n 1)))))))
                (lambda (p) (lambda (n) (cond ((= n 0) 1)
                                (else (* n ((p p) (- n 1)))))))) 5))

本文完结. (才没有呢)
有没有什么通用的方法生成这个代码呢?当然有!
我们具体的思路就是将这个函数本身作为参数本身传入该函数中,可以整理一个Y函数来生成这个。
代码:
(define Y
  (lambda (f) ((lambda (p) (f (lambda (s) ((p p) s))))
  (lambda (p) (f (lambda (s) ((p p) s)))))))

而以上的f可以改用Y函数来生成:
代码:
(define f
  (Y (lambda (p) (lambda  (n) (cond ((= n 0) 1)
                                    (else (* n (p (- n 1)))))))))

真正的结束了..



author@RMOlives
 

在线会员

现在没有会员在线。