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.

Proliferation

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.

Mendicant

Thank you, I have just a question. If I query delMember(Y, [1,2,3,1,2,3], X), I get only one solution (Y=1, X=[2,3,2,3]). Why I don't get also Y=2 and Y=3 ? – Proliferation

That's because we use (\=)/2, that doesn't really fit the job. That results in Prolog only being able to use the second clause to find X. Try using dif(X, T) instead of X \= T – Mendicant

Great catch! dif/2 it's a really weird beast, and this put it to good use. – Hyaluronidase

Yup, still +, -, + loops. Not the best solution! – Mendicant

Answer 2

Lets do a bit of rephrasing: since you want to use the predicate in more than one instantiation pattern " a procedure that given a value and a list, it deletes all the occurrence of that value in the list" does not define how it should behave in the other cases. So, we probably want something like "the predicate is true if the second and third argument are lists L1, L2 and L1 is the same list with L2 if we ignore all occurrences of the first argument"

Now, there are two ways of writing a predicate with multiple possible instantiations; you can use meta-logical predicates such as var/1 and ground/1 and write code for each one (which will probably allow you to write code that's optimised for that specific instantiation) or write code that would define the properties logically (which can be more challenging).

In this case, we could do something like that:

    del(_, [], []).
    del(X, [X|L1], L2):-
        del(X,L1,L2).
    del(X, [H|L1], [H|L2]):-
        X\==H,
        del(X,L1,L2).

which has the following behaviour:

19 ?- del(1, [1,2,3], X).
X = [2, 3] ;
false.
1,2,3,
20 ?- del(1, [1,2,3], [2,3]).
true ;
false.

21 ?- del(X, [1,2,3], [2,3]).
X = 1 ;
false.

22 ?- del(X, [1,2,3], Y).
X = 1,
Y = [2, 3] ;
X = 2,
Y = [1, 3] ;
X = 3,
Y = [1, 2] ;
Y = [1, 2, 3] ;
false.

23 ?- del(X, P, Y).
P = Y, Y = [] ;
P = [X],
Y = [] ;
P = [X, X],
Y = [] ;
P = [X, X, X],
Y = [] ;
P = [X, X, X, X],
Y = [] ;
P = [X, X, X, X, X],
Y = [] ;
P = [X, X, X, X, X, X],
Y = [] .

regarding the last call; prolog returns a list of X that grows cause a depth-first algorithm is used; by using length/2 we can get the results breadth-first (_G means that the variable is not instantiated (it can be anything)):

24 ?- length(P,N), del(X, P, Y).
P = [],
N = 0,
Y = [] ;
P = [X],
N = 1,
Y = [] ;
P = [_G548],
N = 1,
Y = [_G548] ;
P = [X, X],
N = 2,
Y = [] ;
P = [X, _G551],
N = 2,
Y = [_G551] ;
P = [_G548, X],
N = 2,
Y = [_G548] ;
P = [_G548, _G551],
N = 2,
Y = [_G548, _G551] ;
P = [X, X, X],

edit: as @chac pointed out, the predicate above behaves incorrectly if the first list has (at least) one duplicate element:

?- del(X,[1,2,1],Y).
X = 1,
Y = [2] ;
X = 2,
Y = [1, 1] ;
X = 1,
Y = [1, 2] ;                  <----- wrong
Y = [1, 2, 1].

this is because \==/2 and \=/2 do not actually impose a restriction on the variable. this could be solved by switching the order of the rules in the third clause:

    del(_, [], []).
    del(X, [X|L1], L2):-
        del(X,L1,L2).
    del(X, [H|L1], [H|L2]):-
        del(X,L1,L2),
        X\==H.


4 ?- del(X,[1,2,1],Y).
X = 1,
Y = [2] ;
X = 2,
Y = [1, 1] ;
Y = [1, 2, 1] ;
false.

this however means that the predicate is no longer tail-recursive. to fix that we could keep a list of the values that X shouldn't be:

del(X,L1,L2):-
    del(X,L1,L2,[]).

del(X, [], [], NotX):-
    \+ member(X,NotX).
del(X, [X|L1], L2, NotX):-
    del(X,L1,L2,NotX).
del(X, [H|L1], [H|L2], NotX):-
    X\==H,     % <--- optional; stops the execution earlier (saving time)
    del(X,L1,L2,[H|NotX]).

however, according to the following, the tail recursive version is actually slower:

?-time(forall((between(1,50,N),length(X,N),del2(1,X,[2,3,2,3])),true)).
% 25,600,793 inferences, 5.468 CPU in 5.548 seconds (99% CPU, 4682134 Lips)
true.

?- time(forall((between(1,50,N),length(X,N),del_tr(1,X,[2,3,2,3])),true)).
% 37,346,143 inferences, 6.426 CPU in 6.428 seconds (100% CPU, 5811563 Lips)
true.

still, the + - + doesnt work (it falls in a infinite loop). but why? the problem lies in the order of the clauses: del(1, L1, [2]) will first apply the rule that "adds" X to the head of L1, then applies the same rule forever. this can be countered by using (again) length/2:

?- length(X,2), del(1,X,[2]).
X = [1, 2] ;
X = [2, 1] ;
false.

alternatively we can change the order of the clauses:

del(_, [], []).
del(X, [H|L1], [H|L2]):-
    X\==H,
    del(X,L1,L2),
    X\==H.
del(X, [X|L1], L2):-
    del(X,L1,L2).

yet length/2 might be useful again since without it prolog does a depth first search:

?- del(1,X,[2]).
X = [2] ;
X = [2, 1] ;
X = [2, 1, 1] ;
X = [2, 1, 1, 1] ;
X = [2, 1, 1, 1, 1] ;
X = [2, 1, 1, 1, 1, 1] ;
X = [2, 1, 1, 1, 1, 1, 1] 

of course length/2 can be incorporated in a wrapper predicate since it doesnt affect the other instantiation patterns.

Sweptback

Answer 3

This is not a true answer, just an extended note to Mog and thanosQR answers, too long to fit in a comment. Such answers are agreeable and instructive, but the cut removal need to be rethinked. Consider:

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

This definition allows

?- delMember(Y, [1,2,3,1,2,3,1,2,3], [1,2,1,2,1,2]).
Y = 3.

that fails in original Mog' code because of the guard in last cause. It's worth to note that replacing there the guard with X \== T (that restricts the test to matched instantiation state), also solve this query, as noted by thanosQR.

But none of these snippets solve the general case:

?- del(X,[1,2,1],Y).
X = 1,
Y = [2] ;
X = 2,
Y = [1, 1] ;
X = 1,
Y = [1, 2] ;
Y = [1, 2, 1].

Hyaluronidase

@thanosQR: I took del/3 verbatim from your answer. The output produced seems wrong ; X = 1, Y = [1, 2] ; – Hyaluronidase

oh right, i got it now! (was under the impression that the output you posted was what the solution was supposed have). indeed, as, \==/2 doesnt actually impose a restriction on X it can be later unified with 1. I think that this can be solved by reversing the rules in the body (del(X, [H|L1], [H|L2]):- del(X,L1,L2), X\==H.) – Sweptback

thanks :) edited my post and added a tail-recursive version (i hoped it didnt change the semantics). – Sweptback

