Prolog 写経記 その 12 insert/4

Tech Prolog

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

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

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

今日は insert/4 を写経します．

解説

insert(X, Y, List2, List2) は要素 Y を List1 中の要素 X の後に挿入した新しいリストを List2 として返す．

ふむ．Java だと．．．list.add(list.indexOf(x) + 1, y) みたいな．
なんか，やり方が想像できちゃう今日この頃です．

モード

insert(?, ?, ?, ?)

定義

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

insert(X, Y, List1, List2) :-
	conc(L1, [X|L2], List1),
	conc(L1, [X, Y|L2], List2).

やはり．
このパターンにも見慣れてきたというか，きっとこうなんだろうなということが想像できるようになってきました．
例によって List1 を X よりも左にある要素のリスト L1 と右にある要素のリスト L2 に分けて，

  • L1，X，L2 を連結したものが List1．
  • L1，X，Y，L2 を連結したものが List2．

ってことですね．

注記

insert/4 は与えられたリスト中の要素 X の後ろに挿入された要素 Y を得たり，与えられたリスト中で後ろに要素 Y が挿入された要素 X を得たり，さらには隣接する2つの要素 X と Y の組み合わせを得るためにも用いられる．これらの場合，最後の例に示すように，3 番目の引数は少なくとも部分的に具体化されていなければならない．そうでなければ，複数の回答を探すことになり，無限ループに陥る危険性が生じる．この問題を避けるには述語 neighbour/3 を用いるとよい．

また出たな，部分的に具体化．最後の例を見ればいいわけね．
neighbour/3 は．．． それを写経する時に．

例

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

3 ?- insert(1, 3, [1, 5], L).

L = [1, 3, 5] ;

No
4 ?- insert(1, X, [1, 5], [1, 3, 5]).

X = 3 ;

No
5 ?- insert(X, Y, [_,  _], [1, 3, 5]).

X = 1
Y = 3 ;

X = 3
Y = 5 ;

No

最後の例の第 3 引数．
そうですか，これも部分的に具体化というのですか．とはいえ，具体化されているのは要素の数だけのような気のせいが．
ちょっと意地悪してみるテスト．

7 ?- insert(X, Y, List1, [1, 3, 5]).

X = 1
Y = 3
List1 = [1, 5] ;

X = 3
Y = 5
List1 = [1, 3] ;
ERROR: Out of global stack

おぉっ！？
これかっ？ これが無限ループに陥るということなのか！？
っていうか，フィジカルトレーニング中に散々お世話になった気のせいが．心より恥じる．
でもでも，なぜ無限ループ？
List2 は与えられているわけだから，2 番目の節

	conc(L1, [X, Y|L2], List2).

が無限ループに陥ることはないはず．

10 ?- conc(L1, [X, Y|L2], [1, 3, 5]).

L1 = 
X = 1
Y = 3
L2 = [5] ;

L1 = [1]
X = 3
Y = 5
L2 =  ;

No

うむ．
ということは，1 番目の節

	conc(L1, [X|L2], List1),

で無限ループかぁ．
っていうか，2番目の節より先にこっちが評価されるわけですが，そうすると何一つ具体化されていないということですか．

13 ?- conc(L1, [X|L2], List1).

L1 = []
X = _G332
L2 = _G333
List1 = [_G332|_G333] ;

L1 = [_G435]
X = _G332
L2 = _G333
List1 = [_G435, _G332|_G333] ;

L1 = [_G435, _G441]
X = _G332
L2 = _G333
List1 = [_G435, _G441, _G332|_G333] ;

L1 = [_G435, _G441, _G447]
X = _G332
L2 = _G333
List1 = [_G435, _G441, _G447, _G332|_G333] ;
・
・
・

これでトラックバックによる再試行が無限に続いちゃうわけですね．
List1 の要素の数を制限すればそれを防ぐことができる，と．

14 ?- conc(L1, [X|L2], [_, _]).

L1 = 
X = _G338
L2 = [_G344] ;

L1 = [_G341]
X = _G338
L2 =  ;

No

ふむ．


まぁ，無限ループに陥ることは分かったのですが，それを注意するのは insert/4 を使う側なんですね．
Prolog の場合，引数と戻り値の区別が曖昧というかどちらとしても使えたりするので，簡単なパラメータチェックすらできなかったりするのだろうか？
大きなアプリケーションを作る場合なんかは落とし穴が多くなりそう．．．
そんな機会はなさそうだからいいけど，何か手があるのかなぁ？
昨日の var/1 なんかをうまく使うのかなぁ．
まぁ，そういう実用的な話は追々ということで．心より恥じる．