Lisp の集合関数

Lispにも、集合を扱える関数がある。リストの要素を集合に見立てて使うのだが、

• adjoin
• union
• intersection
• set-difference

という関数が用意されている。それぞれ、以下のような構文。

• (adjoin ITEM LIST &KEY TEST TEST-NOT KEY)
• (union LIST1 LIST2 &KEY KEY TEST TEST-NOT)
• (intersection LIST1 LIST2 &KEY KEY TEST TEST-NOT)
• (set-difference LIST1 LIST2 &KEY KEY TEST TEST-NOT)

adjoinだけ、引数の片方がLISTでなくITEM。実行すると以下のようになった。

? (adjoin 'a '(a b c))
(A B C)
? (adjoin 0 '(a b c))
(0 A B C)
? (adjoin 'c '(a b c))
(A B C)

ITEMが後続のLISTに含まれない場合のみ、LISTとITEMが合体する。

unionを実行すると以下のようになる。

? (union '(a b c) '(a b c))
(A B C)
? (union '(a b c) '(0 1 2))
(C B A 0 1 2)
? (union '(a b c) '(a b d))
(C A B D)

引数で渡された２つのLISTを合わせるのがこの関数。adjoinと似ているが、LIST同士という点が異なる。また、集合を扱うため、順序については適当。

intersectionは以下の通り。

? (intersection '(a b c) '(a b c))
(C B A)
? (intersection '(a b c) '(0 1 2))
NIL
? (intersection '(0 2 4) '(1 2 4))
(4 2)

引数で渡されたLISTで、共通の要素を返すのがこの関数。順序はunion同様に適当。

set-differenceは以下のようになった。

? (set-difference '(0 1 2) '(0 3 5))
(2 1)
? (set-difference '(0 3 5) '(0 1 2))
(5 3)
? (set-difference '(1 2 3) '(4 5 6))
(3 2 1)
? (set-difference '(0 1 2 3 4) '(0))
(4 3 2 1)
? (set-difference '(0 1 2 3 4 5 6) '(2 3 4))
(6 5 1 0)
? (set-difference '(2 3 4) '(0 1 2 3 4 5 6 7))
NIL

参考にしている情報ソース（ANSI Common Lisp）では、この関数は差集合を返す、
とのことだが・・・動きとしては、最初のLISTから２つめのLISTの内容を取り除いたものが返される、という感じだな。この関数は順不同にリストを扱う、というようにはなっていないみたいだ。