ド素人が始めるCommon Lisp 10. リストで集合を扱う

前回リストを扱う関数をいくつか学習した。今回はリストを集合と見たときにどのようなことができるのかを見ていく。
前回の記事はこちら。

ド素人が始めるCommon Lisp 9. リスト再び

以前リストについて書きましたがあれは本当にさわりの部分だったようだ。まだまだたくさんリストに関して学ぶことがある。さすがLISP! 今回はリストをデータとして扱っていくうえで有用なその他たくさんの関数等を見ていく。 この記事に出てくる関数一...

projectdeep.net

2021-03-07

この記事に出てくる関数一覧

リストを集合として扱う

リストと集合はもちろん違うものだ。リストは要素が重複することもあるし、要素の順番にも意味がある。集合は要素の重複はないし順番も関係ない。ただCommon Lispにはリストを集合として扱うような関数が用意されている。今日はそれを学ぶ。
まずは以下のように集合set-aとset-bを作っておこう。

(setf set-a '(a b c d))
(setf set-b '(c d e f))

member: ある要素の有無を調べる

memberを使うとリスト(データタイプとしてのリスト、今は集合として扱っている。)にある要素が含まれているか調べることができる。含まれている場合はその要素以降の要素を持つリストが返る。

(member 'd set-a)   ; => (D)
(member 'c set-b)   ; => (C D E F)
(member 'a set-b)   ; => NIL

集合として扱う場合は要素の順番は関係ないのだが、memberに関しては要素の順番によって返り値が異なる。この見つけたら残りの要素をリストにして返すという仕様はどういうときに役に立つのかは今のところわからない。要素が含まれない場合はnilが返る。

intersection: 積集合を得る

intersectionを使うと2つの集合の積集合を得る。

(intersection set-a set-b)  ; => (D C)

union: 和集合を得る

unionを使うと2つの集合の和集合を得る。

(union set-a set-b) ; => (B A C D E F)

set-difference: 差集合を得る

set-differenceを使うと2つの集合の差集合を得る。

(set-difference set-a set-b)    ; => (B A)
(set-difference set-b set-a)    ; => (F E)

subsetp: 部分集合か調べる

subsetpを使うと部分集合かどうか調べられる。1つ目の引数として渡された集合としてのリストが2つ目の引数として渡された集合としてのリストの部分集合かどうかを調べるもの。

(subsetp set-a '(a c))  ; => NIL
(subsetp '(a c) set-a)  ; => T

adjoin: 要素を追加する

adjoinを使うと集合に要素を追加できる。すでにその要素が含まれている場合は何も変わらない。

(adjoin 'e set-a)   ; => (E A B C D)
(adjoin 'e set-b)   ; => (C D E F)

元の集合は変わらない

上記の処理を行ってもset-a、set-bの中身には変化はない。あくまで新しい集合としてのリストを返しているようだ。

set-a   ; => (A B C D)
set-b   ; => (C D E F)

まだ続く

今回は集合としてのリストを学んだ。
次回はテーブルとしてのリストを学んでいく。