Dựa vào trật tự quy tắc

Question

Để tính khoảng cách Hamming giữa hai danh sách có cùng chiều dài, tôi sử dụng foldl(hamm, A, B, 0, R). với định nghĩa này của hamm/4:

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

Việc cắt giảm trong quy tắc đầu tiên ngăn ngừa sự quay lui không cần thiết. Nguyên tắc thứ hai, tuy nhiên, có thể đã được viết khác:

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

và hamm2/4 vẫn sẽ được chính xác cùng với foldl/5 hoặc các truy vấn mà cả A và B là mặt đất.

Vì vậy, có một lý do thực sự tốt để thích cái khác? Hoặc là có lý do để giữ các quy tắc theo thứ tự đó hoặc chuyển đổi chúng xung quanh?

Tôi biết rằng các truy vấn

hamm(a, B, 0, 1). 

là sai, trong khi

hamm2(a, B, 0, 1). 

là đúng, nhưng tôi không thể khá quyết định cái nào ý nghĩa hơn. . .

Answer 1

Bạn đã phát hiện sự khác biệt giữa các định nghĩa đó: ngoài hiệu quả, bạn nên quyết định các yêu cầu của mình. Bạn sẽ chấp nhận các biến trong cấu trúc dữ liệu của bạn? Kiểu lập trình như vậy giới thiệu một số tính năng Prolog nâng cao (cấu trúc dữ liệu không đầy đủ).

Dù sao, tôi nghĩ rằng hình thức đầu tiên là chính xác hơn (không thực sự chắc chắn về, tôi sẽ nói kiên định trên 4 ° luận)

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

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

khi hamm2 là

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

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

Answer 2

Các OP đã triển khai hai biến vị ngữ kiểu tích lũy để tính toán khoảng cách Hamming (hamm/4 và hamm2/4), nhưng không chắc chắn cái nào đã làm cho cảm giác thêm.

Hãy đọc truy vấn gây nhầm lẫn cho OP: "Có X chẳng hạn khoảng cách đó (a, X) là 1 không?". Dưới đây là những "câu trả lời" Prolog cho:

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

Từ góc độ logic, cả triển khai hoạt động rất tồi thử nghiệm trên. Chúng ta hãy làm một vài xét nghiệm cho kiên định:

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

Lưu ý rằng trong các truy vấn trước hamm/4 đúng không khi hamm2/4 sai đã thành công, và ngược lại. Vì vậy, cả hai là nửa bên phải/nửa sai và không phải một là kiên định.

---

Có thể làm gì?

Dựa trên if_/3 và (=)/3 được trình bày bởi @false trong this answer, tôi thực hiện mã tinh khiết sau đây cho vị hamm3/4:

:- use_module(library(clpfd)). 

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

Bây giờ chúng ta hãy lặp lại trên các truy vấn sử dụng 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. 

Nó hoạt động! Cuối cùng, chúng ta hãy yêu cầu truy vấn tổng quát nhất để xem toàn bộ bộ giải pháp của hamm3/4:

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