2.2.1 Representing Sequences

One of the useful structures we can build with pairs is a

利用序对可以构造出许多有用的结构，其中之一是

sequence—an ordered collection of data objects. There are, of

course, many ways to represent sequences in terms of pairs. One particularly

straightforward representation is illustrated in Figure 2.4, where the

sequence 1, 2, 3, 4 is represented as a chain of pairs. The car of each

pair is the corresponding item in the chain, and the cdr of the pair is

the next pair in the chain. The cdr of the final pair signals the end

of the sequence by pointing to a distinguished value that is not a pair,

represented in box-and-pointer diagrams as a diagonal line and in programs as

the value of the variable nil. The entire sequence is constructed by

nested cons operations:

序列 (sequence)——一组有序的数据对象。当然，用序对表示序列的方式有很多。图 2.4 展示了一种特别直接的表示方式：序列 1, 2, 3, 4 被表示为一条序对链。每个序对的 car 是该链中对应的元素，cdr 是链中的下一个序对。最后一个序对的 cdr 指向一个特殊的值，该值不是序对，以此标志序列的结束——在方框与指针图中以斜线表示，在程序中则是变量 nil 的值。整个序列由嵌套的 cons 操作构造而成：

Figure 2.4: The sequence 1, 2, 3, 4 represented as a chain of pairs.

图 2.4：序列 1, 2, 3, 4 表示为序对链。

Such a sequence of pairs, formed by nested conses, is called a

这种由嵌套的 cons 构成的序对序列称为

list, and Scheme provides a primitive called list to help in

constructing lists. The above sequence could be produced by (list 1 2 3 4).

In general,

表 (list)。Scheme 提供了一个名为 list 的基本过程，以帮助构造表。上述序列可以用 (list 1 2 3 4) 来生成。一般地，

is equivalent to

等价于

Lisp systems conventionally print lists by printing the sequence of elements,

enclosed in parentheses. Thus, the data object in Figure 2.4 is printed

as (1 2 3 4):

Lisp 系统通常打印表时，会将各元素序列括在括号内输出。因此，图 2.4 中的数据对象被打印为 (1 2 3 4)：

Be careful not to confuse the expression (list 1 2 3 4) with the list

(1 2 3 4), which is the result obtained when the expression is

evaluated. Attempting to evaluate the expression (1 2 3 4) will signal

an error when the interpreter tries to apply the procedure 1 to

arguments 2, 3, 4.

请注意不要混淆表达式 (list 1 2 3 4) 与表 (1 2 3 4)——后者是对该表达式求值所得到的结果。若尝试对表达式 (1 2 3 4) 求值，解释器会试图将过程 1 应用于实参 2、3、4，从而引发错误。

We can think of car as selecting the first item in the list, and of

cdr as selecting the sublist consisting of all but the first item.

Nested applications of car and cdr can be used to extract the

second, third, and subsequent items in the list. The constructor cons

makes a list like the original one, but with an additional item at the

beginning.

我们可以把 car 理解为选取表中的第一个元素，把 cdr 理解为选取由除第一个元素之外所有元素构成的子表。对 car 和 cdr 的嵌套调用可用于提取表中第二、第三及后续各元素。构造函数 cons 能构造出一个与原表相似的新表，只是在开头增加了一个额外的元素。

The value of nil, used to terminate the chain of pairs, can be thought

of as a sequence of no elements, the

empty list. The word

nil 用于终结序对链，可以将其视为不含任何元素的序列，即

nil is a contraction of the Latin word nihil, which means

“nothing.”

Subheading: List operations

空表。nil 是拉丁词 nihil 的缩写，意为「什么都没有」。

小节标题：表操作

The use of pairs to represent sequences of elements as lists is accompanied by

conventional programming techniques for manipulating lists by successively

“cdring down” the lists. For example, the procedure list-ref

takes as arguments a list and a number n and returns the n

用序对将元素序列表示为表，伴随着一套约定俗成的编程技法：通过反复对表做 cdr 操作来逐步遍历表。例如，过程 list-ref 接受一个表和一个数 n 作为实参，返回表中第 n

th item of

the list. It is customary to number the elements of the list beginning with 0.

The method for computing list-ref is the following:

个元素。表中元素的编号习惯上从 0 开始。计算 list-ref 的方法如下：

For n

=

0, list-ref should return the car of the list.

当 n = 0 时，list-ref 应返回表的 car。

Otherwise, list-ref should return the (

n

−

1

)-st item of the

cdr of the list.

否则，list-ref 应返回该表的 cdr 中第 (n − 1) 个元素。

Often we cdr down the whole list. To aid in this, Scheme includes a

primitive predicate null?, which tests whether its argument is the empty

list. The procedure length, which returns the number of items in a

list, illustrates this typical pattern of use:

我们经常需要对整个表做 cdr 操作。为此，Scheme 提供了基本谓词 null?，用于测试其实参是否为空表。过程 length 返回表中元素的个数，体现了这种典型的使用模式：

The length procedure implements a simple recursive plan. The reduction

step is:

The length of any list is 1 plus the length of the cdr of

the list.

This is applied successively until we reach the base case:

The length of the empty list is 0.

We could also compute length in an iterative style:

length 过程实现了一个简单的递归方案。其归约步骤为：

任意表的长度等于 1 加上该表 cdr 的长度。

反复应用这一步骤，直到达到基础情况：

空表的长度为 0。

我们也可以用迭代风格来计算 length：

Another conventional programming technique is to “cons up” an answer

list while cdring down a list, as in the procedure append, which

takes two lists as arguments and combines their elements to make a new list:

另一种约定俗成的编程技法是：在对表做 cdr 操作向下遍历的同时，用 cons 将结果"收拢"成一个答案表。过程 append 正是如此，它接受两个表作为实参，将两者的元素合并成一个新表：

Append is also implemented using a recursive plan. To append

lists list1 and list2, do the following:

append 同样基于递归方案实现。要将表 list1 与 list2 拼接，执行以下步骤：

If list1 is the empty list, then the result is just list2.

若 list1 是空表，则结果就是 list2。

Otherwise, append the cdr of list1 and list2, and

cons the car of list1 onto the result:

否则，将 list1 的 cdr 与 list2 拼接，再将 list1 的 car 用 cons 接在结果的前面：