Marvin's Blog【程式人生】

Ability will never catch up with the demand for it

24 Sep 2020

The Little Schemer读书笔记(三)

第四章(Numbers Games)

这一章使用递归来表达正整数。首先介绍两个操作:add1和sub1,分别对数进行加一和减一操作。

add1的定义如下:

(define add1
  (lambda (n)
    (+ n 1)))

sub1的定义如下:

(define sub1
    (lambda (n)
      (- n 1)))

负数不在我们讨论之列,因为(sub1 0)会产生负数。所以(sub1 0)在此章中是不被允许的。

另外还用到scheme自带的zero?函数,用来判断一个数值是否为0.

有了这些原语操作,就可以来定义加法操作了:

 (define 0+
    (lambda (n m)
      (cond
        ((zero? m) n)
        (else (add1 (+ n (sub1 m)))))))

上面加法操作看上去有点奇怪。其实质是通过sub1的递归,让m变为0.然后在递归返回的时候通过add1,把m变为0的过程逆向施加到n上,结果就变成n+m的值了。

采用同样的思路可以用来定义减法:

 (define 0-
    (lambda (n m)
      (cond
        ((zero? m) n)
        (else (sub1 (- n (sub1 m)))))))

减法的要义是使用sub1将m递归变为0, 在递归返回的过程中通过sub1把m变为0的过程逆向施加到n上,导致n值变小。

文中对(0- n m)操作的描述:

It takes two numbers as arguments, and reduces the second until it hits zero. It subtracts one from the result as many times as it did to cause the second one to reach zero.

接下来要介绍的操作叫做addtup。tup是可以为空的list of numbers,代表一组数值。addtup的作用是把这组中的所有数值相加。

对于数值,其递归终止条件是(zero? n),而不是(null? lat),所以第一条戒律需要进行修正:

The First Commandment (first revision): When recurring on a list of atoms, lat, ask two questions about it: (null? lat) and else. When recurring on a number, n, ask two questions about it: (zero? n) and else.

让我们来定义addtup:

 (define addtup
    (lambda (tup)
      (cond
        ((null? tup) 0)
        ((0+ (car tup) (addtup (cdr tup)))))))

紧接着出场的是第四戒律:

The Fourth Commandment (first revision): 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? and when using sub1, test termination with zero?.

下一位出场的是乘法:

 (define 0*
    (lambda (n m)
      (cond
        ((zero? m) 0)
        (else (0+ n (0* n (sub1 m)))))))

上面代码的要义就是把m个n相加。如下所示:

(0* 12 3) = 12 + (0* 12 2)
              = 12 + 12 + (0* 12 1)
              = 12 + 12 + 12 + (0* 12 0)
              = 12 + 12 + 12 + 0

呼之欲出的是第五戒律:

The Fifth Commandment: When building a value with +, always use 0 for the value of the terminating line, for adding 0 does not change the value of an addition. When building a value with *, always use 1 for the value of the terminating line, for multiplying by 1 does not change the value of a multiplication. When building a value with cons, always consider () for the value of the terminating line.

