The Little Schemer读书笔记（二）

《The Little Schemer》读书笔记（第三章）。

第三章（Cons the Magnificent）伊始，书中引入了另一个函数rember（remove member的缩写）。rember从lat（list of atoms）中移除一个atom，所以需要把list拆开了再合上去，期间去除匹配到的atom。合并的操作是通过cons来完成的。

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

这个版本的rember，只能从lat中移除首个匹配的atom。

下面是第二戒律：

The Second Commandments: Use cons to build lists.

书中也给出的对于rember的文字解释：

The function rember checked each atom of the lat, one at a time, to see if it was the same as the atom and. If the car was not the same as the atom, we saved it to be consed to the final value later. When rember found the atom and, it dropped it, and consed the previous atoms back onto the rest of the lat.

根据这个描述，rember中cond部分可以简化成:

(cond
  ((null? lat) '())
  ((eq? a (car lat)) (cdr lat))
  (else (cons (car lat) (rember a (cdr lat)))))

接下来的内容涉及firsts函数，它的参数不再是list of atoms，而是list of lists。firsts返回一个list的节点list上的第一个节点。也就是说(firsts '((a b) (c d) (e f)))返回的是(a c e)。

书中对firsts的文字描述如下：

The function firsts takes one argument, a list, which is either a null list or contains only non-empty lists. It builds another list composed of the first S-expression of each internal list.

具体的代码如下：

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

然后引出第三条戒律：

The Third Commandment: When building a list, describe the first typical element, and then cons it onto the natural recursion.

接下来介绍的函数insertR的作用对象又回到了list of atoms。此函数的作用是再某个atom之后插入一个新的atom，调用形式为(insertR new old lat)。

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

insertR是在目标atom的右边插入新atom，那么接下来要出场的insertL就是在左边插入新的atom。insertL只要在 ((eq? old (car lat)) (cons old (cons new (cdr lat))))行上把new和old交换位置即可。

下一个出场的是subst，这个不是插入，而是替换，将old替换成new。还是简单地修改inserR的这一行 ((eq? old (car lat)) (cons old (cons new (cdr lat))))，找到old的时候只保留对new的cons操作即可。

subst的一个扩展版是subst2，调用形式为(subst2 new o1 o2 lat)。也就是被替换的既可以是o1也可以是o2，这个需要在深层的cond语句之中分别对o1和o2增加判断：

(cond
  ((eq? (car (lat) o1) (cons new (cdr lat))
  ((eq? (car (lat) o2) (cons new (cdr lat))
  ...)

接下来要引出的是multirember，之前介绍的rember的扩展版。在介绍multirember之前，让我们来复习以下rember的定义：

The function rember looks at each atom of a lat to see if it is the same as the atom a. If it’s not, rember saves the atom and proceeds. When it finds the first occurrence of a, it stops and gives the value (cdr lat), or the rest of the lat, so that the value returned is the original lat, with only that occurrence of a removed.

rember移除的是第一个出现的目标，而multirember则需要移除所有目标，其定义如下：

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

同样地，可以把insertR和insertL扩展到多匹配版本：

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

第四条戒律：

Always change at least one argument while recurring. It must be changed to be closer to termination. The changing argument must be tested in the termination condition: when using cdr, test termination with null?

最后把subst扩展成multisubst:

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

第三章结束。

（本篇完）