专栏首页窗户相互递归(3)

相互递归(3)

  版权申明:本文为博主窗户(Colin Cai)原创,欢迎转帖。如要转贴,必须注明原文网址

  http://www.cnblogs.com/Colin-Cai/p/10963080.html 

  作者:窗户

  QQ/微信:6679072

  E-mail:6679072@qq.com

  我们根据上一章最开始的相互递归转一般递归的方法,结合Y Combinator,来对第一章的append实现做一下测试。

(define (append . lst)
 (if (null? lst)
  '()
  ((apply _append (cdr lst)) (car lst))
 )
)

(define (_append . lst)
 (cond
  ((null? lst) (lambda (x) x))
  ((null? (cdr lst))
   (lambda (x)
    (if (null? x)
     (car lst)
     (cons (car x) ((_append (car lst)) (cdr x)))
    )
   )
  )
  (else (_append (apply append lst)))
 )
)

  上述实现中,append和_append互相递归。

  按照第二章中相互递归转普通递归的方法,我们可以定义一个高阶函数append-high,

  使得(append-high 1)就是append,(append-high 2)就是_append。

  于是我们可以这样写,append-high带一个参数,如果参数为1,则是上述append的定义,否则则为上述_append的定义,并在定义中把append和_append都用append-high表示。代码如下:

(define (append-high n)
 (if (= n 1)
  (lambda lst
   (if (null? lst)
    '()
    ((apply (append-high 2)(cdr lst)) (car lst))))
  (lambda lst
   (if (null? lst)
    (lambda (x) x)
    (if (null? (cdr lst))
     (lambda (x)
      (if (null? x)
       (car lst)
       (cons (car x) (((append-high 2)(car lst)) (cdr x)))))
     ((append-high 2) (apply (append-high 1) lst)))))))

  完全写成lambda的方式(实际上,define (funname arg)这样的写法是语法糖),以便于后面全用lambda演算。

  代码如下:

(define append-high
 (lambda (n)
  (if (= n 1)
   (lambda lst
    (if (null? lst)
     '()
     ((apply (append-high 2)(cdr lst)) (car lst))))
   (lambda lst
    (if (null? lst)
     (lambda (x) x)
     (if (null? (cdr lst))
      (lambda (x)
       (if (null? x)
        (car lst)
        (cons (car x) (((append-high 2)(car lst)) (cdr x)))))
      ((append-high 2) (apply (append-high 1) lst))))))))

  以append-high为不动点的函数则为以下:

