LISP-セット

CommonLispはセットデータ型を提供しません。ただし、リストに対してセット操作を実行できるようにする機能がいくつか用意されています。

さまざまな基準に基づいて、リスト内のアイテムを追加、削除、および検索できます。和集合、積集合、集合差などのさまざまな集合演算を実行することもできます。

LISPでのセットの実装

リストのようなセットは、通常、consセルの観点から実装されます。ただし、まさにこの理由から、セットが大きくなるほど、セット操作の効率は低下します。

ザ・ adjoin関数を使用すると、セットを構築できます。アイテムとセットを表すリストを受け取り、アイテムと元のセット内のすべてのアイテムを含むセットを表すリストを返します。

ザ・ adjoin関数は最初に指定されたリスト内のアイテムを検索し、見つかった場合は元のリストを返します。それ以外の場合は、新しい短所セルを作成しますcar アイテムとして cdr 元のリストをポイントし、この新しいリストを返します。

ザ・ adjoin 関数もかかります :key そして :testキーワード引数。これらの引数は、アイテムが元のリストに存在するかどうかを確認するために使用されます。

adjoin関数は元のリストを変更しないため、リスト自体に変更を加えるには、adjoinから返された値を元のリストに割り当てるか、マクロを使用する必要があります。 pushnew セットにアイテムを追加します。

例

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

セットユニオン

関数の和集合グループを使用すると、テストに基づいて、これらの関数の引数として提供される2つのリストで集合和集合を実行できます。

これらの関数の構文は次のとおりです-

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

ザ・ union関数は2つのリストを受け取り、いずれかのリストに存在するすべての要素を含む新しいリストを返します。重複がある場合、返されたリストにはメンバーのコピーが1つだけ保持されます。

ザ・ nunion 関数は同じ操作を実行しますが、引数リストを破壊する可能性があります。

例

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 #'mismatch3つのベクトルのリストの引数。これは、リストがconsセルで構成されており、値は明らかに同じように見えますが、cdrセルの一部が一致しないため、LISPインタープリター/コンパイラーと完全に同じではありません。という訳だ; 大きなセットを実装することは、リストを使用することはお勧めしません。ただし、小さなセットでは問題なく動作します。

交差点を設定

関数の交差グループを使用すると、テストに基づいて、これらの関数の引数として提供される2つのリストで交差を実行できます。

これらの関数の構文は次のとおりです-

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

これらの関数は2つのリストを受け取り、両方の引数リストに存在するすべての要素を含む新しいリストを返します。いずれかのリストに重複するエントリがある場合、冗長なエントリが結果に表示される場合と表示されない場合があります。

例

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

交差関数は、交差の破壊バージョンです。つまり、元のリストを破壊する可能性があります。

差を設定する

関数のset-differenceグループを使用すると、テストに基づいて、これらの関数の引数として提供される2つのリストに対してsetdifferenceを実行できます。

これらの関数の構文は次のとおりです-

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

set-difference関数は、2番目のリストに表示されない最初のリストの要素のリストを返します。

例

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