Notch operator commutativity in Prolog
I am currently studying Prolog and one of the notes I am reading provides an example of how to use the cut statement correctly. Consider the following function to remove all elements of a specific value from a list.
rm(_,[],[]).
rm(A,[A|L],R) :- rm(A,L,R).
rm(A,[B|L],[B|R]) :- rm(A,L,R).
Due to backtracking, this is an incorrect function definition, and the function will return all the sublists of the list resulting from the removal of some elements of a specific value, but not necessarily all of them. The notes I am reading say that the correct way to fix this is to replace the second line with the line
rm(A,[A|L],R) :- !, rm(A,L,R)
But replacing the line with
rm(A,[A|L],R) :- rm(A,L,R), !
wrong. I'm not sure why the second example is the wrong way to fix this feature. In swipl, replacing the second term with these fixes seems to always return the same answer for the test cases I'm looking at. What am I missing here?
source to share
Your example is a perfect example to illustrate why using a slash here is never a good idea.
Use rm(A,[A|L],R) :- !, rm(A,L,R).
only makes sense if both the first and second arguments are sufficiently instantiated. But if they are not sufficiently created, you will get an incomplete answer like:
?- rm(X, [a], R).
X = a, R = []. % incomplete
This clearly misses the answer as it X
only restricts a
. But if X
- something else, we get a different result, namely:
?- X = b, rm(X,[a],R). R = [a].
Using the abbreviation at the end, as in rm(A,[A|L],R) :- rm(A,L,R), !.
, is even worse: first, all our assumptions still have to be met, and then an additional third argument should not be created. Otherwise, we get additional wrong decisions.
?- rm(a,[a],R). R = []. ?- rm(a,[a],[a]). true % incorrect
Just remember what we are asking here:
User: When removed
a
from the list[a]
, what do we get?Prologue: nothing, zero, nada.
User: But can't I just do nothing instead
[a]
? You are welcome!Prologue: Okay, I give up.
This is not how you want to implement an accounting system.
Thus, both uses of incisions are bad. But the second one is clearly worse, because it still has many prerequisites for memorizing and is also ineffective. On the other hand, there are some cases where you can use these predicates. But it's usually hard to remember when it's safe. Thus, such abbreviations are a constant source of error.
Is there any hope of getting rid of all this small print? Fortunately, there is a way if_/3
out library(reif)
for SICStus | SWI . Download and say:
:- use_module(reif).
rm(_,[],[]).
rm(A,[X|Xs], Ys0) :-
if_(A = X, Ys0 = Ys, Ys0 = [X|Ys]),
rm(A, Xs, Ys).
This program is comparatively efficient but does not have any of the aforementioned defects:
?- rm(X, [a], R).
X = a,
R = []
; R = [a],
dif(X, a).
Pay attention to the second answer! He says that for everyone X
other than a
, the list remains the same.
source to share