LISP - 集合差集

Lisp - 集合操作：set-difference

在 Lisp 中，列表可以被视为集合。set-difference 函数计算两个集合之间的差集，返回一个新列表，其中包含第一个列表中存在但未出现在第二个列表中的元素。

语法

(set-difference list-1 list-2 &key :test :test-not :key)

参数与关键字

• list-1：从中获取元素的主列表。
• list-2：要从 list-1 中移除的元素列表。
• :test：用于比较元素的函数。默认为 #'eql，适用于符号和数字，但不适用于字符串或嵌套列表。对于通用比较，请使用 #'equal。
• :key：在比较前应用于每个元素的函数。在基于对象的某个属性进行比较时非常有用。

示例 1：简单的数字和符号集合

对于数字或符号等简单数据，默认的 :test 函数 #'eql 就足够了。

(let ((set-a '(1 2 3 4 5))
      (set-b '(3 4)))
  (let ((result (set-difference set-a set-b)))
    (format t "Result of A - B: ~a~%" result)))

(let ((set-c '(a b c d))
      (set-d '(b d e)))
  (let ((result (set-difference set-c set-d)))
    (format t "Result of C - D: ~a~%" result)))

预期输出

注意：结果中元素的顺序不保证。

Result of A - B: (1 2 5)
Result of C - D: (A C)

示例 2：将 :test 用于字符串和嵌套列表

当处理字符串或嵌套列表等复杂数据时，你必须提供一个合适的 :test 函数，例如 #'string= 或 #'equal。

;; 对于字符串，必须使用字符串比较函数
(let ((fruit-bowl-1 '("apple" "banana" "cherry"))
      (fruit-bowl-2 '("banana" "date")))
  (let ((result (set-difference fruit-bowl-1 fruit-bowl-2 :test #'string=)))
    (format t "String difference: ~a~%" result)))

;; 对于嵌套列表，使用 #'equal
(let ((list-of-lists-1 '((1 2) (3 4) (5 6)))
      (list-of-lists-2 '((3 4) (7 8))))
  (let ((result (set-difference list-of-lists-1 list-of-lists-2 :test #'equal)))
    (format t "List of lists difference: ~a~%" result)))

预期输出

String difference: ("apple" "cherry")
List of lists difference: ((1 2) (5 6))

示例 3：将 :key 用于复杂对象

:key` 参数功能强大。它允许你基于每个元素的特定部分（如 ID 或名称）执行集合差集操作。

;; 为我们的示例定义一个简单结构
(defstruct user id name)

(let ((all-users (list (make-user :id 1 :name "Alice")
                     (make-user :id 2 :name "Bob")
                     (make-user :id 3 :name "Charlie")))
      (banned-users (list (make-user :id 3 :name "Charlie")
                        (make-user :id 4 :name "David"))))

  ;; 我们希望基于 :id 槽位进行差集操作。
  (let ((active-users (set-difference all-users banned-users :key #'user-id)))
    (format t "Active users: ~a~%" active-users)))

预期输出

Active users: (#S(USER :ID 1 :NAME "Alice") #S(USER :ID 2 :NAME "Bob"))

破坏性版本：nset-difference

Lisp 还提供了 nset-difference，这是此函数的破坏性版本。它可能会修改 list-1 的底层列表结构以生成结果，这可以更节省内存。

语法

(nset-difference list-1 list-2 &key :test :test-not :key)

主要考量与警告

• set-difference 是非破坏性的：它总是返回一个新列表，不触及原始列表。这通常更安全。
• nset-difference 是破坏性的：它被允许重用第一个列表的内存。你不应依赖于调用后原始 list-1 仍然有效。仅在不再需要原始列表的性能关键部分使用它。
• 顺序不保证：请记住这些是集合操作。返回列表中元素的顺序未指定，并且可能因 Lisp 实现而异。
• 始终为复杂数据提供 :test：忘记为列表的列表使用 :test #'equal 或为字符串列表使用 :test #'string= 是一个非常常见的错误。