下一个要学习的函数是tup+,用于把两个数值list相加,这里假设两个list含有的数值个数相同:

 (define tup+
    (lambda (tup1 tup2)
      (cond
        ((and (null? tup1) (null? tup2)) '())
        (else
          (cons (0+ (car tup1) (car tup2)) (tup+ (cdr tup1) (cdr tup2)))))))

允许两个list不等长的话,可以得到:

 (define tup+
    (lambda (tup1 tup2)
      (cond
        ((and (null? tup1) (null? tup2)) '())
        (else
          (cons (0+ (car tup1) (car tup2)) (tup+ (cdr tup1) (cdr tup2)))))))

接下来要学习的是比大小。(0> n m)用来对比n和m的大小。具体的递归过程是同时削减n和m,看哪个先减到0,代码如下:

 (define 0>
    (lambda (n m)
      (cond
        ((zero? n) #f)
        ((zero? m) #t)
        (else (0> (sub1 n) (sub1 m))))))

上面的逻辑是如果n先减到0,那么n肯定不会比m大,结果为#f,否则为#t。下面将要引入的0<函数正好反过来,则需要先判断m是否先减到0,然后再判断n。

 (define 0<
    (lambda (n m)
      (cond
        ((zero? m) #f)
        ((zero? n) #t)
        (else (0< (sub1 n) (sub1 m))))))

以此类推,判断相等的话,只要两个同时减到0即可:

 (define 0=
    (lambda (n m)
      (cond
        ((0< n m) #f)
        ((0> n m) #f)
        (else #t))))

或者

(define 0=
    (lambda (n m)
      (cond
        ((zero? m) (zero? n))
        ((zero? n) #f)
        (else (0= (sub1 n) (sub1 m))))))

现在来定义幂函数:

 (define 0^
    (lambda (n m)
      ((zero? m) 1)
      (else (0* n (0^ n (sub1 m))))))

上面的操作是把幂操作转化为乘操作,然后乘操作在暗地里其实被转为加操作。

那么怎么定义除法的,先列举以下递归过程:

(0/ 15 4) = 1 + (0/ 11 4)
            = 1 + (1 + (0/ 7 4))
            = 1 + (1 + (1 + (0/ 3 4)))
            = 1 + (1 + (1 + 0))

其scheme代码如下:

 (define 0/
    (lambda (n m)
      (cond
        ((0< n m) 0)
        (else (add1 (0/ (0- n m) m))))))

画风一转,书中的例子又回到了list of atoms身上,这回引出的是length函数,用来统计list中atom的个数:

 (define length
    (lambda (lat)
      (cond
        ((null? lat) 0)
        (else (add1 (length (cdr lat)))))))

pick函数从lat中选出相应位置的atom。比如(pick 2 '(a b c)返回b:

 (define pick
    (lambda (n lat)
      (cond
        ((zero? (sub1 n)) (car lat))
        (else (pick (sub1 n) (cdr lat))))))

rempick则删除相应位置的atom:

(define rempick
    (lambda (n lat)
      (cond
        ((zero? (sub1 n)) (cdr lat))
        (else (cons (car lat) (rempick (cdr lat)))))))

下一个函数是no-nums,也就是把list of atoms里面的number全部移除。(no-nums '(5 pears 6 prunes 9 dates))返回(pears prunes dates)

 (define no-nums
    (lambda (lat)
      (cond
        ((null? lat) '())
        (else (cond
                ((number? (car lat)) (no-nums (cdr lat)))
                (else (cons (car lat) (no-nums (cdr lat)))))))))

同理,可以有all-nums,在lat中挑出所有number:

 (define all-nums
    (lambda (lat)
      (cond
        ((null? lat) '())
        (else
          (cond
            ((number? (car lat)) (cons (car lat) (all-nums (cdr lat))))
            (else (all-nums (cdr lat))))))))

下面出场的是eqan?,用来比较两个atom,如果atom是number的话,则用0=来比较:

 (define eqan?
    (lambda (a1 a2)
      (cond
        ((and (number? a1) (number? a2)) (0= a1 a2))
        ((or (number? a1) (number? a2)) #f)
        (else (eq? a1 a2)))))

马上又来一个occur,用来统计一个atom在lat中出现的次数:

 (define occur
    (lambda (a lat)
      (cond
        ((null? lat) 0)
        (else (cond
                ((eq? (car lat) a) (add1 (occur a (cdr lat))))
                (else (occur a (cdr lat))))))))

下面来顶一个一个函数one?:

 (define one?
    (lambda (n)
      (= n 1)))

one?的作用很简单,就是判断一个number是否为1,可以用这个函数来重写rempick:

 (define rempick
    (lambda (n lat)
      (cond
        ((one? n) (cdr lat))
        (else (cons (car lat) (rempick (sub1 n) (cdr lat)))))))

到此位置,第四章(Numbers Games)就结束了。

(本篇完)

comments powered by Disqus