序列的表示

在真正进入数据抽象之前，我们先来聊聊将用来存储数据的数据结构：序对（pair）。到目前为止，我们知道的唯一存储信息的方式是使用句子。本节将介绍用序对组合和存储数据的思想。序对功能丰富、易于扩展，因为序对中可以嵌套序对，从而创建出列表（list）——这种数据结构和第 1 课的句子惊人地相似。

序对

一般来说，人本能地倾向于把事物看作多个东西的集合或组合。书是纸上的文字集合，沙拉是菜叶和其他美味食材的组合。现在，让我们换个视角。在 Racket 中，也在大部分计算机科学中，万物都用序对表示。可序对只有两项，怎么存多个东西呢？原来，序对的第二项通常是一个指向另一个序对的指针（pointer）！有了序对指向序对、序对再指向序对的链条，我们想存多少信息就能存多少。它很好地遵循了计算机科学那条规律：一切都能用二进制表示。

创建序对

在 Racket 中，我们用函数 cons 创建序对。它接受任意类型的两个实参，返回一个序对。为了直观，我们可以把序对看成一个分成两半的盒子：

前半叫序对的 car，后半叫 cdr。它们各自有同名的选择函数（selector）。过程 car 和 cdr 都只接受一个序对作为实参，分别返回该序对的第一项和第二项。

看下面的例子，创建数字 3 和 4 的序对：

-> (cons 3 4)
(3 . 4) ;; 注意 3 和 4 之间有个点
-> (car (cons 3 4))
3
-> (cdr (cons 3 4))
4

这个序对画出来是这样的：

这种可视化表示叫盒子指针图（box and pointer diagram），是理解日后更复杂序对的极有用工具。

再看一个例子：

-> (cons 'hello 'world)
(hello . world)
-> (define greeting (cons 'hello 'world))
greeting ;; 把序对存进名为 greeting 的变量
-> (car greeting)
hello
-> (cdr greeting)
world

可以看到，序对可以存任意类型的数据——数字、单词、过程，甚至更多序对！

序对里存序对很常见，因为这样一个序对想存多少信息就能存多少。看看这个嵌套序对例子的盒子指针图：

-> (cons (cons 1 2) 4)
((1 . 2) . 4)

注意这个序对的 car 是另一个序对 (cons 1 2)，而 cdr 是 4。这种情况下，盒子指针图应该这样画：

可想而知，我们有无数种方式存大量数据！

(define z (cons (cons 1 2) 4))

序对的 cdr 也可以指向空列表，写作 '()。例如：

-> (cons 1 '())
(1)

这有什么用？我们什么时候想把”什么都没有”存进序对？别急，看下一个例子。假设我们往解释器里输入：

-> (cons 1 (cons 2 '()))

先自己画画盒子指针图，再猜 Racket 会打印什么，然后对照解释器验证。

实际输出符合你的预期吗？你可能以为它会返回 (1 . (2 . ())) 之类的东西，结果却是 (1 2)。这是因为 Racket 有个聪明的办法来简化嵌套序对！由于 (cons a (cons b (cons c (cons ...)))) 这种格式太常用，Racket 每次看到”点后面跟左括号”时，都会这样简化：

(1 . (2 . ()))
(1 2)

下面有几道练习题。对每个表达式，先画对应的盒子指针图，再写出 Racket 解释器会打印什么：

(cons 4 5)
(cons (cons 2 (cons 4 5)) (cons 6 7))
(cons 3 (cons (cons 1 4) (cons 5 '())))
(cons 1 (cons 2 (cons 3 '())))

下列表达式会返回什么？卡住的话，就画个盒子指针图。

(car (cons 4 5))
(car (cdr (car (car (cons (cons (cons 4 5) (cons 6 7)) (cons 1 (cons 2 3))))))
(cdr (cdr (cdr (cons 1 (cons 2 (cons 3 '())))))

一些简写

一长串 car 和 cdr 可能很难看。我们的 Racket 解释器内置了简写，可以一次调用多个 car 和/或 cdr。

(car (cdr a)) 等价于 (cadr a)。

(car (cdr (car (car a)))) 等价于 (cadaar a)。

注意第一个例子里，如果对序列 a 取 cadr，我们先取 a 的 cdr，再对结果取 car。一般来说，你可以从一串 car 和 cdr 中提取 a 和 d，按同样顺序拼在一起，放在一个 c 和一个 r 之间。最长可以写到 cxxxxr（4 个 x），其中 x 是 a 或 d。

列表

反复用这个 cons 模式会相当繁琐。因为它太常见，Racket 有另一个内置过程替我们创建嵌套的 cons：list。list 接受任意数量、任意类型的实参，把它们作为嵌套的 cons（即 list）返回。例如：

-> (cons 5 (cons 6 (cons 7 (cons 8 '()))))
(5 6 7 8)
-> (list 5 6 7 8) ;; 这和上面的表达式完全等价！
(5 6 7 8)

-> (list 'hello 'world 5 #t)
(hello world 5 #t)

我们可以用下面的递归定义来正式定义 list：列表要么是空列表，写作 '()，要么是一个 cdr 为另一个列表的序对。 注意，这意味着对任何列表不断取 cdr，最终一定会到达空列表。

列表的盒子指针图，只要把每个列表改写成嵌套的 cons 就能画出来。例如，(list 1 2 3) 的盒子指针图和 (cons 1 (cons 2 (cons 3 '()))) 的一样：

由此我们学到一条非常重要的关键结论：每个列表都是序对。 反过来就不对了——并非所有序对都是列表。(cons 1 2) 是序对，但不是列表。

Append

现在，我们几乎有了在 Racket 中表示集合和序列所需的全部工具！只差一个简便合并两个列表的方法。例如，有列表 (list 1 2 3) 和 (list 4 5 6)，想把它们合成一个大列表 (list 1 2 3 4 5 6)。Racket 有个过程替我们做这件事：append。给定任意数量的列表，append 返回一个包含所有实参列表全部元素的列表。

上面这个例子调用 append 的盒子指针图如下。

我们从两个列表 (1 2 3) 和 (4 5 6) 开始：

然后，去掉第一个列表末尾的空指针，让它指向第二个列表的开头：

Append 的原理

下面是 append 的底层工作原理。还记得列表的递归定义告诉我们，列表最后一个 cdr 总是指向空列表吗？首先，append 取第一个实参列表，顺着 cdr 指针找到列表的最后一个序对。然后，它把那个最后序对的 cdr 指向的值，替换为 append 的第二个实参列表。这可能听起来像天书，看下面的例子就清楚了：

-> (define list1 (list 1 2 3 4))
list1 ;; list1 的最后一个序对是 (4 . ())
-> (define list2 (list 5 6 7 8))
list2 ;; list2 的最后一个序对是 (8 . ())
-> (define list3 (list 9 10 11 12))
list3
-> (append list1 list2 list3) ;; 我们取 list1 最后一个序对的 cdr，也就是空列表 '()，让它指向 list2。然后取 list2 最后一个序对的 cdr，也是 '()，让它指向 list3。
(1 2 3 4 5 6 7 8 9 10 11 12)

只有最后一个实参之外全是列表，append 才能工作。你能解释为什么最后一个实参不必是列表吗？调用 append 时最后一个实参不是列表，Racket 会返回什么？