LISP - 序列中搜索元素

现代Lisp：序列搜索

Common Lisp 提供了一套统一且功能强大的序列搜索函数。序列（sequence）是一种有序的元素集合，最常见的类型包括列表（lists）、向量（vectors）和字符串（strings）。这些搜索函数是多态的（polymorphic），意味着它们可以无缝地适用于这些不同的数据类型。

基本搜索函数

三个用于搜索序列的基本函数是 find、position 和 count。

find - 定位第一个匹配项

find 函数在一个序列中搜索一个项。如果找到匹配项，它会返回该项本身。如果没有找到匹配项，它会返回 NIL。

(let ((my-vector #(10 20 30 40)))
  (format t "Find 30: ~a~%" (find 30 my-vector))   ; -> 30
  (format t "Find 99: ~a~%" (find 99 my-vector)))  ; -> NIL

position - 查找项的索引

position 函数在一个序列中搜索一个项，并返回第一个匹配项的零基索引。如果没有找到匹配项，它会返回 NIL。

(let ((my-list '(a b c d)))
  (format t "Position of 'c: ~a~%" (position 'c my-list)) ; -> 2
  (format t "Position of 'x: ~a~%" (position 'x my-list)))  ; -> NIL

count - 统计项的出现次数

count 函数返回一个项在序列中出现的总次数。如果未找到该项，则返回 0。

(let ((my-string "hello world"))
  (format t "Count of #\l: ~a~%" (count #\l my-string)) ; -> 3
  (format t "Count of #\z: ~a~%" (count #\z my-string))) ; -> 0

利用关键字参数释放强大功能

这些函数的真正强大之处通过其关键字参数（keyword arguments）得以展现，它们允许进行高度灵活和富有表达力的搜索。

1. :test - 指定相等谓词

默认情况下，搜索函数使用 #'eql 进行比较。:test 参数允许您指定一个不同的函数，例如用于结构相等性（structural equality）的 #'equal，或者用于不区分大小写字符串比较的 #'string-equal。

(let ((str-list '("apple" "Banana" "CHERRY")))
  (format t "Find 'banana' (case-sensitive): ~a~%" (find "banana" str-list :test #'equal))
  (format t "Find 'banana' (case-insensitive): ~a~%" (find "banana" str-list :test #'string-equal)))

2. :key - 基于元素的一部分进行搜索

:key 参数接受一个函数，该函数在进行比较之前会应用于每个元素。这对于在复杂对象序列中进行搜索非常有用。

;; 首先，定义一个简单的人员结构体
(defstruct person name age)

(let ((people (list (make-person :name "Alice" :age 30)
                    (make-person :name "Bob" :age 25)
                    (make-person :name "Charlie" :age 35))))

  ;; 查找名称为 "Bob" 的人对象
  (let ((found-person (find "Bob" people :key #'person-name :test #'equal)))
    (format t "Found person: ~a~%" found-person))

  ;; 统计有多少人年龄大于 28
  (format t "Count of people over 28: ~a~%"
          (count-if (lambda (age) (> age 28)) people :key #'person-age)))

3. :from-end、:start、:end - 搜索子序列

这些参数允许您将搜索限制在序列的特定部分。:from-end 从右侧开始搜索，而 :start 和 :end 则定义一个范围。

(let ((data '(1 2 3 1 2 3)))
  (format t "Position of 2 (from left): ~a~%" (position 2 data))             ; -> 1
  (format t "Position of 2 (from right): ~a~%" (position 2 data :from-end t)) ; -> 4
  (format t "Position of 1 (in range 2-5): ~a~%" (position 1 data :start 2 :end 5))) ; -> 3

使用谓词搜索：find-if、position-if、count-if

为了提供更大的灵活性，Lisp 提供了不同的变体函数，它们搜索满足给定谓词函数（predicate function）的元素，而不是匹配特定项。这些函数以 -if 后缀命名（例如，find-if）。

示例：查找第一个偶数

(let ((numbers '(1 3 5 8 9 10)))
  (format t "First even number: ~a~%" (find-if #'evenp numbers))
  (format t "Position of first even number: ~a~%" (position-if #'evenp numbers))
  (format t "Count of even numbers: ~a~%" (count-if #'evenp numbers)))

输出

First even number: 8
Position of first even number: 3
Count of even numbers: 2

实用建议

• 布尔上下文（Boolean Context）： 请记住，find 和 position 等函数在失败时返回 NIL，在成功时返回非 NIL 值。这意味着您可以直接在 if 和 when 等条件表达式中使用它们的结果。
• 选择正确的工具： 当您需要查找特定项时，使用 find/position/count。当您寻找具有某种属性的项时，使用 -if 变体函数。