The Little Schemer 知识点整理（三）：用 cons 构筑恢宏

2018 年 12 月 05 日

Scheme 十诫之第二诫

使用 cons 来构建列表。

Scheme 十诫之第三诫

构建一个列表的时候，描述第一个典型的元素，之后 cons 该元素到一般性递归上。

Scheme 十诫之第四诫

在递归时总是改变至少一个参数。该参数必须向着不断接近结束条件而改变。改变的参数必须在结束条件中得以测试：当使用 cdr 时，用 null? 测试是否结束。

自定义函数

(rember a lat)

定义：rember 函数将一个原子 a 和一个列表 lat 作为参数，生成一个新列表，新列表为剔除了首个 a 的 lat。

实现：

(define rember
  (lambda (a lat)
    (cond
      ((null? lat) (quote ()))
      ((eq? (car lat) a) (cdr lat))
      (else (cons (car lat)
                  (rember a (cdr lat)))))))

(firsts l)

定义：firsts 函数以一个列表 l 为参数，该列表要么为空列表，要么只包含非空列表。该函数构建出一个新列表，新列表中的元素由列表 l 中每个内部列表的第一个 S-表达式组成。

实现：

(define firsts
  (lambda (l)
    (cond
      ((null? l) (quote ()))
      (else (cons (car (car l))
                  (firsts (cdr l)))))))

(insertR new old lat)

定义：insertR 函数有三个参数：原子 new 与 old，以及一个列表 lat。该函数在 lat 的第一个 old 后面插入 new，并返回新的列表。

实现：

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

(insertL new old lat)

定义：同上，不过是在列表 lat 中的第一个 old 前面插入 new。

实现：

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

(subst new old lat)

定义：用 new 替换列表 lat 中的第一个 old。

实现：

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

(subst2 new o1 o2 lat)

定义：用 new 替换列表 lat 中的第一个 o1 或者第一个 o2。

实现：

(define subst2
  (lambda (new o1 o2 lat)
    (cond
      ((null? lat) (quote ()))
      ((or (eq? (car lat) o1) (eq? (car lat) o2))
        (cons new (cdr lat)))
      (else (cons (car lat)
                  (subst2 new o1 o2 (cdr lat)))))))

(multirember a lat)

定义：类似于 rember，不过是把 lat 中的所有 a 都移除。

实现：

(define multirember
  (lambda (a lat)
    (cond
      ((null? lat) (quote ()))
      ((eq? (car lat) a) (multirember a (cdr lat)))
      (else (cons (car lat)
                  (multirember a (cdr lat)))))))

(multiinsertR new old lat)

定义：类似于 insertR，不过是在 lat 中的所有 old 后面都插入 new。

实现：

(define multiinsertR
  (lambda (new old lat)
    (cond
      ((null? lat) (quote ()))
      ((eq? (car lat) old)
        (cons old
              (cons new
                    (multiinsertR new old (cdr lat)))))
      (else (cons (car lat)
                  (multiinsertR new old (cdr lat)))))))

(multiinsertL new old lat)

定义：类似于 insertL，不过是在 lat 中的所有 old 前面插入 new。

实现：

(define multiinsertL
  (lambda (new old lat)
    (cond
      ((null? lat) (quote ()))
      ((eq? (car lat) old)
        (cons new
              (cons old
                    (multiinsertL new old (cdr lat)))))
      (else (cons (car lat)
                  (multiinsertL new old (cdr lat)))))))

(multisubst new old lat)

定义：类似于 subst，不过是用 new 替换列表 lat 中的所有 old。

实现：

(define multisubst
  (lambda (new old lat)
    (cond
      ((null? lat) (quote ()))
      ((eq? (car lat) old)
        (cons new
              (multisubst new old (cdr lat))))
      (else (cons (car lat)
                  (multisubst new old (cdr lat)))))))

EOF