3. 层次性数据和闭包¶

前述我们使用两个数值数据进行cons进行构造序对。这提供了一种将数据粘合的方式，于是我们还可以将cons的序对进行构造cons。这称为“盒子和指针” 每个对象表示为一个指向盒子的指针。如果(cons 1 2)，则对应这个cons盒子第一个指针指向数字1本身，第二个指针指向数字2本身。那么(cons (cons 1 2) (cons 3 4))就是一个盒子的第一个指针指向另一个盒子，被指向的这个盒子是前述的那个指向1和2的盒子，当然，这个盒子的第二个指针指向了另一个指向3和4的盒子。这样可以用cons组合任何形式的数据。

可以建立元素本身也是序对的序对，这就表结构得以作为一种表示工具的根本基础，这称为“闭包性质”。

注解

“闭包”一词来自抽象代数。在抽象代数中，如果将这种运算应用于一集中的元素，产生的仍然是该集中的元素，则称一集元素称为在某个运算（或操作）下封闭。

通过它组合的数据对象得到的结果本身还可以通过同样的操作再进行组合。闭包性质是任何一种组合功能的威力的关键要素，因为它可以建立起层次性结构，这种结构从一部分开始，而其中各个部分又是由它们的部分构成，并且可以如此继续下去。

之前的运算中，数值数据的运算结果仍是数值数据，就已经利用了闭包性质。所有的程序都依赖的一个事实是：组合式的成员本身还可以是组合式。

3.1. 序列的表示¶

利用序对可以构造的有用结构是序列。序列的表示方式很多，在这里我们使用序对的链表来表示。链表结点的值是序对的第一个元素，后继链表是序对的第二个元素。

