Reliance on the order of rules

Question

To calculate the distance between two lists of the same length, I use foldl(hamm, A, B, 0, R). with this definition of hamm/4 :

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

The abbreviation in the first rule prevents unnecessary backtracking. The second rule, however, could be written in different ways:

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

and hamm2/4 will still be correct along with foldl/5 or for queries where both A and B are grounded.

So is there really a good reason to prefer one over the other? Or is there a reason to keep the rules in that order or switch them?

I know the request

 hamm(a, B, 0, 1). 

false and

 hamm2(a, B, 0, 1). 

true, but I can’t decide which one makes more sense.,.

Answer 1

You have already noticed the differences between these definitions: effectiveness separately, you must solve your requirements. Are you going to accept variables in your data structures? This programming style introduces some of the advanced features of Prolog (incomplete data structures).

Anyway, I think the first form is more accurate (not really sure, I would say an argument resistant to 4 °)

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

and hamm2 -

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

Answer 2

OP implemented two drive-style predicates for calculating Hamming distances ( hamm/4 and hamm2/4 ), but was not sure which one made more sense.

Let's read the query puzzled by the OP: "Is there an X such that the distance (a, X) is 1?" Here are the “answers” ​​Prolog gives:

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

From a logical point of view, both implementations do not work correctly in the above test. Let's do some durability tests:

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

Note that in previous hamm/4 requests, failure fails if hamm2/4 and vice versa. Thus, both are half-right / half-wrong, and neither are stable.

---

What can be done?

Based on if_/3 and (=)/3 provided by @false in this answer , I implemented the following clean code for the hamm3/4 predicate:

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

Now repeat the above queries with 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. 

It works! Finally, let me ask you the most general query to see the entire hamm3/4 solution set:

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