SICP——层次性结构(树),以及约定化的接口

范围

keywords:树、递归、对树映射;约定的序列化接口。
程序count-leavesdeep-reversemapfilteraccumulatorenumerate

利用 cons 的闭包性,将序对用作 cons 的参数,就可以产生层次性结构(树)。

本身是序对的元素就成了树中的子树。因此,递归是处理树结构的一种很自然的工具。我们可以来看一个例子:

序列中求表长的 length 的方案是:

  • 表 x 的 length 是 (cdr x) 的 length + 1
  • 空表长度为 0
1
2
3
4
(define (length L)
(if (null? L)
0
(+ 1 (length (cdr L)))))

count-leaves 过程,统计一棵树中叶子的个数,其实方案是类似的:

  • 空表的 count-leaves 是 0
  • 在递归中,当我们去掉一个 car 时,就可能出现这个 car 是一棵子树的情况。所以正确的归约步骤应该是
    • 树 x 的 count-leaves 应该是 (car x) 的 count-leaves 与 (cdr x) 的 count-leaves 之和。
    • 树叶的 count-leaves 是 1

Scheme 提供基本过程pair?,它检查参数是否为序对。

1
2
3
4
5
(define (count-leaves x)
(cond ((null? x) 0) ; cond 中前两个条件的顺序很重要,因为空表将满足 null? 且同时不是序对
((not (pair? x)) 1) ; x 不是序对则 x 是叶子
(else (+ (count-leaves (car x)) ; 左子树
(count-leaves (cdr x)))))) ; 右子树

查看测试样例:

可以得知,过程length对于car是序对或者是序列的,也只算 1,cons (list 1 2)(list 3 4) 中(list 1 2)算长度 1,后面的 (list 3 4) 算长度 2。过程count-leaves则注意到了car也需要递归。

一些函数

对于序列的reverse过程,写一个deep-reverse过程,以一个表为参数,除了将表中的元素翻转过来之外,把其中的子树也翻转。

