SICP——层次性结构（树），以及约定化的接口

范围

keywords：树、递归、对树映射；约定的序列化接口。
程序：count-leaves、deep-reverse、map、filter、accumulator、enumerate

树

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

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

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

• 表 x 的 length 是 (cdr x) 的 length + 1
• 空表长度为 0

(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?，它检查参数是否为序对。

(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

(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，以一个树为参数，返回一个表，元素是这棵树的树叶。

(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 是类似的

(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 是处理序列的强有力抽象。

(define (map proc items)
  (if (null? items)
      nil
      (cons (proc (car items))
            (map proc (cdr items)))))

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

• 将树看成子树的序列，对它使用 map，依次对各棵子树做 proc 返回结果的表。
• 当被处理的树是树叶，直接用因子去乘。

(define (scale-tree tree factor)
  (map (lambda (sub-tree)
         (if (pair? sub-tree)
             (scale-tree sub-tree factor)
             (* sub-tree factor)))
       tree))

序列作为一种约定的界面

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

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

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

(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)的一个表。

(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

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

(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。在一个过程定义中，如果在形参表的最后一个参数之前有一个点号，那么表明这一过程实际调用时，前面各个形式参数将以前面的实际参数位值。但最后一个形式参数以所有剩下的实际参数的表为值。

若我们有如下代码：

(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 过程。

(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

(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

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

(define (enumerate-tree tree)
  (cond ((null? tree) nil)
        ((not (pair? tree)) (list tree))
        (else (append (enumerate-tree (car tree))
                      (enumerate-tree (cdr tree))))))

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

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

重构

现在，我们运用信号流图来重构sum-odd-squares与even-fibs。

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

(define (sum-odd-squares tree)
  (accumulate +
              0
              (map square
                   (filter odd?
                           (enumerate-tree tree)))))

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

(define (even-fibs n)
  (accumulate cons
              nil
              (filter even?
                      (map fib
                           (enumerate-interval 0 n)))))