The Little Schemer 知识点整理（五）：我得天！都是星星

2018 年 12 月 13 日

准备知识

  1. 所有 * 函数所处理的列表，都满足以下情况中的一种：

    • 空列表。
    • 一个原子 cons 在一个列表上。
    • 一个列表 cons 在另一个列表上。
  2. (and ...) 第一个参数为 false 则直接返回 false；(or ...) 第一个参数为 true 则直接返回 true。所以它们的问题可能不会全部问到。
  3. 一个 S-表达式要么是一个原子，要么是一个 S-表达式列表（也可以是空列表）。
  4. 注意区分 eq?、=、eqan? 和 equal?。

Scheme 十诫之第一诫（终极式）

  • 当对一个原子列表 lat 进行递归调用时，询问两个有关 lat 的问题：(null? lat) 和 else。
  • 当对一个数字 n 进行递归调用时，询问两个有关 n 的问题：(zero? n) 和 else。
  • 当对一个 S-表达式列表 l 进行递归调用时，询问三个有关 l 的问题：null? l、(atom? (car l)) 和 else。

Scheme 十诫之第四诫（终极式）

在递归时总是改变至少一个参数：

  • 当对一个原子列表 lat 进行递归调用时，使用 (car lat)。
  • 当对数字 n 进行递归调用时，使用 (sub1 n)。
  • 当对一个 S-表达式进行递归调用时，只要 (null? lat) 和 (atom? (car l)) 都不为 true，那么就同时使用 (car lat) 和 (cdr lat)。

在递归时改变的参数，必须向着不断接近结束条件而改变。改变的参数必须在结束条件中得以测试：

  • 当使用 cdr 时，用 null? 测试是否结束。
  • 当使用 sub1 时，用 zero? 测试是否结束。

Scheme 十诫之第六诫

简化工作只在功能正确之后开展。

自定义函数

(rember* a l)

定义：移除列表 l 中的全部原子 a，以此类推。

实现：

(define rember*
  (lambda (a l)
    (cond
      ((null? l) (quote ()))
      ((atom? a)
        (cond
          ((eq? (car l) a) (rember* a (cdr l)))
          (else (cons (car l)
                      (rember* a (cdr l))))))
      (else (cons (rember* a (car l))
                  (rember* a (cdr l)))))))

(insertR* new old l)

定义：在列表 l 中的所有原子 old 后面插入原子 new。

实现：

(define insertR*
  (lambda (new old l)
    (cond
      ((null? l) (quote ()))
      ((atom? (car l))
        (cond
          ((eq? (car l) old)
            (cons old
                  (cons new
                        (insertR* new old (cdr l)))))
          (else (cons (car l)
                      (insertR* new old (cdr l))))))
      (else (cons (insertR* new old (car l))
                  (insertR* new old (cdr l)))))))

比较 rember* 和 insertR* 两个函数，看看是怎么问问题的。

(occur* a l)

定义：统计列表 l 中原子 a 出现的所有次数。

实现：

(define occur*
  (lambda (a l)
    (cond
      ((null? l) 0)
      ((atom? (car l))
        (cond
          ((eq? (car l) a)
            (add1 (occur* a (cdr l))))
          (else (occur* a (cdr l)))))
      (else (plus (occur* a (car l))
                  (occur* a (cdr l)))))))

(subst* new old l)

定义：把列表 l 中的所有原子 old 都替换为原子 new。

实现：

(define subst*
  (lambda (new old l)
    (cond
      ((null? l) (quote ()))
      ((atom? (car l))
        (cond
          ((eq? (car l) old)
            (cons new
                  (subst* new old (cdr l))))
          (else (cons old
                      (subst* new old (cdr l)))))
      (else (cons (subst* new old (car l))
                  (subst* new old (cdr l))))))))

(insertL* new old l)

定义：在列表 l 中的所有原子 old 前面插入原子 new。

实现：

