LISP - 集合

Lisp - 列表上的集合操作

Common Lisp 将列表视为表示集合的默认数据结构。在此语境下，“集合”本质上就是一个不包含重复元素的列表。Lisp 提供了一组函数，用于对这些列表执行并集、交集和差集等标准集合操作。

重要提示：对于需要在大数据集上执行高性能集合操作的应用，使用哈希表（hash table）是更高效的方法。基于列表的操作其性能特征会随着列表大小线性下降（O(n*m)）。

构建和修改集合

adjoin 函数和 pushnew 宏是向基于列表的集合中添加元素的主要工具。

使用 adjoin 和 pushnew

adjoin 是一个非破坏性函数。它检查一个元素是否已存在于列表中。如果不存在，它会返回一个新列表，其中包含添加到最前面的元素。如果元素已存在，它会返回原始列表。它不会修改原始列表。

pushnew 是一个便捷的宏，它通过仅在元素不存在时才添加元素来修改一个位置（如变量）。它有效地结合了 adjoin 和 setf 的功能。

(let ((my-set '(c b a)))
  (print "--- Using adjoin (non-destructive) ---")
  (print (adjoin 'd my-set))   ; Returns a new list with 'd
  (print (adjoin 'a my-set))   ; Returns the original list
  (print my-set)             ; Original list is unchanged

  (print "--- Using pushnew (destructive) ---")
  (pushnew 'd my-set)          ; Modifies my-set, adds 'd
  (print my-set)
  (pushnew 'a my-set)          ; Does nothing, 'a is already there
  (print my-set))

输出

"--- Using adjoin (non-destructive) ---"
(D C B A)
(C B A)
(C B A)
"--- Using pushnew (destructive) ---"
(D C B A)
(D C B A)

成员资格测试

member 函数检查一个元素是否是列表的成员。一个重要的 Lisp 惯用法是，member 不仅仅返回 T（真值）。如果找到了该元素，它会返回从该元素开始的子列表。这是一种“广义布尔值”，因为除了 NIL 之外的任何值都被认为是真。

(let ((my-set '(a b c d)))
  (print (member 'c my-set))  ; Found, returns the rest of the list
  (print (member 'x my-set))  ; Not found, returns NIL

  ;; Using it as a predicate
  (if (member 'b my-set)
      (print "'b is in the set")
      (print "'b is not in the set")))

输出

(C D)
NIL
"'b is in the set"

使用 :test 和 :key 比较复杂元素

默认情况下，集合函数使用 eql 进行比较，它检查对象标识。这对于符号和数字来说没有问题，但无法比较等效的字符串或结构。使用 :test 关键字参数来提供一个不同的比较函数，例如 #‘equal（用于结构相似的对象）或 #‘equalp（用于不区分大小写的字符串比较）。

;; Define a list of lists
(let ((list-of-lists '((1 2) (3 4))))

  ;; Fails with default test (eql)
  (print (member '(1 2) list-of-lists))
  ; => NIL

  ;; Succeeds with `equal` test
  (print (member '(1 2) list-of-lists :test #'equal))
  ; => ((1 2) (3 4))
)

核心集合操作

Lisp 提供了 union、intersection 和 set-difference 的非破坏性函数。它们的破坏性对应物（nunion、nintersection、nset-difference）是为了性能优化而存在的，但应谨慎使用，因为它们可能会修改输入列表。

示例：union、intersection 和 set-difference

(let ((set-a '(1 2 3 4))
      (set-b '(3 4 5 6)))

  ;; UNION: Elements in either set
  (print (union set-a set-b))
  ; => (1 2 3 4 5 6) or some permutation

  ;; INTERSECTION: Elements in both sets
  (print (intersection set-a set-b))
  ; => (3 4) or (4 3)

  ;; SET-DIFFERENCE: Elements in A but not in B
  (print (set-difference set-a set-b))
  ; => (1 2) or (2 1)

  ;; SET-DIFFERENCE: Elements in B but not in A
  (print (set-difference set-b set-a))
  ; => (5 6) or (6 5)
)

为了确保列表只包含唯一元素，如同一个真正的集合那样，你可以使用 remove-duplicates 函数。

(remove-duplicates '(a b a c b d a) :test #'eql)

输出

(B C D A)