构建层次结构

组合序对与列表

此前我们见过如何用 cons 把两个值”组合”成一个序对（pair），例如 (cons 1 2) 返回序对 (1 . 2)。我们也可以用 list 把任意数量的数据组合在一起。例如在解释器中输入 (list 1 2 'bagel 4)，Racket 会打印出列表 (1 2 bagel 4)。注意，我们可以在其中放入任何类型的数据，甚至是其他的序对和列表！

现在我们来构造一个由列表组成的序对：

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

这个序对的第一项是列表 (1 2)，第二项是列表 (3 4)。我们可以用下面的盒状指针图（box-and-pointer diagram）来表示这个结构：

（如果你不熟悉如何绘制和理解盒状指针图，请回头复习第 4 课中的相关章节。）

你也可以用小写 t 树（little-t tree）来表示结构 ((1 2) 3 4)：

在小写 t 树中，序列里的每个元素都是一个节点。在上面的例子中，(1 2) 是 ((1 2) 3 4) 的一个元素，所以它是一个节点。但它同时也是一棵有两个子节点的树——每个元素对应一个子节点。

为什么叫”小写 t 树”？在本课的后面，我们会讨论”大写 T 树（capital-T Tree）“数据类型，它与小写 t 树数据类型完全不同。我们使用这种记号是为了保持一致和清晰。

我们也可以把小写 t 树称为深列表（deep lists）（因为它们是列表中套列表、再套列表……），这种说法歧义更少，但不太能体现列表的树形结构特征。

测试理解

假设我们求值表达式 (list 1 (list 2 (list 3 4)))。在解释器中输入它会返回什么？请自己画出对应的盒状指针结构和对应的小写 t 树。

选项：

• (1 2 3 4)：这个答案缺少嵌套结构！
• (1 (2 (3 4)))：正确！（✅）
• (1 2 (3 4))：包含 2 的列表不是嵌套在最外层列表里面吗？
• (1 . 2 . 3 4)：点太多了！

要点总结

本节讨论了嵌套的 cons 结构，还介绍了小写 t 树。

在继续之前……

请复习 car 和 cdr 的简写记号，它很快就会派上用场！