Prolog 写経記その 4 delete_all/3

今日は delete_all/3 を写経します．

解説

delete_all(X, List1, List2) は List1 から要素 X を全て削除した新しいリストを List2 として返す．

昨日写経した delete/3 は List1 から最初に見つかった X を削除しましたが，delete_all は全ての X を削除するというのが異なる点ですね．
Java でいうと．．．そのままズバリはないような．近いのは List#removeAll(Collection) あたりか．

モード

delete_all(?, ?, ?).

これもまた 3 引数全てを入力としても出力としても使えるようです．

定義

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

delete_all(_, [], []).
delete_all(X, [X|List1], List2) :-
    !,
    delete_all(X, List1, List2).
delete_all(X, [Y|List1], [Y|List2]) :-
    delete_all(X, List1, List2).

ふむ．
最初の節は問題ありませんね．
で，二番目の節ですが．．．

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

バックトラックを禁止するカット (!) が使われています．うーみゅ．．．
カットを除けばこの定義は簡単です．第 1 引数で渡されたリストの先頭が X であれば，その残りから全ての X を取り除いリスト (List2) が結果ということです．
でもでも，なぜここでカットが必要なのかが分かりません．無念だ．
ま，これは後ほど改めて考えることにしませう．
最後の節は難しくはありません．

delete_all(X, [Y|List1], [Y|List2]) :-
    delete_all(X, List1, List2).

第 1 引数で渡されたリストの先頭が X でなければ，その残りから全ての X を取り除いたリストに (List2) の先頭に Y を付け加えたものが結果ということです．
そんなわけで (どんなわけで？)，カットのことは忘れて例に進みましょう．

例

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

2 ?- delete_all(c, [d, a, c, b, c, a], X).

X = [d, a, b, a] ;

No
3 ?- delete_all(X, [3, 2, 7, 2, 3, 1], [2, 7 ,2, 1]).

X = 3 ;

No
4 ?- delete_all(X, [3, 2, 7, 2, 3, 1], [7, 1]).

No

まぁ，どうということもない結果です．

そんなわけで (どんなわけで？)，カットについて探求すべく，実験を行います．
まず，定義の2番目の節からカットを削除してみませう．

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

これで最初の例を試してみると．．．

6 ?- delete_all(c, [d, a, c, b, c, a], X).

X = [d, a, b, a] ;

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

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

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

No

ぐはぁっ，何が起きているわけ！？

1番目の答えは期待したとおりなんですが，カットがなくなったことによりバックトラックが行われて，本来削除すべき c を含んだリストが結果として返ってきてしまいました．
うーみゅ．．．

どうやらこれは，3 番目の節に原因があるようです．

delete_all(X, [Y|List1], [Y|List2]) :-
    delete_all(X, List1, List2).

ここで，第 1 引数を X，第 2 引数で渡されたリストの先頭の要素を Y としているわけですが，必ずしも X != Y に限定しているわけではありません．単に違う名前を付けているだけで，X と Y が異ならなければいけないという条件はどこにもないからです．
上の定義のところで 3 番目の節を

第 1 引数で渡されたリストの先頭が X でなければ，その残りから全ての X を取り除いたリストに (List2) の先頭に Y を付け加えたものが結果ということです．

と解釈しましたが，これは正しくなくて，

第 1 引数で渡されたリストの先頭が X であろうがなかろうが，その残りから全ての X を取り除いたリストに (List2) の先頭に Y を付け加えたものが結果ということです．

となるのでしょう．
そのため，第 1 引数が c で第 2 引数の先頭の要素が c の場合，2 番目の節にマッチした後のバックトラックで 3 番目の節にマッチしてしまっておかしな結果が返ってきたのだと思われます．たぶん．

つまり，2番目の節にカットが付けられているのは，2番目の節と3番目の節が排他的であることを示しているのですね (たぶん)．2 番目の節にマッチしたら，もう 3 番目の節を試す必要はないよ，という．
なので，2 番目の節にカットを付ける代わりに 3 番目の節を

delete_all(X, [Y|List1], [Y|List2]) :-
    not(X = Y),
    delete_all(X, List1, List2).

として，この節は X と Y が異なる場合のみマッチするように明示してみます．
そして最初の例を試してみると．．．

8 ?- delete_all(c, [d, a, c, b, c, a], X).

X = [d, a, b, a] ;

No

ということで，カットを使った定義と同じ結果になりました♪

おそらく，カットを使った方が効率的なんでしょうね．後続の節に対するマッチングを省略できる訳なので．
一方，カットを使わずに条件を明示した場合は 2 番目の節と 3 番目の節の順序を入れ替えてもちゃんと動きますが，カットを使った場合は節の順番を入れ替えるとメロメロになるのでちょっと注意が必要です．

ともあれ，排他的な節を表現する場合のイディオムとして，

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

とすることにより，最初の節の頭部にマッチした場合は，2 番目の節にガード条件を付けなくてもマッチしないということをを覚えておくことにします．
．．．
覚えてられるのか？いやその，そんな場合 (どんな場合？) のための日記だし (苦笑)．