Warum funktioniert dieses Prolog-Prädikat?

Question

Ich habe den folgenden Code: Beachten Sie, dass, während dieser Code auf Listen funktioniert, diese Listen Sätze darstellen, also sollten [1,1,2,2,3,3] und [1,2,3] gleichwertig sein .

%contains(L1, L2), returns true if L1 contains L2 
contains(_, []). 
contains(L1, [Head|Tail]) :- member(Head, L1), contains(L1, Tail). 
%equals(L1, L2), returns true if L1 is equal to L2 
equals([X|L1],[X|L2]) :- equals(L1, L2). 
equals(L1, L2) :- contains(L1, L2), contains(L2, L1). 

Die Idee ist, dass equals ([1,2,3], [1,2,1,3]) wahr zurückgeben sollte. Auf der Grundlage der obigen Definition ist jedoch Folgendes zu erwarten:

1. equals ([1,2,3], [1,2,1,3]) entspricht der ersten Regel und wird aufgerufen gleich ([2,3], [2,1,3]]).
2. gleich ([2,3], [2,1,3]]) stimmt mit der zweiten Regel überein und enthält enthält ([2,3], [2,1,3]), enthält ([2,1 , 3], [2,3]).
3. enthält ([2,3], [2,1,3]) ausfällt, und gleich kehrt Nr

Und es aber immer noch funktioniert. Und auch andere Versuche, es zu verwirren. Kann mir bitte jemand das erklären?

(Prolog Umsetzung: SWI-Prolog Version 2.7.12)

Answer 1

Prolog verwendet eine Technik namens "Backtracking".

Werfen Sie einen Blick auf den ersten Schritt, Ihr Schritt 1.

Prolog hat zwei Regeln kann es hier verwenden, wenn es die Regel anwendet Sie in Ihrer Erklärung gewählt haben, wird es immer scheitern. Aber wenn es einmal gescheitert ist, wird Prolog zurückgehen und die Alternativregel ausprobieren:

ist gleich ([1,2,3], [1,2,1,3]): - enthält ([1,2,3] , [1,2,1,3]), enthält ([1,2,1,3], [1,2,3])

Durch wiederholtes Zurückverfolgen nach dem Auffinden falscher Antworten findet Prolog schließlich eine Lösung, die ist wahr, und so weiß es die Antwort ist wahr.

Wenn versucht wird, die Regeln anzuwenden, ohne eine richtige Antwort zu finden, muss die Antwort falsch sein.

Dies ist ein sehr grundlegender Teil von Prolog. Ich bin überrascht, dass du so weit gekommen bist, ohne es zu verstehen.

Answer 2

Ihr Code ist sehr seltsam, jedoch kann ich Ihnen die Verwendung von Trace-Prädikat zu Testzwecken empfehlen. Hier ist das Beispiel:

4 ?- trace([equals,contains]). 
%   equals/2: [call, redo, exit, fail] 
%   contains/2: [call, redo, exit, fail] 
true. 

[debug] 5 ?- equals([1,2,3],[1,2,1,3]). 
T Call: (7) equals([1, 2, 3], [1, 2, 1, 3]) 
T Call: (8) equals([2, 3], [2, 1, 3]) 
T Call: (9) equals([3], [1, 3]) 
T Call: (10) contains([3], [1, 3]) 
T Fail: (10) contains([3], [1, 3]) 
T Fail: (9) equals([3], [1, 3]) 
T Redo: (8) equals([2, 3], [2, 1, 3]) 
T Call: (9) contains([2, 3], [2, 1, 3]) 
T Call: (10) contains([2, 3], [1, 3]) 
T Fail: (10) contains([2, 3], [1, 3]) 
T Fail: (9) contains([2, 3], [2, 1, 3]) 
T Fail: (8) equals([2, 3], [2, 1, 3]) 
T Redo: (7) equals([1, 2, 3], [1, 2, 1, 3]) 
T Call: (8) contains([1, 2, 3], [1, 2, 1, 3]) 
T Call: (9) contains([1, 2, 3], [2, 1, 3]) 
T Call: (10) contains([1, 2, 3], [1, 3]) 
T Call: (11) contains([1, 2, 3], [3]) 
T Call: (12) contains([1, 2, 3], []) 
T Exit: (12) contains([1, 2, 3], []) 
T Exit: (11) contains([1, 2, 3], [3]) 
T Exit: (10) contains([1, 2, 3], [1, 3]) 
T Exit: (9) contains([1, 2, 3], [2, 1, 3]) 
T Exit: (8) contains([1, 2, 3], [1, 2, 1, 3]) 
T Call: (8) contains([1, 2, 1, 3], [1, 2, 3]) 
T Call: (9) contains([1, 2, 1, 3], [2, 3]) 
T Call: (10) contains([1, 2, 1, 3], [3]) 
T Call: (11) contains([1, 2, 1, 3], []) 
T Exit: (11) contains([1, 2, 1, 3], []) 
T Exit: (10) contains([1, 2, 1, 3], [3]) 
T Exit: (9) contains([1, 2, 1, 3], [2, 3]) 
T Exit: (8) contains([1, 2, 1, 3], [1, 2, 3]) 
T Exit: (7) equals([1, 2, 3], [1, 2, 1, 3]) 
true