Prolog 写経記 その 8 delete_n/3

Tech Prolog

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

解説

delete_n(N, List1, List2) は List1 から N 番目の要素を削除した新しいリストを List2 として返す．

まぁ普通．Java でいうと List#remove(int) みたいな．

モード

delete_n(?, ?, ?)

これは全ての引数を入力・出力の両方で使えるようです．

定義

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

delete_n(N, List1, List2) :-
    conc(L1, [_|L2], List1),
    length(L1, M),
    N is M + 1,
    conc(L1, L2, List2),
    !.

未知の述語，length/2 が使われています．
こいつを事前に写経しなきゃいけないと思ったのですが，おいらが使っている SWI-Prolog という処理系では length/2 は組み込み述語として用意されていて，写経するまでもなく使えちゃいました．
念のため length/2 の解説を写経しておくと，

length(List, L) はリスト List の長さを返す．すなわちLを List の要素の数に具体化する．

まぁ普通．Java でいうと List#size() みたいな．


ともあれ (JW)，delete_n/3 に戻ります．
こいつの定義は久しぶりに節が一つだけ，再帰も無しということで，結構簡単な感じ．
し・か・も
発想自体も以前写経した delete/3 とそっくりで， List1 を N 番目の要素とその左右の要素からなるリストの3つに分割します．

  • N 番目の要素より左の要素からなるリスト (L1)．
  • N 番目の要素 (無名の項)．
  • N 番目の要素より右の要素からなるリスト (L2)．

そして

  • L1，無名の項，L2 を連結したものが List1 である．
  • L1, L2 を連結したものが List2 である．

ということになります．
この二つを表しているのが節の本体に出てくる conc/3 ですが，その間にある

    length(L1, M),
    N is M + 1,

が

  • N 番目の要素より左の要素からなるリスト (L1)．

を表しています．
L1 の長さは M で，M に 1 加えたものが N ということです．ちょっと回りくどい感じがしますね．
たぶん，

    M is N -1,
    length(L1, M),

でも同じような気がして，手続き的な頭にはこっちの方が自然な感じ．宣言的に考えた場合に本質的な違いってあるのかなぁ？
ともあれ (JW)，同じ動きになるかあとで確認．


最後にカットが付いているのですが，この意味がよく分かりません．ゴールに達したあとのバックトラックを禁止しているわけですが，この述語の場合 length/2 があるので別の解が得られることはないような気のせいが．
単に無駄な推論をさせないためのカットかなぁ？
ともあれ (JW)，これも削除して同じ動きになるかあとで確認．

注記

あまり写経する必要なさげなんですが，昨日したので今日からは写経します．

List1 と List2 がすでに具体化されている場合，delete_n は List1 から N 番目の要素が削除されたかどうかを調べる．

ね？ 大したことないでしょ？

例

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

2 ?- delete_n(3, [mike, john, ann, steve], L).

L = [mike, john, steve] ;

No
3 ?- delete_n(Which, [peter, tom, mary], [tom, mary]).

Which = 1 ;

No
4 ?- delete_n(Which, [peter, tom, mary], [mary, tom]).

No

まぁ，普通．


そんなわけで (どんなわけで？)，実験開始．
まずは述語の定義を

delete_n(N, List1, List2) :-
    conc(L1, [_|L2], List1),
    M is N - 1,
    length(L1, M),
    conc(L1, L2, List2),
    !.

に変更してお試し．

6 ?- delete_n(3, [mike, john, ann, steve], L).

L = [mike, john, steve] ;

No

ふむ．うまく動いてますね．
続けてお試し．

7 ?- delete_n(Which, [peter, tom, mary], [tom, mary]).
ERROR: Arguments are not sufficiently instantiated
^  Exception: (8) _L152 is _G491-1 ? abort
% Execution Aborted

ぐはぁっ．．．
えっと，何が起きたかというと．．． そうか，そういうことか．
例の最初のように

delete_n(3, [mike, john, ann, steve], L).

と第 1 引数に具体的な値を渡した場合は N が具体化されているので

    M is N - 1,

を計算することができますが，2 番目の例のように

delete_n(Which, [peter, tom, mary], [tom, mary]).

と第 1 引数に具体的な値を渡さなかった場合は N が具体化されていないので

    M is N - 1,

を計算することができないと，そういうわけですか．うーみゅ．．．
どの引数が具体化されているか (いないか)，ちゃんと考えないといけないという事ですね．
っていうか，引数が入力になったり出力になったり自由自在っていうのも考えるのが難しそうな気がする今日この頃です．
っていうか，わざわざ注記に書いてあったとです．．．
それなのに，「大したことない」とか書いてしまったとです．．．
k(1) です．．．
k(1) です．．．


ともあれ (JW)，気を取り直して次行きますよ！！ 次，次！！ (久々エビちゃん風)
そんなわけで (どんなわけで？)，カットを外してみます．

delete_n(N, List1, List2) :-
    conc(L1, [_|L2], List1),
    length(L1, M),
    N is M + 1,
    conc(L1, L2, List2).

そして例をお試し．

11 ?- delete_n(3, [mike, john, ann, steve], L).

L = [mike, john, steve] ;

No
12 ?- delete_n(Which, [peter, tom, mary], [tom, mary]).

Which = 1 ;

No
13 ?- delete_n(Which, [peter, tom, mary], [mary, tom]).

No

ふむ．こちらはうまくいったっぽい．
なので，おそらくこのカットは効率のために付いているだけではないかと．第2引数で与えるリストがとても長い場合などに差が出てくるのかも．


ともあれ (JW)，ここ数日順調に Prolog を分かりつつあったような気がしていたのですが，まだまだ未熟だということを痛感しました．心より恥じる．