《The Little Schemer》知识点整理(四):数字游戏

准备知识

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

重要

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

  1. zero? 之于数字相当于 null? 之于列表;
  2. 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 加一。

实现:

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

(sub1 n)

定义:n 减一。

实现:

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

(plus n m)

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

定义:把 nm 相加。用到了上面定义的 add1sub1,以下函数的用法相似。

实现:

1
2
3
4
5
(define plus
(lambda (n m)
(cond
((zero? m) n)
(else (add1 (plus n (sub1 m)))))))

(minus n m)

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

定义:把 nm 相减。

实现:

1
2
3
4
5
(define minus
(lambda (n m)
(cond
((zero? m) n)
(else (sub1 (minus n (sub1 m)))))))

(addtup tup)

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

实现:

1
2
3
4
5
(define addtup
(lambda (tup)
(cond
((null? tup) 0)
(else (plus (car tup) (addup (cdr tup)))))))

(× n m)

定义:把 nm 相乘。

实现:

1
2
3
4
5
(define ×
(lambda (n m)
(cond
((zero? m) 0)
(else (plus n (× n (sub1 m)))))))

(tup+ tup1 tup2)

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

实现:

1
2
3
4
5
6
(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+

1
2
3
4
5
6
7
(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)

定义:比较 nm 的大小,如果前者大于后者,则返回 #t,否则返回 #f

实现:

1
2
3
4
5
6
(define >
(lambda (n m)
(cond
((zero? n) #f)
((zero? m) #t)
(else (> (sub1 n) (sub1 m))))))

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

(< n m)

定义:比较 nm 的大小,如果前者小于后者,则返回 #t,否则返回 #f

实现:

1
2
3
4
5
6
(define <
(lambda (n m)
(cond
((zero? m) #f)
((zero? n) #t)
(else (< (sub1 n) (sub1 m))))))

(= n m)

定义:比较 nm 的大小,如果两者相等,则返回 #t,否则返回 #f

实现:

1
2
3
4
5
6
(define =
(lambda (n m)
(cond
((zero? m) (zero? n))
((zero? n) #t)
(else (= (sub1 n) (sub1 m))))))

或者:

1
2
3
4
5
6
(define =
(lambda (n m)
(cond
((> n m) #f)
((< n m) #f)
(else #t))))

(↑ n m)

定义:计算 nm 次方。

实现:

1
2
3
4
5
(define
(lambda (n m)
(cond
((zero? m) 1)
(else (× n ( n (sub1 m)))))))

(÷ n m)

定义:把 nm 相除,只求商。

实现:

1
2
3
4
5
(define ÷
(lambda (n m)
(cond
((< n m) 0)
(else (add1 (÷ (minus n m) m))))))

(length lat)

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

实现:

1
2
3
4
5
(define length
(lambda (lat)
(cond
((null? lat) 0)
(else (add1 (length (cdr lat)))))))

(pick n lat)

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

实现:

1
2
3
4
5
(define pick
(lambda (n lat)
(cond
((zero? (sub1 n)) (car lat))
(else (pick (sub1 n) (cdr lat))))))

(rempick n lat)

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

实现:

1
2
3
4
5
6
(define rempick
(lambda (n lat)
(cond
((zero? (sub1 n)) (cdr lat))
(else (cons (car lat)
(rempick (sub1 n) (cdr lat)))))))

或者(使用下述函数 one?):

1
2
3
4
5
6
(define rempick
(lambda (n lat)
(cond
((one? n) (cdr lat))
(else (cons (car lat)
(rempick (sub1 n) (cdr lat)))))))

(no-nums lat)

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

实现:

1
2
3
4
5
6
7
(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。

实现:

1
2
3
4
5
6
7
8
(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)

定义:如果参数 a1a2 是同一个原子则返回 true(#t)。

实现:

1
2
3
4
5
6
7
8
(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 中出现的次数。

实现:

1
2
3
4
5
6
(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

实现:

1
2
3
4
5
(define one?
(lambda (n)
(cond
((zero? (sub1 n)) #t)
(else #f))))

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

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

– EOF –