(define insertL*
  (lambda (new old l)
    (cond
      ((null? l) (quote ()))
      ((atom? (car l))
        (cond
          ((eq? (car l) old)
            (cons new
                  (cons old
                        (insertL* new old (cdr l)))))
          (else (cons old
                      (insertL* new old (cdr l)))))
      (else (cons (insertL* new old (car l))
                  (insertL* new old (cdr l))))))))

(member* a l)

定义：判断原子 a 是否出现在列表 l 中。

实现：

(define member*
  (lambda (a l)
    (cond
      ((null? l) #f)
      ((atom? (car l))
        (or (eq? (car l) a)
            (member* a (cdr l))))
      (else (or (member* a (car l))
                (member* a (cdr l)))))))

回忆一下 or 的用法。

(leftmost l)

定义：找出非空 S-表达式列表 l 中最左边的原子。同时该列表不包含空列表元素。

实现：

(define leftmost
  (lambda (l)
    (cond
      ((atom? (car l)) (car l))
      (else (leftmost a (cdr l))))))

(eqlist? l1 l2)

定义：判断两个列表是否相等。

思考：需要问 9 个问题，因为处理列表有 3 种情况，两个列表就是 9 种情况。

实现：

(define eqlist?
  (lambda (l1 l2)
    (cond
      ((and (null? l1) (null? l2)) #t)
      ((and (null? l1) (atom? (car l))) #f)
      ((null? l1) #f)
      ((and (atom? (car l1)) (null? l2)) #f)
      ((and (atom? (car l1)) (atom? (car l2)))
        (and (eqan? (car l1) (car l2))
             (eqlist? (cdr l1) (cdr l2))))
      ((atom? (car l1)) #f)
      ((null? l2) #f)
      ((atom? (car l2)) #f)
      (else (and (eqlist? (car l1) (car l2))
                 (eqlist? (cdr l1) (cdr l2)))))))

(and (null? l1) (null? l2)) 和 (or (null? l1) (null?l2)) 可以确定 3 种情况，以此简化一下：

(define eqlist?
  (lambda (l1 l2)
    (cond
      ((and (null? l1) (null? l2)) #t)
      ((or (null? l1) (null? l2)) #f)
      ((and (atom? (car l1)) (atom? (car l2)))
        (and (eqan? (car l1) (car l2))
             (eqlist? (cdr l1) (cdr l2))))
      ((or (atom? (car l1)) (atom? (car l2))) #f)
      (else (and (eqlist? (car l1) (car l2))
                 (eqlist? (cdr l1) (cdr l2)))))))

(equal? s1 s2)

定义：判断两个 S-表达式是否相同。

实现：

(define equal?
  (lambda (s1 s2)
    (cond
      ((and (atom? s1) (atom? s2))
        (eqan? s1 s2))
      ((atom? s1) #f)
      ((atom? s2) #f)
      (else (eqlist? s1 s2)))))

同上，第二第三个问题可以归纳为 (or (atom? s1) (atom? s2))，简化版：

(define equal?
  (lambda (s1 s2)
    (cond
      ((and (atom? s1) (atom? s2))
        (eqan? s1 s2))
      ((or (atom? s1) (atom? s2))
        #f)
      (else (eqlist? s1 s2)))))

接下来用 equal? 重写 eqlist?：

(define eqlist?
  (lambda (l1 l2)
    (cond
      ((and (null? l1) (null? l2)) #t)
      ((or (null? l1) (null? l2)) #f)
      (else (and (equal? (car l1) (car l2))
                 (eqlist? (cdr l1) (cdr l2)))))))

(rember s l)

定义：详见第三篇，这里是用任意 S-表达式列表 l 替代 lat，任意 S-表达式 s 替代原子 a 之后的版本。用到了上述的 equal?。

实现：

(define rember
  (lambda (s l)
    (cond
      ((null? l) (quote ()))
      ((equal? (car l) s) (cdr l))
      (else (cons (car l)
                  (rember s (cdr l)))))))
EOF

Twinkle 的博客
瞎折腾