4

Prolog でリスト操作用の述語をいくつか実装しようとしています。すべてが希望どおりに機能します。例えば

append([],Ys,Ys).
append([X|Xs],Ys,[X|Zs]) :- append(Xs,Ys,Zs).

サンプルクエリ:

?- append([1,2,3],[4,5,6],X).
X = [1,2,3,4,5,6].                   % OK

しかし、「delete」述語に問題があります。実装方法は次のとおりです。

delete(X,[Y|Ys],Zs) :- X == Y, delete(X,Ys,Zs).
delete(X,[_X|Ys],[_Z|Zs]) :- delete(X,Ys,Zs).
delete(_X,[],[]).

悪い結果のサンプル クエリ:

?- delete(4,[1,2,3,4],X).
X = [_G8975, _G8978, _G8981].       % BAD

さらに入力してテストしましたが、常に予想される長さのリストが返されるため、機能します。しかし、なぜ数字ではなく、不可解な _GXXXX しか得られないのでしょうか?

よろしくお願いします！

4

3 に答える 3

4

プログラムにはいくつかの問題があります。しかし、最初に、初心者として：

Prolog の純粋な単調サブセットに固執する

あなたのプログラムで(==)/2は、もはやその純粋なサブセットにないものを使用しています。あなたの場合は、に置き換えてください(=)/2。

常にすべての回答を見てください

Prolog の最上位のループでは、最初の答えだけが表示されます。;またはを押して、さらに要求する必要がありSPACEます。あなたのプログラム(=)/2は（より読みやすい変数で）与えます：

?- delete(4,[1,2,3,4],X).
X = [_A,_B,_C] ;
X = [_A,_B,_C,_D] ;
false.

つまり、最初の回答が予想外であるだけでなく、元の回答と同じ長さのリストを持つ 2 番目の回答があります。一方、最初の回答には予想される解決策が含まれていました。したがって、プログラムはかなり一般的すぎます。

入力サイズを減らす

?- delete(4,[4],L).
L = [] ;
L = [_A] ;
false.

最初の答えは正しいように見えますが、2 番目の答えはまったく予想外です。つまり、この定義は、delete(4,[4],[any])

プログラムを専門化する

falseプログラムをローカライズするには、などの目標を導入してプログラムを専門化し、=可能な限りdelete(4,[4],[any])成功するまで続けます。私は思いつきます：

?- 削除(4,[4],[任意])。

delete(X,[Y|Ys],Zs) :- false , X = Y, delete(X,Ys,Zs) .
delete(X,[_X|Ys],[_Z|Zs]) :- X = 4、_X = 4、_Z = 任意、
   削除 (X、Ys、Zs)。
削除 (_X、[]、[]) :- _X = 4。

ここで、このルールでは、_X =4, _Z = anyはかなり同じであり、X = 4, _X = 4異なるはずであることは明らかです。不等式は で最もよく表されdif/2ます。

delete(_X, [], []).
delete(X, [Y|Ys], [Y|Zs]) :-
   dif(X, Y),
   delete(X, Ys, Zs).
delete(X, [X|Ys], Zs) :-
   delete(X, Ys, Zs).

この定義は現在、さまざまな方法で使用できます。お気に入り

?- delete(X,Xs,[1,2,3]).
Xs = [1, 2, 3],
dif(X, 3),
dif(X, 2),
dif(X, 1) ;
Xs = [1, 2, 3, X],
dif(X, 3),
dif(X, 2),
dif(X, 1) ;
Xs = [1, 2, 3, X, X],
dif(X, 3),
dif(X, 2),
dif(X, 1) ...

無限に多くの答えがあることに注意してください。

于 2014-11-20T12:01:13.833 に答える
4

この回答は、 @falseが回答で提示した論理的に純粋なコードに 触発されています。

tfilter/3 メタ述語と具象化された不等式dif/3を使用して、単純に次のように書きましょう。

?- Vs0 = [1,2,3,4], tfilter(dif( 4 ),Vs0,Vs)。
Vs0 = [1,2,3, 4 ],
Vs = [1,2,3]。% は決定論的に成功します

?- Vs0 = [1,2,3,4,2,3,4], tfilter(dif( 2 ),Vs0,Vs)。
Vs0 = [1, 2 ,3,4, 2 ,3,4],
Vs = [1, 3,4, 3,4]。% は決定論的に成功します

の実装は次のdelete/3ようになります。

delete(E,Vs0,Vs) :-
   tfilter(dif(E),Vs0,Vs).

@false のコードと同様に、この実装はmonotoneであり、述語が多用途になり、根拠のない用語を扱う場合でも論理的に正しい答えを得ることができます。

最後に、非常に一般的なクエリを作成して、すべての回答を見てみましょう。

?- Vs0 = [X,Y,Z], delete( E ,Vs0,Vs).
Vs0 = [ X、Y、Z ]、      E = X、      E = Y、      E = Z、 Vs = [ ] ;
Vs0 = [ X , Y , Z ],      E = X ,      E = Y , dif( E , Z ), Vs = [     Z ] ;
Vs0 = [ X , Y , Z ],      E = X , dif( E , Y ),      E = Z , Vs = [   Y   ] ;
Vs0 = [ X , Y , Z ],      E = X , dif( E , Y ), dif( E , Z ), Vs = [   Y , Z ] ;
Vs0 = [ X , Y , Z ], dif( E , X ),      E = Y ,      E = Z , Vs = [ X     ] ;
Vs0 = [ X , Y , Z ], dif( E , X ),      E = Y , dif( E , Z ), Vs = [ X ,   Z ] ;
Vs0 = [ X , Y , Z ], dif( E , X ), dif( E , Y ),      E = Z , Vs = [ X , Y   ] ;
Vs0 = [ X , Y , Z ], dif( E , X ), dif( E , Y ), dif( E , Z ), Vs = [ X , Y , Z ].
于 2015-05-16T17:25:39.183 に答える
2

不可解な変数名を取り除く 1 つの不可解な方法はnumbervars/3、たとえば、次のように使用することです。

?- length(X, 3).
X = [_G2019, _G2022, _G2025].

?- length(X, 3), numbervars(X, 0, _).
X = [A, B, C].

今あなたにdelete/3。引数の異​​常な順序、句の異常な順序などの他の小さな問題とは別に、1 つの大きな問題があります。2 番目の句では、元のリストの要素があったはずの場所に新しい無名変数を配置します。

delete(X, [Y|Ys], [Y|Zs]) :- delete(X, Ys, Zs).

2番目の節でこれを使用すると、次のように機能します。

?- delete(4, [1,2,3,4], L).
L = [1, 2, 3] .

?- delete(2, [1,2,3,4,2,3,4], L).
L = [1, 3, 4, 3, 4] .

実装にはさらに問題があります。SWI-Prolog から同じ述語の実装を見ることができます: ドキュメントも読んでください!library(lists)

于 2014-10-25T09:32:31.797 に答える