《The Little Schemer》知识点整理(五):我得天!都是星星

准备知识

  1. 所有 * 函数所处理的列表,都满足以下情况中的一种:

    • 空列表。
    • 一个原子 cons 在一个列表上。
    • 一个列表 cons 在另一个列表上。
  2. (and ...) 第一个参数为 false 则直接返回 false;(or ...) 第一个参数为 true 则直接返回 true。所以它们的问题可能不会全部问到。

  3. 一个 S-表达式要么是一个原子,要么是一个 S-表达式列表(也可以是空列表)。

  4. 注意区分 eq?=eqan?equal?

Scheme 十诫之第一诫(终极式)

  • 当对一个原子列表 lat 进行递归调用时,询问两个有关 lat 的问题:(null? lat)else
  • 当对一个数字 n 进行递归调用时,询问两个有关 n 的问题:(zero? n)else
  • 当对一个 S-表达式列表 l 进行递归调用时,询问三个有关 l 的问题:null? l(atom? (car l))else

Scheme 十诫之第四诫(终极式)

在递归时总是改变至少一个参数:

  • 当对一个原子列表 lat 进行递归调用时,使用 (car lat)
  • 当对数字 n 进行递归调用时,使用 (sub1 n)
  • 当对一个 S-表达式进行递归调用时,只要 (null? lat)(atom? (car l)) 都不为 true,那么就同时使用 (car lat)(cdr lat)

在递归时改变的参数,必须向着不断接近结束条件而改变。改变的参数必须在结束条件中得以测试:

  • 当使用 cdr 时,用 null? 测试是否结束。
  • 当使用 sub1 时,用 zero? 测试是否结束。

Scheme 十诫之第六诫

简化工作只在功能正确之后开展。

自定义函数

(rember* a l)

定义:移除列表 l 中的全部原子 a,以此类推。

实现:

1
2
3
4
5
6
7
8
9
10
11
(define rember*
(lambda (a l)
(cond
((null? l) (quote ()))
((atom? a)
(cond
((eq? (car l) a) (rember* a (cdr l)))
(else (cons (car l)
(rember* a (cdr l))))))
(else (cons (rember* a (car l))
(rember* a (cdr l)))))))

(insertR* new old l)

定义:在列表 l 中的所有原子 old 后面插入原子 new

实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
(define insertR*
(lambda (new old l)
(cond
((null? l) (quote ()))
((atom? (car l))
(cond
((eq? (car l) old)
(cons old
(cons new
(insertR* new old (cdr l)))))
(else (cons (car l)
(insertR* new old (cdr l))))))
(else (cons (insertR* new old (car l))
(insertR* new old (cdr l)))))))

比较 rember*insertR* 两个函数,看看是怎么问问题的。

(occur* a l)

定义:统计列表 l 中原子 a 出现的所有次数。

实现:

1
2
3
4
5
6
7
8
9
10
11
(define occur*
(lambda (a l)
(cond
((null? l) 0)
((atom? (car l))
(cond
((eq? (car l) a)
(add1 (occur* a (cdr l))))
(else (occur* a (cdr l)))))
(else (plus (occur* a (car l))
(occur* a (cdr l)))))))

(subst* new old l)

定义:把列表 l 中的所有原子 old 都替换为原子 new

实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
(define subst*
(lambda (new old l)
(cond
((null? l) (quote ()))
((atom? (car l))
(cond
((eq? (car l) old)
(cons new
(subst* new old (cdr l))))
(else (cons old
(subst* new old (cdr l)))))
(else (cons (subst* new old (car l))
(subst* new old (cdr l))))))))

(insertL* new old l)

定义:在列表 l 中的所有原子 old 前面插入原子 new

实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
(define insertL*
(lambda (new old l)
(cond
((null? l) (quote ()))
((atom? (car l))
(cond
((eq? (car l) old)
(cons new
(cons old
(insertL* new old (cdr l)))))
(else (cons old
(insertL* new old (cdr l)))))
(else (cons (insertL* new old (car l))
(insertL* new old (cdr l))))))))

(member* a l)

定义:判断原子 a 是否出现在列表 l 中。

实现:

1
2
3
4
5
6
7
8
9
(define member*
(lambda (a l)
(cond
((null? l) #f)
((atom? (car l))
(or (eq? (car l) a)
(member* a (cdr l))))
(else (or (member* a (car l))
(member* a (cdr l)))))))

回忆一下 or 的用法。

(leftmost l)

定义:找出非空 S-表达式列表 l 中最左边的原子。同时该列表不包含空列表元素。

实现:

1
2
3
4
5
(define leftmost
(lambda (l)
(cond
((atom? (car l)) (car l))
(else (leftmost a (cdr l))))))

(eqlist? l1 l2)

定义:判断两个列表是否相等。

思考:需要问 9 个问题,因为处理列表有 3 种情况,两个列表就是 9 种情况。

实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
(define eqlist?
(lambda (l1 l2)
(cond
((and (null? l1) (null? l2)) #t)
((and (null? l1) (atom? (car l))) #f)
((null? l1) #f)
((and (atom? (car l1)) (null? l2)) #f)
((and (atom? (car l1)) (atom? (car l2)))
(and (eqan? (car l1) (car l2))
(eqlist? (cdr l1) (cdr l2))))
((atom? (car l1)) #f)
((null? l2) #f)
((atom? (car l2)) #f)
(else (and (eqlist? (car l1) (car l2))
(eqlist? (cdr l1) (cdr l2)))))))

(and (null? l1) (null? l2))(or (null? l1) (null?l2)) 可以确定 3 种情况,以此简化一下:

1
2
3
4
5
6
7
8
9
10
11
(define eqlist?
(lambda (l1 l2)
(cond
((and (null? l1) (null? l2)) #t)
((or (null? l1) (null? l2)) #f)
((and (atom? (car l1)) (atom? (car l2)))
(and (eqan? (car l1) (car l2))
(eqlist? (cdr l1) (cdr l2))))
((or (atom? (car l1)) (atom? (car l2))) #f)
(else (and (eqlist? (car l1) (car l2))
(eqlist? (cdr l1) (cdr l2)))))))

(equal? s1 s2)

定义:判断两个 S-表达式是否相同。

实现:

1
2
3
4
5
6
7
8
(define equal?
(lambda (s1 s2)
(cond
((and (atom? s1) (atom? s2))
(eqan? s1 s2))
((atom? s1) #f)
((atom? s2) #f)
(else (eqlist? s1 s2)))))

同上,第二第三个问题可以归纳为 (or (atom? s1) (atom? s2)),简化版:

1
2
3
4
5
6
7
8
(define equal?
(lambda (s1 s2)
(cond
((and (atom? s1) (atom? s2))
(eqan? s1 s2))
((or (atom? s1) (atom? s2))
#f)
(else (eqlist? s1 s2)))))

接下来用 equal? 重写 eqlist?

1
2
3
4
5
6
7
(define eqlist?
(lambda (l1 l2)
(cond
((and (null? l1) (null? l2)) #t)
((or (null? l1) (null? l2)) #f)
(else (and (equal? (car l1) (car l2))
(eqlist? (cdr l1) (cdr l2)))))))

(rember s l)

定义:详见第三篇,这里是用任意 S-表达式列表 l 替代 lat,任意 S-表达式 s 替代原子 a 之后的版本。用到了上述的 equal?

实现:

1
2
3
4
5
6
7
(define rember
(lambda (s l)
(cond
((null? l) (quote ()))
((equal? (car l) s) (cdr l))
(else (cons (car l)
(rember s (cdr l)))))))

– EOF –