LISP - 列表

Lisp 基础：列表和 Cons 单元格

列表是 Lisp 中最具代表性的数据结构，以至于语言的名称就是 List Processing（列表处理）的首字母缩写。尽管现代 Common Lisp 提供了像向量（vectors）和哈希表（hash tables）这样强大的替代品，但深入理解列表对于掌握这门语言至关重要。

基本构成块：cons 单元格

在最低层，列表是由一种称为 cons 单元格的简单结构构建的。一个 cons 单元格是一对指针，分别命名为 car（地址寄存器内容，Contents of the Address Register）和 cdr（递减寄存器内容，Contents of the Decrement Register）——这些是 Lisp 最初在 IBM 704 计算机上实现时沿用的历史名称。

cons 函数用于创建一个新的 cons 单元格。它接受两个参数：

;; 一个 CAR 为 1，CDR 为 2 的 cons 单元格
;; 这被打印为“点对”（dotted pair）
(cons 1 2)   ; => (1 . 2)

;; 访问其组成部分
(car (cons 1 2)) ; => 1
(cdr (cons 1 2)) ; => 2

一个**正确列表（proper list）**是由 cons 单元格通过它们的 cdr 链接起来的链条，其中最后一个 cdr 是特殊的空列表值 nil。

;; 一个元素列表：(1)
(cons 1 nil)

;; 一个包含三个元素的列表：(1 2 3)
;; 其内部结构如下：
(cons 1 (cons 2 (cons 3 nil)))

;; 图示：
;;  [o|/]-- -> [o|/]-- -> [o|/]--> NIL
;;   |          |
;;   |          |
;;   v          v
;;   1          2

使用 list 创建列表

尽管你可以通过嵌套 cons 调用来构建列表，但这很麻烦。list 函数是方便地从多个元素创建列表的方式。

(list 1 2 3)         ; => (1 2 3)
(list 'a 'b 'c)      ; => (A B C)
(list 1 "hello" t)   ; => (1 "hello" T)

;; 列表可以嵌套
(list 'a (list 1 2) 'c) ; => (A (1 2) C)

常用列表操作函数

Common Lisp 提供了一个丰富的列表操作函数库。以下是一些最主要的函数：

函数	描述
car 或 first	返回列表的第一个元素。
cdr 或 rest	返回除第一个元素外所有元素的列表。
cons	将一个新元素添加到列表的头部。
append	将两个或更多列表合并成一个新列表。
reverse	返回一个元素顺序颠倒的新列表。
length	返回列表中的顶级元素数量。
member	检查元素是否在列表中。
nth	访问指定索引（从零开始）处的元素。

实际示例

(defparameter *my-list* '(a b c))

(first *my-list*)     ; => A
(rest *my-list*)      ; => (B C)

;; 将一个新元素添加到头部
(cons 'x *my-list*)   ; => (X A B C)
;; 注意：*my-list* 未改变！=> (A B C)

(nth 1 *my-list*)     ; => B

(append *my-list* '(d e)) ; => (A B C D E)

高级访问：c...r 和解构

对于嵌套列表，Lisp 提供了方便的快捷方式，例如 cadr（(car (cdr list)) 的缩写）、caddr 等。这些对于简单、固定的结构体非常有用。

(defparameter *nested-list* '(a (b c) d))

;; 获取第二个元素：(B C)
(cadr *nested-list*)  ; 等同于 (second *nested-list*) 或 (nth 1 *nested-list*)

;; 获取第二个元素的第一个元素：B
(caadr *nested-list*) ; 等同于 (first (second *nested-list*))

现代实践：对于复杂结构体，使用这些快捷方式可能会变得难以阅读。现代 Lisp 风格通常更倾向于使用 destructuring-bind 宏，它允许你在一个清晰的表达式中将变量绑定到列表的部分。

;; 使用 destructuring-bind 要清晰得多！
(destructuring-bind (first-item (second-item-a second-item-b) third-item)
    *nested-list*
  (format t "Items are: ~a, ~a, ~a, and ~a~%"
          first-item second-item-a second-item-b third-item))
;; Output: Items are: A, B, C, and D