(define nil '())
(cons 1
    (cons 2
        (cons 3
            (cons 4 nil))))

通过嵌套的cons形成的序对的序列称为一个表。这种操作太常见了，但是这样构造起来比较麻烦，所以使用基本操作list可以产生一个表：

(list 1 2 3 4)

之前对cons序对进行car和cdr操作时，car取出cons的首个元素，cdr取出cons的第二个元素。由于list也是由cons构成的，我们同样可以对list使用car和cdr，其中car就是取list的首元素，cdr就是取list的除首元素的后继list。另外，cons可以连接一个元素和list来构成一个新的list。以下操作都是合法的：

(define one-through-four (list 1 2 3 4))
(car one-through-four)
(cdr one-through-four)
(car (cdr one-through-four))
(cons 10 one-through-four)
(cons 5 one-through-four)

定义了表之后，我们可以为表编写一些操作。首先就是取值：一个过程list-ref接收一个表和一个非负整数n，其返回值为列表中第n个元素。

(define (list-ref l n)
    (cond ((= n 0) (car l))
        (else ( list-ref (cdr l) (- n 1)))
    )
)

只要n小于列表l的长度都可以正常执行，不然就要对一个空表进行cdr，则会报错。

程序中经常会遇到遍历整个表，名为null?的基本操作可以检查参数是否为空表。例如计算list的长度就是这样实现:

(define (length l)
    (if
        (null? l)
        0
        (+ 1 (length (cdr l)))
    )
)

还有一个特别有用的操作是将某个变换应用于表的所有元素，得到所有结果的表。例如我们要将一个list都是数值数据，要将其中的各个元素放大10倍：

(define (times10 l)
    (if (null? l)
        nil
        (cons (* 10 (car l)) (times10 (cdr l)) )
        )
    )

这里的操作是对首元素乘以10，然后对后续表重复调用。

我们可以将此乘以10的处理提取抽象，作为一个参数传入，使其具有通用性：

(define (trans-list f l)
    (if (null? l)
        nil
        (cons (f (car l)) (trans-list f (cdr l)) )
        )
    )

在调用时我们将第一个参数传入一个处理单个元素的函数，第二个参数传入一个列表。

(trans-list (lambda (x) (* 10 x)) one-through-four)

因为这种模式非常具有一般性，所以此过程是一种基本操作map。其调用方法与我们的trans-list一样，只需要将上述语句的trans-list改为map即可。例如：

(map (lambda (x) (* 10 x)) one-through-four)
(map abs (list -10 2 -89.61 43 -1.1))
(map (lambda (x) (* x x)) (list 1 2 3 4))

3.2. 层次性结构¶

将表作为序列的表示，可以自然地推广到那些元素本身也是序列的序列，例如对象( (1 2) 3 4)是由：

(cons (list 1 2) (list 3 4))

构造而来。这是一个包含三个项的表，其中第一项的本身又是表(1 2)。

这种元素本身也是序列的序列，就是“树”形数据结构，序列里的元素就是树的分支，那些本身是序列的元素就是树的子树。例如前述( (1 2) 3 4)可以视为一个三叉树，根结点的第一个子结点是一棵二叉树，这个二叉树只有结点1和2，根结点的第2和第3个结点分别为3和4。

递归是处理树结构很自然的工具。与前述求list的length相对比，编写一个统计树的叶子结点个数的函数 count-leaves。有一个基本操作pair?可以用于判断当前元素是否为序对。

(define (count-leaves t)
    (cond ((null? t) 0)
        ((not (pair? t)) 1)
        (else (+
                (count-leaves (car t))
                (count-leaves (cdr t))))
    )
)

如果树是空树，那么它的叶子结点为0，如果树不是序对结构，说明它只有一个结点，既是根结点也是叶子结点，其它情况下则递归的计算树的首结点和后继结点，并将之相加。

前述的map是一种对序列强有力的抽象。与之类似的，map与递归的结合也是处理树的一种强有力抽象。就像我们编写的将list各元素乘10的方法，我们编写一个time10-tree方法：

(define (time10-tree t)
    (cond ((null? t) nil)
        ((not (pair? t)) (* 10 t))
        (else (cons
            (time10-tree (car t))
            (time10-tree (cdr t))
            )
            )
    )
)

这与叶子结点数量的函数相似：空树则返回空，叶子结点则修改叶子结点的值，否则递归的做子树。

还有一种使用map的递归方法：对树的每一个元素（即根结点的所有子结点，树的第2层），如果这个元素是树，就继续递归，如果是叶子就将之执行运算:

(define (time10-tree t)
    (map (lambda (sub-tree)
        (if (pair? sub-tree)
            (time10-tree sub-tree)
            (* sub-tree 10)))
    t )
)

3.3. 序列作为一种约定的界面¶

首先给出两个函数，一是计算树中的所有奇数结点的平方之和

(define (odd-square-sum t)
    (cond  ((null? t) 0)
        ((not (pair? t))
            (if (odd? t) (* t t) 0))
        (else (+ (odd-square-sum (car t))
            (odd-square-sum (cdr t))))
    )
)

二是构造Fibonacci数为偶数的列表：

(define (even-fib-sum 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)
)

虽然这两程序在结构上差异比较大，但对于抽象描述却能揭示出它们之间极大的相似性。第一个程序：

枚举一棵树的叶子结点
过滤这些结点，选取其中的奇数
对于每个选中的数求平方
用+累加起来，从0开始

第二个程序：

枚举从0到n的整数
对每个整数，计算相应fibonacci数
过滤它们，选出相应的偶数
用cons累积得到的结果，从空表开始

这种过程，可以很自然地用一些级联的处理步骤的信号方式描述，即首先是一个枚举器，然后信号流过一个过滤器，然后经过一个实现映射的转换器，最后用一个累积器进行结果的组合。

如果将上述两个过程抽像成这样四个信号处理结点，我们将关注从前一个步骤流向下一步骤的信号。用一些表表示这个信号，就利用表可以实现每一个步骤的处理。

首先，可能映射的转换最容易实现，因为前述已经有map函数的实现，就可以对应映射的转换器。

过滤操作就是选出其中满足某个谓词的元素，可以按照定义函数filter，符合条件的cons到序列中：

(define (filter condition seq)
    (cond ((null? seq) nil)
        (else (if (condition (car seq))
                (cons (car seq) (filter condition (cdr seq)))
                (filter condition (cdr seq))))
    )
)

然后是累积的处理。累积的操作根据待处理的数据，可能是加，可能是乘，可能是cons构造序列，来分别进行。同时序列初始值也需要指定，应该与待处理的数据相符合，例如乘法应该从数字1开始，加则从数字0开始，cons则从空表nil开始。

(define (accumulate op init seq)
    (if (null? seq)
        init
        (op (car seq) (accumulate op init (cdr seq)))
        )
)

这样，按照前述的流程重新组合，比如构造偶数Fibonacci数的列表：

(define (enum-integer low high)
    (define (acc i c)
        (if (< i c)
            (cons i (acc (+ i 1) c))
            nil
            ))
    (acc low high)
)

(define (even-fib-sum-v2 n)
    (accumulate cons nil
        (filter even?
            (map fib
                (enum-integer 0 (+ n 1)))))
)

将程序表示为针对序列的操作，这样就可以得到模块化的程序。这样可以得到独立的片断的组合构成的设计。

3.4. 嵌套映射¶

考虑对于自然数 \(n\) ，有 \((i,j)\) 满足 \(1 \le j \le i \le n\) ，使 \(i+j\) 是素数。