The Little Schemer 知识点整理（四）：数字游戏

2018 年 12 月 06 日

准备知识

所有数字都是原子；
暂时只考虑非负整数，0、1、2、3……；
用 (zero? n) 判断数字 n 是否为零；
tup 是元组 Tuple 的缩写，用来表示一个数字列表，() 也是一个 tup；
(and a b) : 类似于 (or a b)，&& 和 || 的区别(?)；
= 用来测试数字类型的原子，eq? 用来测试其他类型的原子；
number? 是一个基本函数，判断参数是否为数值型原子；
空心加号（区别于数学符号+）打不出来，所以原书中的空心加号用 plus 代替；

重要

以下定义可以说明我们的操作并不违反 Scheme 十诫。详见起飞式。

zero? 之于数字相当于 null? 之于列表；
add1 之于数字，相当于 cons 之于列表。

Scheme 十诫之第一诫（起飞式）

当对一个原子列表 lat 进行递归调用时，询问两个有关 lat 的问题：(null? lat) 和 else。
当对一个数字 n 进行递归调用时，询问两个有关 n 的问题：(zero? n) 和 else。

Scheme 十诫之第四诫（起飞式）

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

Scheme 十诫之第五诫

当用 plus 构建一个值时，总是使用 0 作为结束代码行的值，因为加上 0 不会改变加法的值。
当用 × 构建一个值时，总是使用 1 作为结束代码行的值，因为乘以 1 不会改变乘法的值。
当用 cons 构建一个值时，总是考虑把 () 作为结束代码行的值。

自定义函数

(add1 n)

定义：n 加一。

实现：

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

(sub1 n)

定义：n 减一。

实现：

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

(plus n m)

打不出空心加号，用 plus 代替

定义：把 n 与 m 相加。用到了上面定义的 add1 和 sub1，以下函数的用法相似。

实现：

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

(minus n m)

打不出空心减号，用 minus 代替

定义：把 n 与 m 相减。

实现：

(define minus
  (lambda (n m)
    (cond
      ((zero? m) n)
      (else (sub1 (minus n (sub1 m)))))))

(addtup tup)

定义：通过统计参数 tup 中所有数字之和来构建一个新的数字。

实现：

(define addtup
  (lambda (tup)
    (cond
      ((null? tup) 0)
      (else (plus (car tup) (addup (cdr tup)))))))

(× n m)

定义：把 n 与 m 相乘。

实现：

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

(tup+ tup1 tup2)

定义：对于相同长度的 tup1 和 tup2，其将 tup1 的第一个数字加到 tup2 的第一个数字上，然后将tup1 的第二个数字加到 tup2 的第二个数字上，以此类推，构建出结果一个新的 tup。

实现：

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

还可以改造成对任意两个 tup 的 tup+：

(define tup+
  (lambda (tup1 tup2)
    (cond
      ((null? tup1) tup2)
      ((null? tup2) tup1)
      (else (cons (plus (car tup1) (car tup2))
                  (tup+ (cdr tup1) (cdr tup2)))))))

(> n m)

定义：比较 n 与 m 的大小，如果前者大于后者，则返回 #t，否则返回 #f。

实现：

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

注意两个条件的顺序，下同。

(< n m)

定义：比较 n 与 m 的大小，如果前者小于后者，则返回 #t，否则返回 #f。

实现：

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

(= n m)

定义：比较 n 与 m 的大小，如果两者相等，则返回 #t，否则返回 #f。

实现：

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

或者：

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

(↑ n m)

定义：计算 n 的 m 次方。

实现：

(define ↑
  (lambda (n m)
    (cond
      ((zero? m) 1)
      (else (× n (↑ n (sub1 m)))))))

(÷ n m)

定义：把 n 与 m 相除，只求商。

实现：

(define ÷
  (lambda (n m)
    (cond
      ((< n m) 0)
      (else (add1 (÷ (minus n m) m))))))

(length lat)

定义：求列表 lat 包含的元素个数。

实现：

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

(pick n lat)

定义：获取列表 lat 中的第 n 个元素。

实现：

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

(rempick n lat)

定义：剔除列表 lat 中的第 n 个元素，以此构建一个新列表。

实现：

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

或者（使用下述函数 one?）：

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

(no-nums lat)

定义：返回一个列表，该列表移除了原始 lat 中的所有数字原子。

实现：

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

(all-nums lat)

定义：返回一个列表，该列表找出原始 lat 中的所有数字原子，并组成一个新的 tup。

实现：

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

(eqan? a1 a2)

定义：如果参数 a1 和 a2 是同一个原子则返回 true（#t）。

实现：

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

(occur a lat)

定义：统计原子 a 在列表 lat 中出现的次数。

实现：

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

(one? n)

定义：如果 n 为 1，则返回 #t，否则返回 #f。

实现：

(define one?
  (lambda (n)
    (cond
      ((zero? (sub1 n)) #t)
      (else #f))))

★ 或者简化并移除 (cond ...)：

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

EOF