(define fix-append-high
 (lambda (append-high)
  (lambda (n)
   (if (null? n)
    (lambda lst
     (if (null? lst)
      '()
      ((apply (append-high '(()))(cdr lst)) (car lst))))
    (lambda lst
     (if (null? lst)
      (lambda (x) x)
      (if (null? (cdr lst))
       (lambda (x)
        (if (null? x)
         (car lst)
         (cons (car x) (((append-high '(()))(car lst)) (cdr x)))))
       ((append-high '(())) (apply (append-high '()) lst)))))))))

  于是这个函数前面接上Y Combinator就得到了append-high函数,再加上参数1,就是我们最终要实现的append函数。

  一起写了,如下:

(define append
 (
  ((lambda (f)
    ((lambda (g) (g g))(lambda (x) (f (lambda s (apply (x x) s))))))
   (lambda (append-high)
    (lambda (n)
     (if (null? n)
      (lambda lst
       (if (null? lst)
        '()
        ((apply (append-high 2)(cdr lst)) (car lst))))
      (lambda lst
       (if (null? lst)
        (lambda (x) x)
        (if (null? (cdr lst))
         (lambda (x)
          (if (null? x)
           (car lst)
           (cons (car x) (((append-high 2)(car lst)) (cdr x)))))
         ((append-high 2) (apply (append-high 1) lst)))))))))
  1)
)

  于是,到这里,我们完全用lambda演算写出来的append就这么实现了,虽然看上去的确不是那么好懂,lambda漫天飞。

  实现看上去这么抽象的函数真的好用吗?测试一下,看看结果对不对?

(append '() '(1) '(2 3) '() '(4 5 6) '(7) '(8) '(9 10 11))

  得到结果

(1 2 3 4 5 6 7 8 9 10 11)

  上述结果说明,函数实现的还是可以用的。

  第一章最后给出的三个函数互相递归,我们也还是验证一下。

(define (type0? x)
 (if (= x 0)
  #t
  (type2? (- x 1))
 )
)
(define (type1? x)
 (if (= x 0)
  #f
  (type0? (- x 1))
 )
)
(define (type2? x)
 (if (= x 0)
  #f
  (type1? (- x 1))
 )
)

  建立一个高阶函数type-high,让(type-high 0)就是type0?,(type-high 1)就是type1?,(type-high 2)就是type2?

  注意,所有都用lambda来表示。

(define type-high
 (lambda (n)
  (cond
   ((= n 0) (lambda (x) (if (= x 0) #t ((type-high 2) (- x 1)))))
   ((= n 1) (lambda (x) (if (= x 0) #f ((type-high 0) (- x 1)))))
   (else (lambda (x) (if (= x 0) #f ((type-high 1) (- x 1)))))
  )
 )
)

  type-high使用Y Combinator匿名递归,实现则为如下

(define type-high
 (
  (lambda (f)
   ((lambda (g) (g g))(lambda (x) (f (lambda s (apply (x x) s)))))
  )
  (lambda (f)
   (lambda (n)
    (cond
     ((= n 0) (lambda (x) (if (= x 0) #t ((f 2) (- x 1)))))
     ((= n 1) (lambda (x) (if (= x 0) #f ((f 0) (- x 1)))))
     (else (lambda (x) (if (= x 0) #f ((f 1) (- x 1)))))
    )
   )
  )
 )
)

  之前的type0? type1? type2?分别是(type-high 0)、(type-high 1)、(type-high 2)

  于是我们可以用以下来验证

(for-each
 (lambda (x) (display x)(newline))
 (map
  (lambda (x)
   (cons
    x
    (map (lambda (f) (f x)) (map (lambda (n) (type-high n)) '(0 1 2)))
   )
  )
  (range 20)
 )
)

  验证结果没有问题

(0 #t #f #f) (1 #f #t #f) (2 #f #f #t) (3 #t #f #f) (4 #f #t #f) (5 #f #f #t) (6 #t #f #f) (7 #f #t #f) (8 #f #f #t) (9 #t #f #f) (10 #f #t #f) (11 #f #f #t) (12 #t #f #f) (13 #f #t #f) (14 #f #f #t) (15 #t #f #f) (16 #f #t #f) (17 #f #f #t) (18 #t #f #f) (19 #f #t #f)

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 相互递归(1)

      相互递归就是多个函数互相定义,最常见的就是两个函数,比如f和g,f的定义中用到g,而g的定义中用到f。

    窗户
  • Scheme来实现八皇后问题(2)

      上一章讲了用1~n的排序来表示n皇后的解,然后通过枚举1~n所有的排列、判定谓词过滤所有排列得到最终的所有解。

    窗户
  • 相互递归(2)

      所有的相互递归都可以被转化为一般的递归,从而最终可以用lambda演算来完成。

    窗户
  • 安卓开发_关于WebView使用链接时调用浏览器显示的问题

    听着music睡
  • 开箱即用,一键集成 Redis 缓存

    Redis 是一个开源、高级的键值存储和一个适用的解决方案,用于构建高性能,可扩展的 Web 应用程序。支持更丰富的数据结构,例如 String、List、ha...

    用户7676729
  • 某公司golang面试题

    这两段程序的区别就一个地方,一个是数组,一个是slice 考察的点有两个,一个是数组和slice的区别,另外就是range的值传递 输出结果大家可以自己运行...

    anakinsun
  • EEG和MEG是否可以检测到小脑信号?

    请点击上面“思影科技”四个字,选择关注我们,思影科技专注于脑影像数据处理,涵盖(fMRI,结构像,DTI,ASL,EEG/ERP,FNIRS,眼动)等,希望专业...

    用户1279583
  • MySQL主从同步读写分离的集群配置

    大型网站为了解决大量的高并发访问问题,除了在网站实现分布式负载均衡,远远不够。到了数据业务层、数据访问层,如果还是传统的数据结...

    业余草
  • Go by Example 中文:使用函数自定义排序

    有时候我们想使用和集合的自然排序不同的方法对集合进行排序。例如,我们想按照字母的长度而不是首字母顺序对字符串排序。这里是一个 Go 自定义排序的例子。

    ccf19881030
  • 介绍几个JavaScript设计模式及场景应用

    当然我们可以用一个通俗的说法:设计模式是解决某个特定场景下对某种问题的解决方案。因此,当我们遇到合适的场景时,我们可能会条件反射一样自然而然想到符合这种场景的设...

    winty

扫码关注云+社区

领取腾讯云代金券