Controlling 'cut' in recursive function to remove an element from a list in Prolog

Question

I'm trying to create a function that would remove all the occurrences of an element form a list. I saw that some solutions have already been mentioned. But I'm trying a different approach. I am basically copying the elements in a new list if they are not equal to what I want to delete.

remove(X, [], A, A):-!.
remove(X1, [X1|T1], A, R):-
    remove(X1, T1, A, R).
remove(X2, [H2|T2], A2, R2):-
    remove(X2, T2, [H2 |A2], R2).

The first answer is the result I expect, but then it keeps providing more possibilities:

?- remove(x, [x, b,c,x,x], [], Result).
Result = [c, b] ;
Result = [x, c, b] ;
Result = [x, c, b] ;
Result = [x, x, c, b] ;
Result = [c, b, x] ;
Result = [x, c, b, x] ;
Result = [x, c, b, x] ;
Result = [x, x, c, b, x].

1. [added after edit] Why does it keep providing answers?
2. Is there a way to have it stop at the first result?

Edit: I also just realized that this is also reversing my list :(

Answer 1

Short answer: if you write remove(X2, [H2|T2], A2, R2), that does not mean that X2 and H2 are different, so you need to prevent Prolog from taking that branch. A fundamental aspect of Prolog is that it automatically performs backtracking. So the fact that one clause "fires" does not prevents it from other clauses to fire.

A fast fix can be to add a cut to the second clause:

remove(X, [], A, A) :- 
    !.
remove(X1, [X1|T1], A, R):-
    !,  % a cut
    remove(X1, T1, A, R).
remove(X2, [H2|T2], A2, R2):-
    remove(X2, T2, [H2 |A2], R2).

So in case X2 and H2 can be unified, Prolog will take the second clause, and then the cut will prevent Prolog taking the third clause.

Another important aspect is that your program reverses the list. We can fix this by dropping the accumulator here (you can also work with difference lists as an accumulator, but this will introduce too much complexity for now):

remove(_, [], []).
remove(X1, [X1|T1], R):-
    !,
    remove(X1, T1, R).
remove(X2, [H2|T2], [H2|R2]):-
    remove(X2, T2, R2).

And now you can use it to remove elements from a list that might be the same: note that Prolog performs unification, so it will also remove free variables, or partially ungrounded ones that can unify.

But: cuts are dangerous and will usually result in impure predicates. The idea of Prolog is that you can use predicates in multiple directions. For instance you can generate all possible lists with such that the outcome after removing 3 would be [1,4,2,5]. In order to do this, we can add a constraint dif/2:

remove(_, [], []).
remove(X2, [H2|T2], [H2|R2]) :-
    dif(X2, H2),
    remove(X2, T2, R2).
remove(X1, [X1|T1], R):-
    remove(X1, T1, R).

we also remove the cut here.

Now we can query it with different tasks:

1. remove all 4s from the list [1,4,2,4,4,5]:

   ?- remove(4,[1,4,2,4,4,5],X).
   X = [1, 2, 5] ;
   false.
   

2. remove an element A from the list:

   ?- remove(A,[1,4,2,4,4,5],X).
   X = [1, 4, 2, 4, 4, 5],
   dif(A, 5),
   dif(A, 4),
   dif(A, 4),
   dif(A, 2),
   dif(A, 4),
   dif(A, 1) ;
   A = 5,
   X = [1, 4, 2, 4, 4] ;
   A = 2,
   X = [1, 4, 4, 4, 5] ;
   A = 4,
   X = [1, 2, 5] ;
   A = 1,
   X = [4, 2, 4, 4, 5] ;
   false.
   

3. generate all lists that could be the input of the removal such that the result is [1,4,2,5] (infinite amount of answers):

   ?- remove(A,L,[1,4,2,5]).
   L = [1, 4, 2, 5],
   dif(A, 5),
   dif(A, 2),
   dif(A, 4),
   dif(A, 1) ;
   L = [1, 4, 2, 5, A],
   dif(A, 5),
   dif(A, 2),
   dif(A, 4),
   dif(A, 1) ;
   L = [1, 4, 2, 5, A, A],
   dif(A, 5),
   dif(A, 2),
   dif(A, 4),
   dif(A, 1) ;
   L = [1, 4, 2, 5, A, A, A],
   dif(A, 5),
   dif(A, 2),
   dif(A, 4),
   dif(A, 1) ;
   L = [1, 4, 2, 5, A, A, A, A],
   dif(A, 5),
   dif(A, 2),
   dif(A, 4),
   dif(A, 1)
   ...
   

4. what element is removed from the list?

   ?- remove(A,[1,4,3,2,5],[1,4,2,5]).
   A = 3 ;
   false.
   
   ?- remove(A,[1,3,4,3,2,5],[1,4,2,5]).
   A = 3 ;
   false.
   

5. can we obtain a list [1,4,2,5] from removing only one sort of value from [1,9,4,3,2,5]? (No!)

   ?- remove(A,[1,9,4,3,2,5],[1,4,2,5]).
   false.
   

Answer 2

The problem is in the clause:

remove(X2, [H2|T2], A2, R2):-
    remove(X2, T2, [H2 |A2], R2).

You need to state explicitly that X2 differs from H2. You can do that by using dif/2:

remove(X2, [H2|T2], A2, R2):-
        dif(X2,H2),
        remove(X2, T2, [H2 |A2], R2).

If you don't state that X2,H2 are different Prolog will try both cases which will lead to keep or throw element H2.