3.1 构造 (Conses)

在 2.4 节我们介绍了 cons , car , 以及 cdr ，基本的 List 操作函数。 cons 真正所做的事情是，把两个对象结合成一个有两部分的对象，称之为 Cons 对象。概念上来说，一个 Cons 是一对指针；第一个是 car ，第二个是 cdr 。

Cons 对象提供了一个方便的表示法，来表示任何类型的对象。一个 Cons 对象里的一对指针，可以指向任何类型的对象，包括 Cons 对象本身。它利用到我们之后可以用 cons 来构造列表的可能性。

我们往往不会把列表想成是成对的，但它们可以这样被定义。任何非空的列表，都可以被视为一对由列表第一个元素及列表其余元素所组成的列表。 Lisp 列表体现了这个概念。我们使用 Cons 的一半来指向列表的第一个元素，然后用另一半指向列表其余的元素(可能是别的 Cons 或 nil )。 Lisp 的惯例是使用 car 代表列表的第一个元素，而用 cdr 代表列表的其余的元素。所以现在 car 是列表的第一个元素的同义词，而 cdr 是列表的其余的元素的同义词。列表不是不同的对象，而是像 Cons 这样的方式连结起来。

当我们想在 nil 上面建立东西时，

  1. > (setf x (cons 'a nil))
  2. (A)

../_images/Figure-3.1.png

图 3.1 一个元素的列表

产生的列表由一个 Cons 所组成，见图 3.1。这种表达 Cons 的方式叫做箱子表示法 (box notation)，因为每一个 Cons 是用一个箱子表示，内含一个 car 和 cdr 的指针。当我们调用 car 与 cdr 时，我们得到指针指向的地方：

  1. > (car x)
  2. A
  3. > (cdr x)
  4. NIL

当我们构造一个多元素的列表时，我们得到一串 Cons (a chain of conses):

  1. > (setf y (list 'a 'b 'c))
  2. (A B C)

产生的结构见图 3.2。现在当我们想得到列表的 cdr 时，它是一个两个元素的列表。

../_images/Figure-3.2.png

图 3.2 三个元素的列表

  1. > (cdr y)
  2. (B C)

在一个有多个元素的列表中， car 指针让你取得元素，而 cdr 让你取得列表内其余的东西。

一个列表可以有任何类型的对象作为元素，包括另一个列表：

  1. > (setf z (list 'a (list 'b 'c) 'd))
  2. (A (B C) D)

当这种情况发生时，它的结构如图 3.3 所示；第二个 Cons 的 car 指针也指向一个列表：

  1. > (car (cdr z))
  2. (B C)

../_images/Figure-3.3.png

图 3.3 嵌套列表

前两个我们构造的列表都有三个元素；只不过 z 列表的第二个元素也刚好是一个列表。像这样的列表称为嵌套列表，而像 y 这样的列表称之为平坦列表 (flatlist)。

如果参数是一个 Cons 对象，函数 consp 返回真。所以我们可以这样定义 listp :

  1. (defun our-listp (x)
  2.   (or (null x) (consp x)))

因为所有不是 Cons 对象的东西，就是一个原子 (atom)，判断式 atom 可以这样定义：

  1. (defun our-atom (x) (not (consp x)))

注意， nil 既是一个原子，也是一个列表。