LISP - 访问序列元素

现代Lisp：访问序列元素

在 Common Lisp 中，序列（sequence）是一种表示有序集合的抽象数据类型。最常见的具体序列类型是列表（lists）、向量（vectors）和字符串（strings）。Lisp 提供了一套丰富的函数来访问它们的元素，但根据数据结构选择正确的函数至关重要，以确保代码的正确性和性能。

访问列表元素

Lisp 中的列表是作为链表（linked lists）实现的。因此，对列表头部的访问效率最高。

first (car) 和 rest (cdr)

first 返回第一个元素，而 rest 返回列表的其余部分。尽管传统的名称 car 和 cdr 仍然有效，但现代名称 first 和 rest 更具描述性，通常为了清晰性更受青睐。

(let ((my-list '(a b c)))
  (format t "First element: ~a~%" (first my-list)) ; -> A
  (format t "Rest of list: ~s~%" (rest my-list)))   ; -> (B C)

second、third… tenth

为了方便起见，Lisp 提供了访问列表前十个元素的访问器函数。

(let ((my-list '(a b c d e)))
  (format t "Third element: ~a~%" (third my-list))) ; -> C

nth - 按索引访问（附带警告）

nth 返回特定零基索引处的元素。警告： 因为列表是链表，nth 必须从头开始遍历列表。这是一个 O(n) 操作，对于长列表来说可能非常慢。

;; 获取索引为 2 的元素（第三个元素）
(format t "Element at index 2: ~a~%" (nth 2 '(a b c d e))) ; -> C

访问向量和字符串元素

向量和字符串是类数组结构，提供对元素快速的 O(1) 随机访问。

elt - 通用序列访问器

elt（element 的缩写）是一个多态函数，适用于任何序列类型。它接受一个序列和一个零基索引，并返回该位置的元素。这是通用序列访问的推荐现代方法。

(let ((my-vector #(10 20 30))
      (my-string "Lisp"))
  ;; 访问向量元素
  (format t "Vector element at index 1: ~a~%" (elt my-vector 1)) ; -> 20

  ;; 访问字符串字符
  (format t "String char at index 2: ~a~%" (elt my-string 2)))   ; -> #\s

aref - 数组专用访问器

aref（array reference 的缩写）专用于数组（包括向量和字符串）。在现代 Lisp 实现中，它对向量和字符串的性能通常与 elt 相同。它的主要用途是当您需要明确表示正在处理数组时，或者在处理多维数组时（此时它是必需的访问器）使用。

(let ((my-vector #(10 20 30)))
  (format t "Vector element with aref: ~a~%" (aref my-vector 1))) ; -> 20

选择正确的访问器：总结

数据结构	访问模式	推荐函数	性能
列表	第一个元素	first (或 car)	O(1)
列表	第 N 个元素	nth (谨慎使用)	O(n)
向量	第 N 个元素	elt (或 aref)	O(1)
字符串	第 N 个字符	elt (或 aref)	O(1)

最佳实践和错误处理

• 数据结构选择： nth 和 elt 之间的性能差异突出了 Lisp 中的一个关键设计原则。如果您需要频繁、快速地按索引随机访问，请使用向量，而不是列表。
• 边界检查： 访问序列中越界的索引会抛出错误。在尝试访问元素之前，请务必确保您的索引有效，例如通过检查 (length sequence)。
• 清晰性至关重要： 在现代代码中，优先使用 first、rest、second 等，而不是 car、cdr、cadr，除非您处于 c...r 传统非常强的上下文（例如，在类似编译器的代码深处）。
• 倾向于使用 elt 提高通用性： 在编写应该对任何类型的序列进行操作的函数时，使用 elt 进行元素访问，以使您的代码更通用和可重用。