构造数据抽象
数据抽象导引
假设make-rat 能使分数最简化
假设 number 能获得分子，denom 能获得分母
1
2
3
4
5
| (define (add-rat x y)
(make-rat (+ (*(number x) (denom y))
(* (denom x) (number y)))
(* (denom x) (denom y)))
)
|
1
2
3
4
5
6
| (define (sub-rat x y)
(make-rat (- (*(number x) (denom y))
(*(denom x) (number x))
)
(* (denom x) (denom y)))
)
|
1
2
3
4
| (define (mul-rat x y)
(make-rat (* (number x) (number y)
(* (denom x) (denom y)))
)
|
1
2
3
4
| (define (div-rat x y)
(make-rat (* (number x) (denom y))
(* (denom y) (number x)))
)
|
1
2
3
4
| (define (equal-rat x y)
(= (* (number x) (denom y)
(* (denom y) (number x)))
)
|
1
2
3
| (define x (cons 1 2))
(car x)
(cdr x)
|
得到的结果分别是 1 和 2
1
2
3
4
5
6
7
| (define (make-rat n d)
(let (
(g (gcd n d))
)
(cons (/ n g) (/ d g))
)
)
|
而 gdc 最大公约数,之前我们介绍过， 可以通过中国余数的方式获得
1
2
3
4
| (define (gcd n d)
(if (= 0 d) (n)
(gcd (d (reminder n d))
)
|
层次性数据和闭包性质
序对为我们提供一种用于构造复合数据的基本“粘结剂”。我们还可以通过它去组合起序对。
1
2
3
| (cons (cons 1 2) (cons 1 2))
(cons (cons 1 (cons 2 3)) 4)
|
（⚠️ 上面的方式不是序列。）
我们可以建立元素本身也是序对的序对，这就是表结构得以作为一种表示工具的根本基础。我们把这种能力称为cons的闭包。
术语 闭包 来自于抽象代数。在抽象代数里，一集元素称为在某个元算（操作）之下封闭。如果将该运算应用于这一集合中的元素，产生出的仍是该集合里的元素。
序列的表示
利用序对可以构造出的一类有用结构是序列。 和Java的数据结构比较对应数据结构是链表
1
2
3
4
| (cons 1
(cons 2
(cons 3
(cons 4 nil))))
|
通过嵌套的cons形成的这样一个序对的序列称为一个表， 它和上面的程序等价
我们将car看作选取表的第一项的操作，将cdr看作选取表中除去第一项之后剩下的所有项形成的子表
比方说我们想得到表的第n项
1
2
3
| (define (list-ref item)
(if (= 0 item) (car item)
(list-ref (cdr item) (- item 1))))
|
比方说append
1
2
3
4
5
6
| (define (append list1 list2)
(if (= nil list1)
(list2)
(cons (car list1) (append((cdr list1) list2)))
)
)
|
首先找到list1的最后一个元素。 把list1最后一个元素的next设置为list2. 依次递归。其中过程中的list1和参数的list1不等价。
对表的映射
$(1\ 2 \ 3) * 3 = (3 \ 6 \ 9)$
1
2
3
4
5
6
7
8
9
| (define (scale-list items factor)
(if
( = nil items)
(nil)
(
(cons (* (car items) factor) (scale-list (crd items) factor))
)
)
)
|
我们将其中的公共模式表述成一个高阶过程，这个高阶过程我们称之为map。返回将这一个过程应用于表中各个元素得到的结果形成的表
通式为
1
2
3
4
5
6
7
8
9
| (define (map proc items)
(if (= nil items)
(nil)
(cons
(proc (car items))
(map proc (crd items))
)
)
)
|
有了这个公式我们可以简化上述集合的乘法
1
2
3
4
5
6
| (define (scale-list items factor)
(map (lambda (x)
(* x factors)
)
items)
)
|
层次性结构
1
| (cons (list 1 2) (list 3 4))
|
我们把这种数据结构称之为树
1
2
3
4
5
6
7
8
9
10
| (define (count-leaves x)
(cond
((null? x) 0)
((pair? x)
(+ (count-leaves (car x))
(count-leaves (cdr x))
))
(else 1)
)
)
|
其中pair? 的作用是检查是不是序对
对树的映射
1
2
3
4
5
6
7
8
9
10
11
| (define (scale-tree tree factor)
(map (lambda (sub-tree)
(if
(pair? sub-tree)
(scale-tree sub-tree factor)
(* factor sub-tree)
)
)
tree
)
)
|
序列作为一种约定的界面
以一棵树为参数，求值为奇数叶子的平方和
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| (define (sum-odd-squares tree)
(map (lambda (sub-tree)
(cond ((null? sub-tree)
0
)
(if (pair? sub-tree)
(+ (sum-odd-squares (car sub-tree))
(sum-odd-squares (cdr sub-tree))
)
(if (= 1 (reminder sub-tree 2))
(square sub-tree)
)
)
)
tree)
)
|
构造偶数的斐波那契数列的表
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
| (define (fibs-iter n_1 n_2 cur N total)
(if (= cur N)
total
(fibs-iter (+ n_1 n_2) n_1 (+ cur 1) N (+ n_1 total )))
)
(define (fibs N)
(fibs-iter 1 0 0 N 0)
)
(define (even-fibs n)
( (lambda (k)
(> k n)
nil
(if (even? (fibs n))
(cons (fibs n)
)
)
)
(lambda
(sub-list k)
(if (
(> k n)
nil
(if
(even? (fibs n))
(cons (fibs n) sub-list)
)
(
(< k n)
()
)
)
)
)
)
|