LISP - 从集合获取子集

Lisp - 从列表中创建子集

在 Common Lisp 中，集合式操作通常在标准列表上执行。虽然 Lisp 没有内置的高性能集合数据类型，但它提供了一套丰富的函数，可以将列表视为集合。本章探讨了从这些列表中创建子集的现代和惯用方法。

使用谓词过滤

创建子集最常见的方法是根据条件过滤列表。这通过使用高阶函数来实现，这些函数接受一个谓词（predicate）——一个返回广义布尔值（任何非 NIL 的值都为真）的函数。

示例：过滤奇数

我们可以使用 remove-if-not 只保留谓词为真的元素。#' 语法是 (function ...) 的简写，用于获取与符号关联的函数对象。

;; 定义一个纯函数，从列表中提取奇数。
;; 它不会修改原始列表。
(defun get-odd-numbers (numbers)
  (remove-if-not #'oddp numbers))

;; 为我们的示例定义一个数字列表。
(let ((my-numbers '(1 2 3 4 5 6 7 8)))
  ;; 调用函数并打印生成的子集。
  (print (get-odd-numbers my-numbers))

  ;; 原始列表保持不变。
  (print my-numbers))

输出

执行这段代码会产生以下结果：

(1 3 5 7)
(1 2 3 4 5 6 7 8)

示例：使用匿名 (Lambda) 函数

对于一次性或简单的谓词，使用 defun 定义一个完整的函数是没有必要的。lambda 函数对此非常适用。在这里，我们创建一个小于 5 的数字子集。

;; 使用 let 块保持作用域局部化。
(let ((my-numbers '(1 2 3 4 5 6 7 8)))
  ;; 使用内联 lambda 函数过滤列表。
  (let ((numbers-less-than-5
          (remove-if-not #'(lambda (x) (< x 5)) my-numbers)))
    (print numbers-less-than-5)))

输出

这将输出：

(1 2 3 4)

使用集合操作导出子集

Common Lisp 提供了标准集合论函数，如 intersection 和 set-difference。这些函数是非破坏性的，意味着它们返回一个新列表，而不修改原始输入。

示例：使用 intersection

intersection 返回一个包含同时出现在两个输入列表中的元素的列表。

(let ((list-a '(1 2 3 4))
      (list-b '(3 4 5 6)))
  (let ((common-elements (intersection list-a list-b)))
    (print common-elements)))

输出

公共元素的结果列表是：

(3 4)

示例：使用 set-difference

set-difference 返回一个在第一个列表中但不在第二个列表中的元素列表。

(let ((list-a '(1 2 3 4))
      (unwanted-elements '(2 4)))
  (let ((remaining-elements (set-difference list-a unwanted-elements)))
    (print remaining-elements)))

输出

结果是移除了不需要的元素的 list-a：

(1 3)

使用 subseq 提取子序列

subseq 函数提取任何序列（如列表、向量或字符串）的连续部分。它不是一个集合操作，而是一种常见的基于位置获取“子集”的方法。

示例：获取列表的一个切片

subseq 接受一个序列、一个零索引的起始位置，以及一个可选的、不包含在内的结束位置。

;;           索引： 0  1  2  3  4  5
(let ((my-sequence '(a b c d e f)))
  ;; 获取从索引 1 开始（但不包括索引 4）的元素
  (let ((slice (subseq my-sequence 1 4)))
    (print slice)))

输出

生成的子序列是：

(B C D)

最佳实践： 为了清晰性和可预测性，优先使用非破坏性函数，如 remove-if-not、intersection 和 set-difference。它们的破坏性对应函数（delete-if-not、nintersection、nset-difference）在特定、受控的情况下可以提供性能优势，但可能会通过修改共享数据引入细微的 bug。