Prolog 写経記 その 7 delete_duplicates/2

Tech Prolog

今日は本来の順番に戻って delete_duplicates/2 を写経します．

解説

delete_duplicates(List1, List2) はリスト List2 から重複する要素を削除した新しいリストを List2 として返す．

Java でいうと．．． うーみゅ，あえていうなら

    public List deleteDuplicates(List list) {
        return new ArrayList(new LinkedHashSet(list));
    }

みたいな感じかなぁ．
JGL (懐かしー) だと Filtering#unique() あたり？
っていうか，ObjectSpace 社は Recursion Software 社に名前が変わってたんだ．．． 知らなかったよ．
っていうか Java5 対応の JGL 5.0 なんて出てるんだぁ．そのうち遊んでみるべし．

モード

delete_duplicates(+, -).

こいつの使い方は第1引数に具体的なリストを与えないといけないようです．
でも，なんで第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).

最初の節はいつものことだからいいとして，2番目の節と3番目の節を見ていきます．
まずはそれぞれの頭部に着目すると，

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

ということで，3番目の節では第2引数で返す結果のリストに第1引数で渡されたリストの最初の要素を含めていますが，2番目の節では含めていません．
そして2番目の節の本体を見てみると，

    member(X, List2),

が含まれていて，第2引数で返すリストに第1引数で渡されたリストの最初の要素が含まれていることが条件となっています．なるほど．
これを大雑把にまとめると，

  • 第 1 引数で渡されたリストの car を X とする．
  • 第 1 引数で渡されたリストの cdr を List1 とする．
  • List1 から重複を除いたものを List2 とする．
  • List2 に X が含まれていれば結果は List2 である．
  • List2 に X が含まれていなければ結果は X と List2 の cons である．

ってことかな．
節の頭部から本体へ，そしてまた頭部へという流れが見えるようになってきた気のせいが．いい感じ♪


2 番目の節の本体は最後にバックトラックを禁止するカットが付いています．
このカットの必要性は，この前の delete_all/3 と似たような感じで，3番目の節で member(X, List2) を否定するガードの意味があるのではないかと思います．
大雑把なまとめの最後で「List2 に X が含まれていなければ」と書いていますが，それに相当する条件が 3 番目の節には含まれていないのはこのカットがあるからでしょう．
これは後ほど実験するということで．

注記

実は写経本には「注記」があったりします．これまでにもありましたが，特に写経するまでもなかったのですが，今回はそうもいかないので写経します．

重複要素の検査は，リストの最後の要素から最初の要素へと向かって，後ろ向きに再帰的に行われる．述語 reverse/2 を下記のように用いることで，能率的とは言えないが，重複要素を削除する前向きの方法が得られる．

delete_duplicates_forward(L1, L2) :-
    reverse(L1, R),
    delete_duplicates(R, Y),
    reverse(Y, L2).

うーみゅ，まだ写経していない reverse/2 を使われてしまった．．．
まぁいいや．順番が来たら写経しましょう．
とりあえず，手元では reverse/2 の定義共々写経して先に進みます．

例

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

2 ?- delete_duplicates([c, d, d, b, a, d, b, c], L1).

L1 = [a, d, b, c] ;

No
3 ?- delete_duplicates_forward([c, d, d, b, a, d, b, c], L2).

L2 = [c, d, b, a] ;

No

ほほぉ．
delete_duplicates/2 が返す結果のリストは，元のリストの順序を維持していないのですね．というか，逆順になっているらしい．って，注記にちゃんと書いてあるわけですが．
一方，delete_duplicates_forward/2 だと順序が維持されています．その代わり効率的ではないよ，と．ふむふむ．
リストの処理が後ろからになるって，car/cdr しながら再帰する場合には避けられない感じですよね．で，それが直感的でない場合もあるよ，と．


む？
そうなのか，それでモードが delete_duplicates(-, ?) ではなくて delete_duplicates(-, +) なのかなぁ．
ちょっと試してみるテスト．

4 ?- delete_duplicates([a, b, a], [a, b]).

No
5 ?- delete_duplicates([a, b, a], [b, a]).

Yes

ふむ．
第2引数に具体的なリストを渡してもちゃんと動くけれど，やはり順番に強く依存しますね．しかも，直感的に正しい方が間違っていることになっちゃいます．そのために第 2 引数は出力専用という扱いなのでしょうね．
これって，Set (順序なし) の操作としては問題ないけど，List (順序付き) の操作としてはいかがなものか？
そうか，そのための delete_duplicates_forward/2 か．抜け目ないな．．．


ともあれ (JW)，次の実験．
定義の2番目の節からカットを削除してみます．

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

すると．．．

6 ?- delete_duplicates([c, d, d, b, a, d, b, c], L1).

L1 = [a, d, b, c] ;

L1 = [b, a, d, b, c] ;

L1 = [d, a, d, b, c] ;

L1 = [d, a, d, b, c] ;

L1 = [d, b, a, d, b, c] ;

L1 = [d, b, a, d, b, c] ;

L1 = [d, a, d, b, c] ;

L1 = [d, b, a, d, b, c] ;

L1 = [d, d, a, d, b, c] ;

L1 = [d, d, b, a, d, b, c] ;

L1 = [c, a, d, b, c] ;

L1 = [c, b, a, d, b, c] ;

L1 = [c, d, a, d, b, c] ;

L1 = [c, d, a, d, b, c] ;

L1 = [c, d, b, a, d, b, c] ;

L1 = [c, d, b, a, d, b, c] ;

L1 = [c, d, a, d, b, c] ;

L1 = [c, d, b, a, d, b, c] ;

L1 = [c, d, d, a, d, b, c] ;

L1 = [c, d, d, b, a, d, b, c] ;

No

やはり．なんかぐちゃぐちゃになってしまいました．
そこで，3番目の節で member(X, List2) を否定するようにします．

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

すると．．．

7 ?- delete_duplicates([c, d, d, b, a, d, b, c], L1).

L1 = [a, d, b, c] ;

No

やはり．思い通りの動き．
予想通り，2 番目の節のカットは 3 番目の節でガード条件を付けるのと同等の意味合いだったようです．
そんなわけで (どんなわけで？)，前は

P :- !, Q.
P :- R.

の場合に「最初の節の頭部にマッチした場合は，2 番目の節にガード条件を付けなくてもマッチしない」ということを憶えておくことにしたわけですが，そのバリエーションとして，

P :- Q, !, R.
P :- S.

の場合には「最初の節の頭部および Q にマッチした場合は，2番目の節にガード条件を付けなくてもマッチしない」ということを憶えておくことにしませう．


むふふ，なんとなくカットの使われ方が読めるようになってきました．
まだまだ思い通りに使うことが出来るわけではありませんが，読む方はかなり進歩した気分♪
写経を始めた甲斐があるというものです．これからも続けるべし．
あー，知ってる (知りつつある) 自分にはしゃいでしまった．(^^;