如果将reverse用于树,就是只将树的最外层翻转。类似分析,使用递归,将内层子树一起reverse

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
(define (reverse L)(reverse-iter L nil))
(define (reverse-iter list other)
(if (null? list)
other
(reverse-iter (cdr list)(cons(car list) other))))
(define (deep-reverse tree)
(cond ((null? tree) ; 空树
'()) ; Scheme 中 '() 表示空表
((not (pair? tree)) ; 叶子
tree) ; 返回本身
(else ; 递归地逆序左右子树
(reverse (list (deep-reverse (car tree))
(deep-reverse (cadr tree)))))))
(define x (list (list 1 2) (list 3 4)))
(reverse x)
;((3 4) (1 2))
(deep-reverse x)
;((4 3) (2 1))

写一个过程fringe,以一个树为参数,返回一个表,元素是这棵树的树叶。

1
2
3
4
5
6
7
8
9
10
(define (fringe tree)
(cond ((null? tree) '())
((not (pair? tree)) (list tree))
(else
(append (fringe (car tree))
(fringe (cdr tree))))))
(define x (list (list 1 2) (list 3 4)))
(fringe x)
;(1 2 3 4)

对树的映射 map

下面是一个与scale-list相似的过程,用一个因子乘上一棵树上所有的叶子。递归的思路和 count-leaves 是类似的

1
2
3
4
5
(define (scale-tree tree factor)
(cond ((null? tree) nil)
((not (pair? tree)) (* tree factor))
(else (cons (scale-tree (car tree) factor)
(scale-tree (cdr tree) factor)))))

map 是处理序列的强有力抽象。

1
2
3
4
5
(define (map proc items)
(if (null? items)
nil
(cons (proc (car items))
(map proc (cdr items)))))

map 与递归结合就也是处理树的一种强有力抽象。

  • 将树看成子树的序列,对它使用 map,依次对各棵子树做 proc 返回结果的表。
  • 当被处理的树是树叶,直接用因子去乘。
1
2
3
4
5
6
(define (scale-tree tree factor)
(map (lambda (sub-tree)
(if (pair? sub-tree)
(scale-tree sub-tree factor)
(* sub-tree factor)))
tree))

序列作为一种约定的界面

讲到数据抽象在工程中的作用。

借助这种思想,构建一种不会被数据表示的细节纠缠的程序。一种强有力的设计原理——使用约定的界面

过程1:以一棵树为参数,计算值为奇数的叶子的平方和。

1
2
3
4
5
6
(define (sum-odd-squares tree)
(cond ((null? tree) 0)
((not (pair? tree))
(if (odd? tree) (square tree) 0))
(else (+ (sum-odd-squares (car tree))
(sum-odd-squares (cdr tree))))))
  • 枚举出一棵树的树叶
  • 过滤它们,选出奇数
  • 求平方 (映射)
  • 用 + 来累积得到的结果,从 0 开始。

过程2:k 小于等于某个给定的整数 n,求所有是偶数的斐波那契数Fib(k)的一个表。

1
2
3
4
5
6
7
8
9
(define (even-fibs n)
(define (next k)
(if (> k n)
nil
(let ((f (fib k)))
(if (even? f)
(cons f (next (+ k 1)))
(next (+ k 1))))))
(next 0))
  • 枚举 k,k是从 0 到 n 的整数
  • (映射)对应每个 k 计算 Fib(k)
  • 过滤它们,从中选取相应的偶数
  • 用 cons 来累积得到的结果,从空表开始。

这种过程可以用一些级联处理步骤的方式来描述:

模块化结构是控制复杂性的一种威力强大的策略。由一些互相比较独立的组件组合构成的设计,有约定的界面使这些部件都能以比较灵活的方式相互连接,进一步推动人们去做模块化的设计。

映射 map

前面提过,不再赘述

过滤器 filter

过滤一个序列,从中选取满足某个给定的谓词的元素:

1
2
3
4
5
6
7
8
9
10
(define (filter predicate sequence)
(cond ((null? sequence) nil)
((predicate (car sequence))
(cons (car sequence)
(filter predicate (cdr sequence))))
(else (filter predicate (cdr sequence)))))
(filter odd? (list 1 2 3 4 5))
;(1 3 5)

下面来看一个 filter 的运用例子。

过程 +*list 可以取任意个数的实际参数。定义这种过程的一种方式是采取一种尾部带点记法形式的 define。在一个过程定义中,如果在形参表的最后一个参数之前有一个点号,那么表明这一过程实际调用时,前面各个形式参数将以前面的实际参数位值。但最后一个形式参数以所有剩下的实际参数的表为值。

若我们有如下代码:

1
2
3
4
5
(define (f x y . z) <body>)
(f 1 2 3 4 5 6)
(define (g . w) <body>)
(g 1 2 3 4 5 6)

则 x 为 1,y 为 2,z 是表(3 4 5 6),w 是表(1 2 3 4 5 6),g 是 0 个或多个参数调用。

下面写一个过程 same-parity,返回所有与第一个参数有着同样奇偶性质的参数形成的表。

  • 判断奇偶性质,可以用基本过程even?odd?
  • 传递给 filter 过程。
1
2
3
4
5
6
(define (same-parity x . others)
(cond ((odd? x) (cons x (filter odd? others)))
((even? x) (cons x (filter even? others)))))
(same-parity 1 2 3 4 5 6 7)
(1 3 5 7)

累加器 accumulator

1
2
3
4
5
6
7
8
9
10
11
12
13
14
(define (accumulate op initial sequence)
(if (null? sequence)
initial
(op (car sequence)
(accumulate op initial (cdr sequence)))))
(accumulate + 0 (list 1 2 3 4 5))
15
(accumulate * 1 (list 1 2 3 4 5))
120
(accumulate cons nil (list 1 2 3 4 5))
(1 2 3 4 5)

枚举 enumerate

枚举出一棵树的所有树叶的列表:

1
2
3
4
5
(define (enumerate-tree tree)
(cond ((null? tree) nil)
((not (pair? tree)) (list tree))
(else (append (enumerate-tree (car tree))
(enumerate-tree (cdr tree))))))

枚举一个给定区间的整数序列:

1
2
3
4
(define (enumerate-interval low high)
(if (> low high)
nil
(cons low (enumerate-interval (+ low 1) high))))

重构

现在,我们运用信号流图来重构sum-odd-squareseven-fibs

sum-odd-squares:枚举一棵树的树叶/过滤剩下奇数/求每个元素的平方/从0累加

1
2
3
4
5
6
(define (sum-odd-squares tree)
(accumulate +
0
(map square
(filter odd?
(enumerate-tree tree)))))

even-fibs:枚举 0~n 的序列/求 Fib(k)/过滤剩下偶数/ 从 nil 开始 cons 成一个表

1
2
3
4
5
6
(define (even-fibs n)
(accumulate cons
nil
(filter even?
(map fib
(enumerate-interval 0 n)))))