Prolog: Deletion of all appearances of an element in a list

Question

I am trying to create a predicate in Prolog which allows me to delete all occurrences of X in a list L. I have the following code:

my_delete(X, L, R):- [] = L, [] = R
my_delete(X, L, R):- [Y|K] = L, [Y|M] = R, my_delete(X, K, M), (Y \= X)
my_delete(X, L, R):- [X|K] = L, [Y|M] = R, my_delete(X, K, R), (Y \= X)

And now, upon querying this following line, I receive no result, implying that no list R could be constructed so that it followed my requirements.

?:- my_delete(baz, [foo, bar, baz], X)

The construction works fine when the list I want to delete from didn't contain an occurrence of X in the first place, but not if it did. Why is my set of predicates insufficient? What needs to be changed?

Answer 1

There are some rules of thumb I follow when writing prolog. Two of them are:

• Use dif instead of \=. From the reference manual: "To make your programs work correctly also in situations where the arguments are not yet sufficiently instantiated, use dif/2 instead."

• Avoid unnecessary variables and always get rid of the "Singleton variables: [X]" error. It makes the code much more readable.

When I rewrite your code accordingly, your

my_delete(X, L, R):- [] = L, [] = R
my_delete(X, L, R):- [Y|K] = L, [Y|M] = R, my_delete(X, K, M), (Y \= X)
my_delete(X, L, R):- [X|K] = L, [Y|M] = R, my_delete(X, K, R), (Y \= X)

becomes

my_delete(A, [], []).
my_delete(X, [Y|K], [Y|M]):- my_delete(X, K, M), dif(X, Y).
my_delete(X, [X|K], R) :- my_delete(X, K, R).

which is not only concise and more readable, but it already seems to work.

As for your particular case, I think it has to do with the quote in the first rule of thumb above. Your X and Y are not sufficiently instantiated, so it is no surprise for me, that your program does not work correctly.

But the "dif vs. \=" issue is probably not a problem in this case. I replaced dif(X, Y) with X \= Y in the code I suggested above, and it still works. (It may be causing a problem in your code though. I don't know if this is the case.)

Just using dif instead of \= is not a solution either. After replacing the \=s with dif in your code, it still does not work correctly. If the element to be removed is at the last position, it does not work. my_delete(baz, [baz], X) fails, for example.

So what is the problem? It seems to me that you've made two mistakes in your last line. You've put an unnecessary (Y \= X). Line 3 was supposed to be the case in which L starts with X. So the inequality check there should probably be an equality check. And secondly, you probably shouldn't have splitted R into [Y|M].

You can try the code here: https://swish.swi-prolog.org/p/myClMmML.pl

Swish has a great debugger as well. Check out its help.