prolog - Depender del orden de las reglas

meta-predicate

Question

Para calcular la distancia Hamming entre dos listas de la misma longitud, utilizo foldl(hamm, A, B, 0, R). con esta definición de hamm/4 :

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

El corte en la primera regla evita el retroceso innecesario. La segunda regla, sin embargo, podría haber sido escrita de manera diferente:

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

y hamm2/4 seguirá siendo correcto junto con foldl/5 o para consultas donde tanto A como B están en la tierra.

Entonces, ¿hay una buena razón para preferir el uno sobre el otro? ¿O hay alguna razón para mantener las reglas en ese orden o cambiarlas?

Sé que la consulta

hamm(a, B, 0, 1).

es falso, mientras

hamm2(a, B, 0, 1).

es cierto, pero no puedo decidir cuál tiene más sentido. . .

Answer 1

Ya descubrió las diferencias entre esas definiciones: aparte de la eficiencia, debe decidir sobre sus requisitos. ¿Vas a aceptar variables en tus estructuras de datos? Tal estilo de programación introduce algunas de las características avanzadas de Prolog (estructuras de datos incompletas).

De todos modos, creo que la primera forma es más precisa (de la que no estoy muy seguro, diría firme en el argumento 4 ° )

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

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

mientras que hamm2 es

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

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

Answer 2

El OP implementó dos predicados de estilo acumulador para calcular la distancia de Hamming ( hamm/4 y hamm2/4 ), pero no estaba seguro de cuál tenía más sentido.

Leamos la consulta que desconcertó al OP: "¿Hay una X tal que la distancia (a, X) es 1?". Aquí están las "respuestas" que Prolog da:

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

Desde una perspectiva lógica, ambas implementaciones se comportan mal en la prueba anterior. Hagamos algunas pruebas de constancia :

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

Tenga en cuenta que en consultas anteriores hamm/4 falla correctamente cuando hamm2/4 tuvo éxito incorrectamente, y viceversa. Entonces ambos están medio correctos / medio equivocados, y ninguno es firme.

¿Qué se puede hacer?

En if_/3 de if_/3 y (=)/3 presentados por @false en esta respuesta , implementé el siguiente código puro para el predicado hamm3/4 :

:- use_module(library(clpfd)).

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

Ahora repitamos las consultas anteriores usando 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.

¡Funciona! Finalmente, hamm3/4 consulta más general para ver el conjunto de soluciones completo de hamm3/4 :

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