2.2.3 Sequences as Conventional Interfaces

In working with compound data, we’ve stressed how data abstraction permits us

to design programs without becoming enmeshed in the details of data

representations, and how abstraction preserves for us the flexibility to

experiment with alternative representations. In this section, we introduce

another powerful design principle for working with data structures—the use of

在处理复合数据的过程中，我们着重强调了数据抽象 (data abstraction) 如何使我们能够在设计程序时无需纠缠于数据表示的细节，以及抽象如何为我们保留了尝试其他表示方式的灵活性。在本节中，我们引入另一种处理数据结构的强大设计原则——约定接口 (conventional interfaces) 的使用。

conventional interfaces.

约定接口。

In 1.3 we saw how program abstractions, implemented as

higher-order procedures, can capture common patterns in programs that deal with

numerical data. Our ability to formulate analogous operations for working with

compound data depends crucially on the style in which we manipulate our data

structures. Consider, for example, the following procedure, analogous to the

count-leaves procedure of 2.2.2, which takes a tree as

argument and computes the sum of the squares of the leaves that are odd:

在 1.3 节中，我们看到程序抽象——以高阶过程的形式实现——如何能够捕捉处理数值数据的程序中的公共模式。我们为处理复合数据构造类似操作的能力，在很大程度上取决于操作数据结构的风格。以下面这个过程为例，它类似于 2.2.2 节中的 count-leaves 过程，以一棵树作为参数，计算其中所有奇数叶节点的平方和：

On the surface, this procedure is very different from the following one, which

constructs a list of all the even Fibonacci numbers Fib

(

k

), where

k is less than or equal to a given integer n:

从表面上看，这个过程与下面这个过程非常不同——后者构造出所有满足 k ≤ n 的偶数 Fibonacci 数 Fib(k) 所组成的表：

Despite the fact that these two procedures are structurally very different, a

more abstract description of the two computations reveals a great deal of

similarity. The first program

尽管这两个过程在结构上差异悬殊，对两段计算的更抽象描述却揭示出大量的相似之处。第一个程序

enumerates the leaves of a tree;

枚举一棵树的所有叶节点；

filters them, selecting the odd ones;

对它们进行过滤，选出其中的奇数；

squares each of the selected ones; and

对每个被选中的叶节点求平方；然后

accumulates the results using +, starting with 0.

The second program

用 + 从 0 开始累积结果。第二个程序

enumerates the integers from 0 to n;

枚举从 0 到 n 的所有整数；

computes the Fibonacci number for each integer;

计算每个整数对应的 Fibonacci 数；

filters them, selecting the even ones; and

对它们进行过滤，选出其中的偶数；然后

accumulates the results using cons, starting with the

empty list.

用 cons 从空表开始累积结果。

A signal-processing engineer would find it natural to conceptualize these

processes in terms of signals flowing through a cascade of stages, each of

which implements part of the program plan, as shown in Figure 2.7. In

sum-odd-squares, we begin with an

enumerator, which generates

a “signal” consisting of the leaves of a given tree. This signal is passed

through a

filter, which eliminates all but the odd elements. The

resulting signal is in turn passed through a

map, which is a

“transducer” that applies the square procedure to each element. The

output of the map is then fed to an

accumulator, which combines the

elements using +, starting from an initial 0. The plan for

even-fibs is analogous.

信号处理工程师会自然地将这些计算过程理解为信号流经一系列级联阶段（如图 2.7 所示），每个阶段实现程序计划的一部分。在 sum-odd-squares 中，我们从一个枚举器 (enumerator) 开始，它产生由给定树的所有叶节点构成的"信号"。该信号经过一个过滤器 (filter)，滤去所有非奇数元素。所得信号再经过一个映射 (map)——这是一个将 square 过程应用于每个元素的"换能器 (transducer)"。map 的输出随后送入一个累积器 (accumulator)，它用 + 从初始值 0 开始合并各元素。even-fibs 的计划与此类似。

Figure 2.7: The signal-flow plans for the procedures sum-odd-squares (top) and even-fibs (bottom) reveal the commonality between the two programs.

图 2.7：过程 sum-odd-squares（上）和 even-fibs（下）的信号流计划揭示了两个程序之间的共同性。

Unfortunately, the two procedure definitions above fail to exhibit this

signal-flow structure. For instance, if we examine the sum-odd-squares

procedure, we find that the enumeration is implemented partly by the

null? and pair? tests and partly by the tree-recursive structure

of the procedure. Similarly, the accumulation is found partly in the tests and

partly in the addition used in the recursion. In general, there are no

distinct parts of either procedure that correspond to the elements in the

signal-flow description. Our two procedures decompose the computations in a

different way, spreading the enumeration over the program and mingling it with

the map, the filter, and the accumulation. If we could organize our programs

to make the signal-flow structure manifest in the procedures we write, this

would increase the conceptual clarity of the resulting code.

Subheading: Sequence Operations

遗憾的是，上面两个过程的定义未能体现这种信号流结构。举例来说，如果我们审视 sum-odd-squares 过程，会发现枚举部分由 null? 和 pair? 的判断以及过程的树形递归结构共同实现；类似地，累积部分则散落在判断和递归中使用的加法运算里。总体而言，两个过程中都没有与信号流描述中各要素一一对应的独立部分。这两个过程以另一种方式分解计算，将枚举散布在整个程序中，并与映射、过滤和累积交织在一起。如果我们能够组织程序，使信号流结构在我们编写的过程中清晰呈现，那将提升所得代码的概念清晰度。子标题：序列操作

