prolog - Deleting all occurrences of an element from a list

Question

Trying to write a procedure that given a value and a list, it deletes all the occurence of that value in the list a wrote:

delMember(X, [], []) :- !.
delMember(X, [X|Xs], Y) :- !, delMember(X, Xs, Y).
delMember(X, [T|Xs], Y) :- !, delMember(X, Xs, Y2), append([T], Y2, Y).

Since the cut this code cannot answer correctly queries like:

delMember(Y, [1,2,3,1,2,3,1,2,3], [1, 2, 1, 2, 1, 2 ]).

If I delete the cuts:

delMember(X, [], []).
delMember(X, [X|Xs], Y) :- delMember(X, Xs, Y).
delMember(X, [T|Xs], Y) :- delMember(X, Xs, Y2), append([T], Y2, Y).

it fail in queries like:

delMember(Y, [1,2,3,1,2,3,1,2,3], [1,2,3,1,2,3,1,2,3]).

(returns true , when the correct answer is false).

How can I make it works in both situations?

Maybe I can check that X is not T in the third line of code, I tried:

delMember(X, [T|Xs], Y) :- not(X = T), delMember(X, Xs, Y2), append([T], Y2, Y).

but it does not work.

Answer 1

Use of the cut

delMember(X, [], []) :- !.
delMember(X, [X|Xs], Y) :- !, delMember(X, Xs, Y).
delMember(X, [T|Xs], Y) :- !, delMember(X, Xs, Y2), append([T], Y2, Y).

Here, you can see that you use !/0 in the last clause of your predicate. It's not necessary. After the last clause, there's no choice left (Prolog remembers choice points from left to right and top to bottom), so a cut (that removes choices), won't do anything useful since you're already at the bottom of your list of choices.

To illustrate, see

a :- b; c.
a :- d.

Here, to prove a, Prolog will first try b, then c, then d (left to right, then top to bottom).

BTW, as a beginner in Prolog, you should go as far as totally avoid the use of the cut. It will just add to your misunderstandings as long as you don't get recursion and the other basics of logic programming.

Prolog recursion

That little note aside, your problem is that you've not properly understood Prolog recursion yet. Please see the first part of this answer that already adresses this concern.

Your third clause is wrong:

delMember(X, [T|Xs], Y) :- delMember(X, Xs, Y2), append([T], Y2, Y).

it should read:

delMember(X, [T|Xs], [T|Y]) :- delMember(X, Xs, Y).

Well, it's not really wrong, it's just really suboptimal. It's not tail-recursive and uses append/3, which would turn your linear predicate into a quadratic one. Plus, as you noticed, since it's not tail-recursive, termination is tougher to obtain in some cases.

Then, to remove the use of the cut !/0, you can consider adding a guard to the last clause:

delMember(_, [], []).
delMember(X, [X|Xs], Y) :-
    delMember(X, Xs, Y).
delMember(X, [T|Xs], [T|Y]) :-
    dif(X, T),
    delMember(X, Xs, Y).

The guard, dif(X, T), specifies that if we're in the third case we cannot be in the second at the same time : X cannot be unified with T here.

Note, there's still one way we can't use the predicate, this is, +, -, +, as cTI tells us. So queries like ?- delMember(1, R, [2, 3]). will loop with my version.

I hope it has been useful.