LISP - 列表搜索

Lisp - 列表中搜索

Common Lisp 提供了一套全面的函数，用于在列表 (lists) 和其他序列 (sequences) 中进行搜索。理解这些工具是有效处理数据的关键。这些函数高度灵活，允许基于值、位置或任意条件进行搜索。

按值搜索：`find` 和 `position`

最基本的搜索操作是在列表中查找特定项。find 返回项本身，而 position 返回其基于零的索引。

语法

(find item sequence &key :test :key)
(position item sequence &key :test :key)

关键参数

item：要搜索的元素。
sequence：要搜索的列表（或其他序列）。
:test：用于比较的函数。默认为 #'eql。对于字符串使用 #'equal，对于不区分大小写的字符串比较使用 #'equalp。
:key：在进行比较之前应用于序列每个元素的函数。

返回值

这两个函数在第一次匹配时都会返回所需的结果（项或其索引）。如果没有找到匹配项，它们返回 NIL。

示例：使用 `find` 和 `position`

(let ((my-list '(10 20 30 40 50))
      (people '((:name "Alice" :age 30) (:name "Bob" :age 25))))

  ;; 简单搜索：查找项 30
  (format t "Find 30: ~a~%" (find 30 my-list))

  ;; 简单搜索：查找 30 的位置
  (format t "Position of 30: ~a~%" (position 30 my-list))

  ;; 搜索不存在的项
  (format t "Position of 99: ~a~%" (position 99 my-list))

  ;; 高级搜索：查找名为 "Bob" 的人结构
  ;; `:key` 在与 "Bob" 比较之前提取 `:name` 值
  ;; `:test` 必须是 `equal` 才能比较字符串
  (let ((bob (find "Bob" people :key #' (lambda (p) (getf p :name)) :test #'equal)))
    (format t "Found person: ~a~%" bob)))

输出

Find 30: 30
Position of 30: 2
Position of 99: NIL
Found person: (:NAME "Bob" :AGE 25)

按条件搜索：`find-if` 和 `position-if`

通常，你不想查找特定的值，而是查找满足特定条件的第一个元素。这就是 find-if 及其相关函数大显身手的地方。它们接受一个谓词 (predicate) 函数作为参数。

语法

(find-if predicate sequence &key :key)
(position-if predicate sequence &key :key)

参数

predicate：接受一个参数并返回 T（真）或 NIL（假）的函数。搜索查找谓词返回 T 的第一个元素。
sequence：要搜索的列表。

返回值

find-if 返回第一个匹配的元素，而 position-if 返回其索引。如果没有元素满足谓词，两者都返回 NIL。

示例：查找第一个奇数

(let ((numbers '(2 4 6 3 7 8)))

  ;; `oddp` 是一个内置谓词，如果一个数字是奇数，它返回 T。
  (format t "First odd number: ~a~%" (find-if #'oddp numbers))

  (format t "Position of first odd number: ~a~%" (position-if #'oddp numbers))

  ;; 你还可以使用 `find-if-not` 来查找*不*满足谓词的第一个元素。
  (format t "First number that is not even: ~a~%" (find-if-not #'evenp numbers)))

输出

First odd number: 3
Position of first odd number: 3
First number that is not even: 3

选择正确的搜索函数

以下是一个快速指南，可帮助你决定使用哪个函数：

要获取项本身：使用 find（用于特定值）或 find-if（用于条件）。
要获取索引：使用 position 或 position-if。
仅检查是否存在：member（或 member-if）通常更具惯用性。它返回从找到的元素开始的列表其余部分，这是一个真值；如果未找到，则返回 NIL。例如：(if (member 30 my-list) ...)。

常见陷阱

字符串忘记 :test 参数：在列表中搜索字符串时，默认的测试 #'eql 通常会失败，因为它检查的是对象标识 (object identity)，而不是结构相等性 (structural equality)。始终使用 (find "my-string" list :test #'equal)。
混淆 find 和 find-if：请记住，find 的第一个参数是项，而 find-if 的第一个参数是函数（一个谓词）。