Lisp - 集合

Common Lisp 没有提供集合数据类型。但是，它提供了一些函数，允许对列表执行集合操作。

您可以根据各种条件添加、删除和搜索列表中的项目。您还可以执行各种集合运算，例如：并集、交集和集合差。

在 LISP 中实现集合

集合，像列表一样，通常是根据 cons 单元实现的。但是，正是由于这个原因，集合操作的效率随着集合的增大而降低。

adjoin 函数允许您构建集合。它接收一个项目和一个表示集合的列表，并返回一个表示包含该项目和原始集合中所有项目的集合的列表。

adjoin 函数首先在给定列表中查找该项目，如果找到，则返回原始列表；否则，它创建一个新的 cons 单元，其 car 为该项目，cdr 指向原始列表，并返回此新列表。

adjoin 函数还采用 :key 和 :test 关键字参数。这些参数用于检查项目是否存在于原始列表中。

由于 adjoin 函数不会修改原始列表，因此要更改列表本身，您必须将 adjoin 返回的值赋给原始列表，或者可以使用宏 pushnew 将项目添加到集合中。

示例

创建一个名为 main.lisp 的新源代码文件，并在其中键入以下代码。

main.lisp

; creating myset as an empty list
(defparameter *myset* ())
(adjoin 1 *myset*)
(adjoin 2 *myset*)

; adjoin did not change the original set
; so it remains same
(write *myset*) ; print the set
; terminate printing
(terpri)
; update the set
(setf *myset* (adjoin 1 *myset*))  
; update the set
(setf *myset* (adjoin 2 *myset*))

; now the original set is changed
; print the updated set
(write *myset*)
; terminate printing
(terpri)

;adding an existing value
(pushnew 2 *myset*)

;no duplicate allowed
; print the set
(write *myset*)
; terminate printing
(terpri)

;pushing a new value
(pushnew 3 *myset*)
; print the set
(write *myset*)
; terminate printing
(terpri)

输出

执行代码时，将返回以下结果：

NIL
(2 1)
(2 1)
(3 2 1)

检查成员资格

member 函数组允许您检查元素是否为集合的成员。

以下是这些函数的语法：

member item list &key :test :test-not :key 
member-if predicate list &key :key 
member-if-not predicate list &key :key

这些函数在给定列表中搜索满足测试的给定项目。如果没有找到这样的项目，则函数返回 nil。否则，返回以该元素作为第一个元素的列表的尾部。

搜索仅在顶层进行。

这些函数可以用作谓词。

示例

更新名为 main.lisp 的源代码文件，并在其中键入以下代码。

main.lisp

; print if zara is part of the list
(write (member 'zara '(ayan abdul zara riyan nuha)))
; terminate printing
(terpri)
; print the even numbers
(write (member-if #'evenp '(3 7 2 5/3 'a)))
(terpri)
; print if not the numbers
(write (member-if-not #'numberp '(3 7 2 5/3 'a 'b 'c)))

输出

执行代码时，将返回以下结果：

(ZARA RIYAN NUHA)
(2 5/3 'A)
('A 'B 'C)

集合并集

union 函数组允许您根据测试对作为这些函数参数提供的两个列表执行集合并集。

以下是这些函数的语法：

union list1 list2 &key :test :test-not :key 
nunion list1 list2 &key :test :test-not :key

union 函数接收两个列表，并返回一个新列表，其中包含两个列表中存在的全部元素。如果存在重复项，则在返回的列表中只保留一个副本。

nunion 函数执行相同的操作，但可能会破坏参数列表。

示例

更新名为 main.lisp 的源代码文件，并在其中键入以下代码。

main.lisp

; calculate union and assign to set1 variable
(setq set1 (union '(a b c) '(c d e)))
; calculate union and assign to set2 variable
(setq set2 (union '(#(a b) #(5 6 7) #(f h)) 
   '(#(5 6 7) #(a b) #(g h)) :test-not #'mismatch)
)
; calculate union and assign to set3 variable       
(setq set3 (union '(#(a b) #(5 6 7) #(f h)) 
   '(#(5 6 7) #(a b) #(g h)))
)
; print set1
(write set1)
; terminate printing
(terpri)
; print set2
(write set2)
; terminate printing
(terpri)
; print set3
(write set3)

输出

执行代码时，将返回以下结果：

(A B C D E)
(#(F H) #(5 6 7) #(A B) #(G H))
(#(A B) #(5 6 7) #(F H) #(5 6 7) #(A B) #(G H))

请注意

对于三个向量的列表，如果没有 :test-not #'mismatch 参数，union 函数将无法按预期工作。这是因为列表是由 cons 单元组成的，尽管值对我们来说看起来是一样的，但单元的 cdr 部分并不匹配，因此它们对 LISP 解释器/编译器来说并不完全相同。这就是不建议使用列表实现大型集合的原因。不过，它适用于小型集合。

集合交集

intersection 函数组允许您根据测试对作为这些函数参数提供的两个列表执行交集。

以下是这些函数的语法：

intersection list1 list2 &key :test :test-not :key 
nintersection list1 list2 &key :test :test-not :key

这些函数接收两个列表，并返回一个新列表，其中包含两个参数列表中都存在的全部元素。如果任一列表具有重复项，则冗余项可能出现在结果中，也可能不会出现。

示例

更新名为 main.lisp 的源代码文件，并在其中键入以下代码。

main.lisp

; compute intersection and assign to set1 variable
(setq set1 (intersection '(a b c) '(c d e)))
; compute intersection and assign to set2 variable
(setq set2 (intersection '(#(a b) #(5 6 7) #(f h)) 
   '(#(5 6 7) #(a b) #(g h)) :test-not #'mismatch)
)
; compute intersection and assign to set3 variable       
(setq set3 (intersection '(#(a b) #(5 6 7) #(f h)) 
   '(#(5 6 7) #(a b) #(g h)))
)
; print set1
(write set1)
; terminate printing
(terpri)
; print set2
(write set2)
; terminate printing
(terpri)
; print set3
(write set3)

输出

执行代码时，将返回以下结果：

(C)
(#(A B) #(5 6 7))
NIL

intersection 函数是 intersection 的破坏性版本，即它可能会破坏原始列表。

集合差

set-difference 函数组允许您根据测试对作为这些函数参数提供的两个列表执行集合差。

以下是这些函数的语法：

set-difference list1 list2 &key :test :test-not :key 
nset-difference list1 list2 &key :test :test-not :key

set-difference 函数返回第一个列表中未出现在第二个列表中的元素列表。

示例

更新名为 main.lisp 的源代码文件，并在其中键入以下代码。

main.lisp

; compute difference and assign to set1 variable
(setq set1 (set-difference '(a b c) '(c d e)))
; compute difference and assign to set2 variable
(setq set2 (set-difference '(#(a b) #(5 6 7) #(f h)) 
   '(#(5 6 7) #(a b) #(g h)) :test-not #'mismatch)
)
; compute difference and assign to set3 variable
(setq set3 (set-difference '(#(a b) #(5 6 7) #(f h)) 
   '(#(5 6 7) #(a b) #(g h)))
)
; print set1
(write set1)
; terminate printing
(terpri)
; print set2
(write set2)
; terminate printing
(terpri)
; print set3
(write set3)

输出

执行代码时，将返回以下结果：

(A B)
(#(F H))
(#(A B) #(5 6 7) #(F H))

打印页面