The key to organizing programs so as to more clearly reflect the signal-flow

structure is to concentrate on the “signals” that flow from one stage in the

process to the next. If we represent these signals as lists, then we can use

list operations to implement the processing at each of the stages. For

instance, we can implement the mapping stages of the signal-flow diagrams using

the map procedure from 2.2.1:

让程序更清晰地反映信号流结构的关键，在于聚焦于在计算过程的各个阶段之间流动的"信号"。如果我们将这些信号表示为表，就可以用表操作来实现各个阶段的处理。例如，我们可以用 2.2.1 节中的 map 过程来实现信号流图中的映射阶段：

Filtering a sequence to select only those elements that satisfy a given

predicate is accomplished by

对序列 (sequence) 进行过滤，仅保留满足给定谓词的元素，可以通过以下方式实现：

For example,

例如，

Accumulations can be implemented by

累积可以通过以下方式实现：

All that remains to implement signal-flow diagrams is to enumerate the sequence

of elements to be processed. For even-fibs, we need to generate the

sequence of integers in a given range, which we can do as follows:

要实现信号流图，剩下的工作就是枚举待处理的元素序列。对于 even-fibs，我们需要生成给定范围内的整数序列，可以如下实现：

To enumerate the leaves of a tree, we can use

枚举一棵树的所有叶节点，我们可以使用：

Now we can reformulate sum-odd-squares and even-fibs as in the

signal-flow diagrams. For sum-odd-squares, we enumerate the sequence of

leaves of the tree, filter this to keep only the odd numbers in the sequence,

square each element, and sum the results:

现在我们可以按照信号流图来重新表述 sum-odd-squares 和 even-fibs。对于 sum-odd-squares，我们枚举树的叶节点序列，过滤以只保留其中的奇数，对每个元素求平方，然后将结果求和：

For even-fibs, we enumerate the integers from 0 to n, generate the

Fibonacci number for each of these integers, filter the resulting sequence to

keep only the even elements, and accumulate the results into a list:

对于 even-fibs，我们枚举从 0 到 n 的整数，为每个整数生成对应的 Fibonacci 数，过滤所得序列以只保留偶数元素，再将结果累积成一个表：

The value of expressing programs as sequence operations is that this helps us

make program designs that are modular, that is, designs that are constructed by

combining relatively independent pieces. We can encourage modular design by

providing a library of standard components together with a conventional

interface for connecting the components in flexible ways.

将程序表述为序列操作的价值在于，这有助于我们设计出模块化的程序——即通过组合相对独立的部件来构造的设计。我们可以通过提供一套标准组件库，并配以一个约定接口用于灵活地连接各组件，来推动模块化设计。

Modular construction is a powerful strategy for controlling complexity in

engineering design. In real signal-processing applications, for example,

designers regularly build systems by cascading elements selected from

standardized families of filters and transducers. Similarly, sequence

operations provide a library of standard program elements that we can mix and

match. For instance, we can reuse pieces from the sum-odd-squares and

even-fibs procedures in a program that constructs a list of the squares

of the first n

+

1 Fibonacci numbers:

模块化构造是工程设计中控制复杂性的强大策略。例如，在实际的信号处理应用中，设计者常常通过级联从标准化过滤器和换能器家族中选取的元素来构建系统。类似地，序列操作提供了一套标准程序元件库，可以自由搭配组合。例如，我们可以将 sum-odd-squares 和 even-fibs 中的部件复用在一个构造前 n + 1 个 Fibonacci 数之平方所组成的表的程序中：

We can rearrange the pieces and use them in computing the product of the squares of the odd

integers in a sequence:

我们也可以重新排列这些部件，用于计算序列中所有奇数的平方之积：

We can also formulate conventional data-processing applications in terms of

sequence operations. Suppose we have a sequence of personnel records and we

want to find the salary of the highest-paid programmer. Assume that we have a

selector salary that returns the salary of a record, and a predicate

programmer? that tests if a record is for a programmer. Then we can

write

我们还可以用序列操作来表述常规的数据处理应用。假设我们有一个人事记录的序列，希望找出薪酬最高的程序员的工资。假定我们有一个选择函数 salary 用于返回一条记录的工资，以及一个谓词 programmer? 用于检验某条记录是否属于程序员。那么我们可以这样写：

These examples give just a hint of the vast range of operations that can be

expressed as sequence operations.

这些例子只是略微展示了可以用序列操作表达的操作的广泛范围。

Sequences, implemented here as lists, serve as a conventional interface that

permits us to combine processing modules. Additionally, when we uniformly

represent structures as sequences, we have localized the data-structure

dependencies in our programs to a small number of sequence operations. By

changing these, we can experiment with alternative representations of

sequences, while leaving the overall design of our programs intact. We will

exploit this capability in 3.5, when we generalize the

sequence-processing paradigm to admit infinite sequences.

以表实现的序列，在此充当了约定接口，使我们得以组合各个处理模块。此外，当我们将数据结构统一表示为序列时，程序中对数据结构的依赖便被局限在少量序列操作上。通过改变这些操作，我们可以在保持程序整体设计不变的前提下，尝试序列的其他表示方式。我们将在 3.5 节中利用这一能力，将序列处理范式推广到无穷序列。