LISP - 访问列表元素

Lisp - 访问列表元素

在 Lisp 中，基本数据结构是列表（List），它由 cons 单元格构建而成。一个 cons 单元格是一个包含两个指针的对：car（值）和 cdr（指向下一个单元格的指针）。一个规范的列表是这些单元格组成的链，以 nil（空列表）结尾。

理解这种结构是掌握列表操作的关键。Lisp 提供了几种强大且惯用的方式来访问列表元素。

car 和 cdr：基本访问器

这些是解构 cons 单元格的原始函数。

• car：返回列表的第一个元素。（可联想为“地址寄存器的内容”，即 Address Register 的 Content）
• cdr：返回列表的其余部分（即，移除了第一个元素的列表）。（可联想为“递减寄存器的内容”，即 Decrement Register 的 Content）

尽管这些名称是 IBM 704 计算机的历史遗留产物，但通常将其视为 first（第一个）和 rest（其余）会很有帮助。

;; main.lisp
(let ((my-list '(A B C D)))
  (print (car my-list))  ; 打印第一个元素
  (print (cdr my-list))  ; 打印列表的其余部分
)

输出

A
(B C D)

复合访问器：cadr、caddr 等

Lisp 提供了方便的简写函数，用于 car 和 cdr 的嵌套调用。这些函数名称由 c 和 r 之间代表 car 的 a 和代表 cdr 的 d 组成。

• (cadr list) 等同于 (car (cdr list))（第二个元素）。
• (caddr list) 等同于 (car (cdr (cdr list)))（第三个元素）。
• (cdar list) 等同于 (cdr (car list))（第一个元素的其余部分，如果它是一个列表）。

;; main.lisp
(let ((my-list '(A B C D)))
  (print (cadr my-list))   ; 第二个元素
  (terpri)
  (print (caddr my-list))  ; 第三个元素
)

(let ((nested-list '((A 1) (B 2))))
  (print (caar nested-list))  ; (car (car '((A 1) (B 2)))) -> A
  (terpri)
  (print (cdar nested-list))  ; (cdr (car '((A 1) (B 2)))) -> (1)
)

输出

B
C
A
(1)

位置访问器：nth 和 elt

当你需要通过零基索引访问元素时，nth 是要使用的函数。请注意，对于列表而言，这可能效率低下，因为它必须从头开始遍历列表（时间复杂度为 O(n)）。

elt 是一个更通用的函数，适用于任何类型的序列，包括列表和向量（数组）。

;; main.lisp
(let ((my-list '(A B C D E)))
  ;; 获取第三个元素（索引为 2）
  (print (nth 2 my-list))

  ;; 如果索引超出范围，nth 返回 NIL
  (print (nth 10 my-list))
)

输出

C
NIL

现代访问方式：destructuring-bind

为了编写更简洁、更可读的代码，destructuring-bind 宏是一种现代且惯用的方式，可以将变量绑定到列表的各个部分。它就像列表结构的模式匹配。

;; main.lisp
(let ((my-list '(A B C D E)))
  (destructuring-bind (first second &rest the-rest) my-list
    (format t "First: ~a~%" first)
    (format t "Second: ~a~%" second)
    (format t "The Rest: ~a~%" the-rest)))

;; 它也适用于嵌套列表
(let ((config '(:host "localhost" :port 8080)))
  (destructuring-bind (&key host port) config
    (format t "Connecting to ~a on port ~a~%" host port)))

输出

First: A
Second: B
The Rest: (C D E)
Connecting to localhost on port 8080

递归访问

递归是 Lisp 中处理列表的一种自然方式。一个典型的递归函数包含一个基本情况（Base Case）（通常通过 null 或 endp 检查空列表）和一个递归步骤（Recursive Step），它处理 car 并对 cdr 进行自身调用。

;; main.lisp

(defun print-list-recursively (lst)
  "使用递归将列表的每个元素打印在新行上。"
  ;; 基本情况：如果列表为空，则不执行任何操作并返回。
  (when lst
    ;; 处理第一个元素
    (print (car lst))
    ;; 递归步骤：对列表的其余部分调用函数
    (print-list-recursively (cdr lst))))

(print-list-recursively '(a b c d e))

输出

A
B
C
D
E

性能提示： 请注意，深度递归可能导致栈溢出。现代 Common Lisp 编译器通常会执行尾调用优化（TCO），这可以将某些递归形式转换为高效的循环，但前提是函数必须处于“尾位置”（即它所做的最后一件事）。