Prolog 写経記 その 42 list_to_set/2

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

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

今日は list_to_set/2 を写経します．

解説

list_to_set(List, Set) はリスト List をその中の重複する要素を削除することで集合 Set に変換する．

ふむ．Java でいうと HashSet#(Collection) みたいな．

モード

list_to_set(+, -).

ふむ．

定義

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

list_to_set([], []).
list_to_set([X | List], Set) :-
	list_to_set(List, Set),
	element(X, Set), !.
list_to_set([X | List], [X | Set]) :-
	list_to_set(List, Set).

最初の節は例によって停止条件なので無視．
2番目の節では，第 1 引数で渡されたリストを最初の要素 X と残りの要素からなるリスト List に分けて，List を集合にした結果である Set に X が含まれていれば Set が結果ですよ，と．
そして Set に X が含まれていなければ X と Set の cons が結果ですよ，と．
ふーん．なんか非効率的な気がするんですけど．
X が Set に含まれていない場合，List から集合の変換が2回行われちゃいますよ？
先に重複をチェックする方がよくない？？

list_to_set([], []).
list_to_set([X | List], Set) :-
	member(X, List), !,
	list_to_set(List, Set).
list_to_set([X | List], [X | Set]) :-
	list_to_set(List, Set).

って感じ．
後で確認しませう．

注記

list_to_set/2 とリスト処理述語 delete_duplicates/2 を比較してみよ。

らじゃあ．

delete_duplicates([], []).
delete_duplicates([X|List1], List2) :-
	delete_duplicates(List1, List2),
	member(X, List2),
	!.
delete_duplicates([X|List1], [X|List2]) :-
	delete_duplicates(List1, List2).

．．．
同じじゃん．
「比較してみよ」って場合はことごとく同じのような気のせいが．
注意が必要な微妙な違いがあるわけじゃないのね．

例

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

3 ?- list_to_set([x4, x3, x5, x1, x3], Set).

Set = [x4, x5, x1, x3] 

Yes
4 ?- list_to_set([y0, y3, y1, y6], S).

S = [y0, y3, y1, y6] 

Yes

ふむ．
特にどうということもなく．
そんなわけで (どんなわけで？)，先に重複チェックする版でお試し．

6 ?- list_to_set([x4, x3, x5, x1, x3], Set).

Set = [x4, x5, x1, x3] 

Yes
7 ?- list_to_set([y0, y3, y1, y6], S).

S = [y0, y3, y1, y6] 

Yes

うまく動いているような気がするよ？
こっちの方が効率的だと思うんだけどなぁ．なにか見落としてるのかなぁ？
うーみゅ．．．