Prolog 写経記 その 40 intersect/2

(ほぼ) 毎日淡々と Prolog を写経します．元ネタはこちら．

Prologユーティリティライブラリ

今度は intersect/2 を写経します．
なんか大したことがないので連チャン．

解説

intersect(Set, Int) は集合の集まりである Sets 中の集合の積 Int (積集合になる) を返す．

ふむ．Java でいうと．．． ないかも．JGL でいうと．．． ないかも．
こういうのって使うのかなぁ？

モード

intersect(+, -).

ふむ．

定義

では，こいつの定義を写経しませう．

intersect([[]], []).
intersect([[X | Rest]], [X | Rest]) :- !.
intersect([Set | Sets], Int) :-
	intersect(Sets, Int),
	intersect(Set, Int, Int).

ふむ．
最初の節は停止条件なのでスルーして，2 番目の節では．．． 何やってんだ？？
うーみゅ．．． ちょっと謎なのでパス．先に最後の節．
第 1 引数で与えられた集合のリストの2番目以降の要素からなる集合 Sets の積集合が結果で，それは第 1 引数で与えられた集合のリストの最初の要素であるところの集合 Set と結果の積集合も結果である．．． ？？？？
だめだ，全然分かんねぇー！！！！
っていうか，これってちゃんと動くの？？

注記

結合性によって，積演算は任意の数の集合に対して適用できる．そして全ての集合に共通する要素の集合が答の集合として返される．

うーん．それは分かるんだけど，上の定義でそうなるとは思えないのですけど？？

例

では使用例を写経しませう．

5 ?- intersect([[b, a, c, d], [c, e, b], [d, a, b, c]], I).

No
6 ?- intersect([[b, a, c, d], [c, e, b], [d, a, b, c], []], Int).

Int = [] 

Yes

をいをい！！
最初の例，写経本だと [b, c] が返ってくることになってるんですけど？？
やっぱりうまく動いてないじゃん．
ちょっと確認．

7 ?- intersect([[a]], Int).

Int = [a] 

Yes
8 ?- intersect([[a], [a]], Int).

Int = [a] 

Yes
9 ?- intersect([[a, b], [b, c]], Int).

No

ふむ．要素が複数あるとダメですね．

しょうがないので修正．どう考えたって最後の節がおかしいので，

intersect([[]], []).
intersect([[X | Rest]], [X | Rest]) :- !.
intersect([Set | Sets], Int) :-
	intersect(Sets, Int1),
	intersect(Set, Int1, Int).

って感じじゃないかなぁ？
これでテスト．

11 ?- intersect([[b, a, c, d], [c, e, b], [d, a, b, c]], I).

I = [b, c] 

Yes
12 ?- intersect(][b, a, c, d], [c, e, b], [d, a, b, c], []], Int).

Int = [] 

Yes
13 ?- intersect([[a, b], [b, c]], Int).

Int = [b] 

Yes

いいじゃん♪

んで，2番目の節を削除して試してみるテスト．

15 ?- intersect([[b, a, c, d], [c, e, b], [d, a, b, c]], I).

No
16 ?- intersect([[b, a, c, d], [c, e, b], [d, a, b, c], []], Int).

Int = [] 

Yes
17 ?- intersect([[a, b], [b, c]], Int).

No

おっと，2 番目の節はしっかり役に立っているのですね．
うーみゅ．

intersect([[]], []).
intersect([[X | Rest]], [X | Rest]) :- !.
intersect([Set | Sets], Int) :-
	intersect(Sets, Int1),
	intersect(Set, Int1, Int).

そうか，集合のリストに要素 (集合) が一つだけになった場合はその集合が結果だということか．
でもでも，こんな回りくどい書き方しなきゃいけないわけ？

intersect([Set], Set) :- !.

素直にこれでもいいんじゃない？

19 ?- intersect([[b, a, c, d], [c, e, b], [d, a, b, c]], I).

I = [b, c] 

Yes
20 ?- intersect([[b, a, c, d], [c, e, b], [d, a, b, c], []], Int).

Int = [] 

Yes
25 ?- intersect([[a, b], [b, c]], Int).

Int = [b] 

Yes

ほらぁ．
結論．

intersect([[]], []).
intersect([Set], Set) :- !.
intersect([Set | Sets], Int) :-
	intersect(Sets, Int1),
	intersect(Set, Int1, Int).

だと思うぞ．

---