auf die Reihenfolge der Regeln Unter Berufung

Question

Um die Hamming-Distanz zwischen zwei Listen der gleichen Länge zu berechnen, verwende ich foldl(hamm, A, B, 0, R). mit dieser Definition von hamm/4:

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

Der Schnitt in der ersten Regel verhindert die unnötigen Rückzieher. Die zweite Regel, jedoch wurde anders geschrieben haben könnte:

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

und hamm2/4 werden noch richtig sein, zusammen mit foldl/5 oder für Abfragen in denen sowohl A als auch B sind geschliffen.

So ist es ein wirklich guter Grund, die einen über den anderen zu bevorzugen? Oder gibt es einen Grund, die Regeln in dieser Reihenfolge zu halten oder umzuschalten?

Ich weiß, dass die Abfrage

hamm(a, B, 0, 1). 

falsch ist, während

hamm2(a, B, 0, 1). 

wahr ist, aber ich kann nicht ganz entscheiden, welche mehr Sinn macht. . .

Answer 1

Sie entdeckte bereits die Unterschiede zwischen diesen Definitionen: Effizienz auseinander, sollten Sie über Ihre Anforderungen entscheiden. Werden Sie Variablen in Ihren Datenstrukturen akzeptieren? Ein solcher Programmierstil führt einige der erweiterten Prolog-Funktionen ein (unvollständige Datenstrukturen).

Wie dem auch sei, ich denke, die erste Form genauer ist (nicht wirklich sicher, ich standhaft auf 4 ° Argument sagen würde)

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

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

während hamm2

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

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

Answer 2

Die OP ist implementiert zwei Akkumulator-Stil Prädikate die Hamming-Distanz (hamm/4 und hamm2/4) zur Berechnung, war aber nicht sicher, welche mehr Sinn.

Lassen Sie uns die Abfrage lesen, die das OP verwirrte: "Gibt es ein X so, dass die Entfernung (a, X) 1 ist?". Hier sind die „Antworten“ Prolog gibt:

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

Aus logischer Sicht beide Implementierungen in über Test schlecht benehmen.

?- 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. 

Beachten Sie, dass in früheren Abfragen hamm/4 zu Recht versagt, wenn hamm2/4 falsch erfolgreich war, und umgekehrt: Lassen Sie uns für Standhaftigkeit ein paar Tests durchführen. Also beide sind halb rechts/halb falsch, und weder noch ist standhaft.

---

Was kann getan werden?

Basierend auf if_/3 und (=)/3 von @False präsentiert in this answer, implementiert ich folgende reinen Code für Prädikat hamm3/4:

:- use_module(library(clpfd)). 

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

nun die obigen Abfragen lassen wiederholen hamm3/4 mit:

?- 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. 

Es klappt! Schließlich fragen wir die allgemeinste Abfrage die gesamte Lösungsmenge von hamm3/4 zu sehen:

?- hamm3(A,B,N0,N). 
A = B, N0 = N ; 
dif(A,B), N0+1 #= N.