LISP - 集合


Common Lisp不提供的一組資料型別。然而,它提供的函式數量,它允許一組操作,以可以在列表上執行。

可以新增,刪除和搜尋列表中的專案,根據不同的標準。還可以執行像不同的集合運算:並,交和集合差。

實現LISP集合

集合像列表一樣,一般實現的利弊單元。由於這個原因,集合操作越來越少,高效的獲取大的集合。要明白這一點,一旦我們深入研究這個問題更深一點。

adjoin函式可建立一個集合。這需要一個條目和一個列表表示一組,並返回表示包含該專案,並在原設定的所有專案的集合列表。

adjoin函式首先查詢的條目給定列表中,一旦找到,將返回原來的名單;否則,建立一個新的cons單元,其car作為該目條,cdr指向原來的列表並返回這個新列表。

該毗函式也需要:key 和 :test關鍵字引數。這些引數用於檢查該條目是否存在於原始列表。

因為,adjoin函式不會修改原來的列表,讓列表本身的變化,必須指定由adjoin到原始列表返回的值或者可以使用巨集pushnew將條目新增到集合。

範例

建立一個名為main.lisp一個新的原始碼檔案,並在其中輸入如下程式碼:

; creating myset as an empty list
(defparameter *myset* ())
(adjoin 1 *myset*)
(adjoin 2 *myset*)
; adjoin didn't change the original set
;so it remains same
(write *myset*)
(terpri)
(setf *myset* (adjoin 1 *myset*))
(setf *myset* (adjoin 2 *myset*))
;now the original set is changed
(write *myset*)
(terpri)
;adding an existing value
(pushnew 2 *myset*)
;no duplicate allowed
(write *myset*)
(terpri)
;pushing a new value
(pushnew 3 *myset*)
(write *myset*)
(terpri)

當執行程式碼,它返回以下結果:

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

檢查成員

函式的成員組允許檢查一個元素是否是一個集合成員。

以下是這些函式的語法:

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

這些函式搜尋給定列表中一個給定的項,滿足了測試。它沒有這樣的項被找到,則函式返回nil。否則,將返回列表中的元素作為第一個元素的尾部。

搜尋是只在頂層進行。

這些函式可作為謂詞。

範例

建立一個名為main.lisp一個新的原始碼檔案,並在其中輸入如下程式碼:

(write (member 'zara '(ayan abdul zara riyan nuha)))
(terpri)
(write (member-if #'evenp '(3 7 2 5/3 'a)))
(terpri)
(write (member-if-not #'numberp '(3 7 2 5/3 'a 'b 'c)))

當執行程式碼,它返回以下結果:

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

集合聯合

聯合組功能能夠在作為引數提供給這些功能測試的基礎上,兩個列表進行集聯合。

以下是這些函式的語法:

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

union函式有兩個列表,並返回一個包含所有目前無論是在列表中的元素的新列表。如果有重複,則該成員只有一個副本被儲存在返回的列表。

union函式執行相同的操作,但可能會破壞引數列表。

範例

建立一個名為main.lisp一個新的原始碼檔案,並在其中輸入如下程式碼:

(setq set1 (union '(a b c) '(c d e)))
(setq set2 (union '(#(a b) #(5 6 7) #(f h)) 
       '(#(5 6 7) #(a b) #(g h)) :test-not #'mismatch))
       
(setq set3 (union '(#(a b) #(5 6 7) #(f h)) 
       '(#(5 6 7) #(a b) #(g h))))
(write set1)
(terpri)
(write set2)
(terpri)
(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 #'不匹配的引數:如預期的union函式不會工作。這是因為,該名單是由cons單元元素,雖然值相同的外觀明顯,單元元素cdr部分不匹配,所以他們並不完全一樣,以LISP直譯器/編譯器。這是原因;實現大集全不建議使用的列表。它工作正常的小集合上。

交集

函式的交點組允許作為引數提供給這些函式測試的基礎上,兩個列表進行交點。

以下是這些函式的語法:

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

這些函式需要兩個列表,並返回一個包含所有目前在這兩個引數列表中的元素的新列表。如果任一列表中的重複項,冗餘項可能會或可能不會出現在結果中。

範例

建立一個名為main.lisp一個新的原始碼檔案,並在其中輸入如下程式碼:

(setq set1 (intersection '(a b c) '(c d e)))
(setq set2 (intersection '(#(a b) #(5 6 7) #(f h)) 
       '(#(5 6 7) #(a b) #(g h)) :test-not #'mismatch))
       
(setq set3 (intersection '(#(a b) #(5 6 7) #(f h)) 
       '(#(5 6 7) #(a b) #(g h))))
(write set1)
(terpri)
(write set2)
(terpri)
(write set3)

當執行程式碼,它返回以下結果:

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

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一個新的原始碼檔案,並在其中輸入如下程式碼:

(setq set1 (set-difference '(a b c) '(c d e)))
(setq set2 (set-difference '(#(a b) #(5 6 7) #(f h)) 
       '(#(5 6 7) #(a b) #(g h)) :test-not #'mismatch))
(setq set3 (set-difference '(#(a b) #(5 6 7) #(f h)) 
       '(#(5 6 7) #(a b) #(g h))))
(write set1)
(terpri)
(write set2)
(terpri)
(write set3)

當執行程式碼,它返回以下結果:

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