even if not tail recursive, it's already faster than the dif/2 version:?- time(forall((between(1,30,N),length(X,N),delMember(1,X,[2,3,2,3])),true)). % 2,557,034 inferences, 1,002 CPU in 1,003 seconds (100% CPU, 2551178 Lips) true. ?- time(forall((between(1,30,N),length(X,N),del2(1,X,[2,3,2,3])),true)). % 1,319,018 inferences, 0,671 CPU in 0,672 seconds (100% CPU, 1965375 Lips). del2 it's your version, delMember use dif/2 – Hyaluronidase

indeed, also, the tail recursive version is in fact (a bit) slower: ?- time(forall((between(1,30,N),length(X,N),del0(1,X,[2,3,2,3])),true)). % 1,318,958 inferences, 0.292 CPU in 0.297 seconds (98% CPU, 4511074 Lips) time(forall((between(1,30,N),length(X,N),del_tr(1,X,[2,3,2,3])),true)). % 1,318,957 inferences, 0.307 CPU in 0.307 seconds (100% CPU, 4292830 Lips) – Sweptback

Answer 4

Here goes a snippet that works also with the first and third arguments uninstantiated:

delMember(X, Y, Z):-
  bagof(A, (setof(X, member(X, Y), L), member(X, L), member(A, Y), A\==X), Z).

I will explain here what this code does. The idea is to:

1. Build a list of distinct members of the input list Y which unify with input member X
2. Then for each X from the list built on 1) discard this element from the input list to get the output list Z without member X.

Step 1 is done with setof(X, member(X, Y), L) and it works in two ways. When parameter X is already instantiated then L will be either the list [X] if X is contained in input parameter Y, of it will fail if X is not contained in Y. On the other hand, if X was uninstantiated then L will be the set of distinct elements of input parameter Y.

Now in step 2 we backtrack over every element of L, and for each member of this list we filter this element from the input list Y which yields the result. We collect all this elements in output list Z.

Note that when parameter X was uninstantiated when the procedure wass called, upon backtracking of member(X, Y) we will get every member of input list Y that will be used for filtering.

Test cases:

?- delMember(Y, [1,2,3,1,2,3,1,2,3], [1,2,3,1,2,3,1,2,3]).
false.

?- delMember(Y, [1,2,3,1,2,3], X).
Y = 1,
X = [2, 3, 2, 3] ;
Y = 2,
X = [1, 3, 1, 3] ;
Y = 3,
X = [1, 2, 1, 2].

?- delMember(Y, [1,2,3,1,2,3,1,2,3], [1,2,1,2,1,2]).
Y = 3.

?- delMember(X,[1,2,1],Y).
X = 1,
Y = [2] ;
X = 2,
Y = [1, 1].

Gridley

I think this answer promotes really bad practices, especially in an post adressed to a beginner. – Mendicant

@Mog: not sure why you said so... maybe because i didn't explain the code ? This implementation does not really use any nasty feature of Prolog... – Gridley

btw, ?- delMember(S, [1, 2], R). S = 1, R = [2] ; S = 2, R = [1]. doesn't give the correct answer R = [1, 2], dif(S, 1), dif(S, 2). See my edit. – Mendicant

That last answer you provided (R = [1, 2], dif(X, 1), dif(X, 2)) is wrong according OPs question. OP says that delMember(Y, [1,2,3,1,2,3,1,2,3], [1,2,3,1,2,3,1,2,3]). should fail. – Gridley

Well OP says true isn't correct maybe because it doesn't provide any meaningful bindings. Correct solutions do. And natural semantics of del as specified in the rest of the OP point towards this being true with correct bindings. – Mendicant