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))

列印頁面