6

同じ長さの2つのリスト間のハミング距離を計算するために、foldl(hamm, A, B, 0, R).次の定義を使用しますhamm/4。

hamm(A, A, V, V) :- !.
hamm(A, B, V0, V1) :- A \= B, V1 is V0 + 1.

最初のルールのカットは、不要なバックトラックを防ぎます。ただし、2番目のルールは別の方法で記述されている可能性があります。

hamm2(A, A, V, V) :- !.
hamm2(_, _, V0, V1) :- V1 is V0 + 1.

また、AとBの両方がグラウンドされているクエリhamm2/4と一緒に、またはクエリに対しても正しいでしょう。foldl/5

それで、一方を他方よりも好む本当に正当な理由がありますか？または、ルールをこの順序で維持したり、切り替えたりする理由はありますか？

私はクエリが

hamm(a, B, 0, 1).

は偽ですが

hamm2(a, B, 0, 1).

本当ですが、どちらがより理にかなっているのかを完全に判断することはできません。。。

4

2 に答える 2

2

OPは、ハミング距離（hamm/4およびhamm2/4）を計算するために2つのアキュムレータスタイルの述語を実装しましたが、どちらがより理にかなっているのかわかりませんでした。

OPを困惑させたクエリを読んでみましょう：「distance（a、X）が1になるようなXはありますか？」Prologが提供する「答え」は次のとおりです。

?- hamm(a,X,0,1). 
false.                          % wrong: should succeed conditionally
?- hamm2(a,X,0,1).              % wrong: should succeed, but not unconditionally
true.

論理的な観点から、両方の実装は上記のテストで誤動作します。安定性についていくつかのテストを行いましょう：

?- hamm(a,X,0,1),X=a.           % right
false.
?- hamm(a,X,0,1),X=b.           % wrong: should succeed as distance(a,b) is 1
false.

?- hamm2(a,X,0,1),X=a.          % wrong: should fail as distance(a,a) is 0
X = a.
?- hamm2(a,X,0,1),X=b.          % right 
X = b.

以前のクエリでhamm/4は、間違って成功すると正しく失敗しhamm2/4、その逆も同様であることに注意してください。したがって、どちらも半分正しい/半分間違っており、どちらも不動ではありません。

何ができる？

この回答の@falseに基づいてif_/3提示されたものに基づいて、述語用に次の純粋なコードを実装しました。(=)/3hamm3/4

:- use_module(library(clpfd)).

hamm3(A,B,V0,V) :-
   if_(A = B, V0 = V, V #= V0+1).

次に、以下を使用して上記のクエリを繰り返しますhamm3/4。

?- hamm3(a,X,0,1). 
dif(X,a).
?- hamm3(a,X,0,1),X=a.
false.
?- hamm3(a,X,0,1),X=b.
X = b.

できます！最後に、最も一般的なクエリを実行して、次のソリューションセット全体を確認し ましょうhamm3/4。

?- hamm3(A,B,N0,N).
A = B,    N0 = N ;
dif(A,B), N0+1 #= N.
于 2015-04-27T06:24:28.097 に答える
-1

これらの定義の違いはすでにわかっています。効率は別として、要件について決定する必要があります。データ構造で変数を受け入れますか？そのようなプログラミングスタイルは、いくつかの高度なProlog機能（不完全なデータ構造）を導入します。

とにかく、私は最初の形式がより正確だと思います（本当によくわかりません、私は4°の議論に固執すると言います）

?- hamm(a, B, 0, 1).
false.

?- hamm(a, B, 0, 0).
B = a.

hamm2は

?- hamm2(a, B, 0, 1).
true.

?- hamm2(a, B, 0, 0).
B = a.
于 2012-12-20T08:52:03.053 に答える