How to remove all occurrences?

Question

I am trying to understand why code 1 works fine but code 2 outputs false:

remove(X,[],[]).
remove(X,[X|Y],Z):-remove(X,Y,Z). % [X|Y] is the input list
remove(X,[F|Y],[F|Z]):-remove(X,Y,Z). % code 1


remove(X,[],[]).
remove(X,[X|Y],Z):-remove(X,Y,Z). % [X|Y] is the input list
remove(X,[F|Y],Z):-remove(X,Y,[F|Z]). % code 2

Third clause of code 2 doesn't seem to make logical sense. It means something totally different than the third clause of code 1. Recursively it will ultimately fail to match the base case. — lurker, Mar 06 '19 at 14:11
can you help me trace it because i can't seem to understand how the base case will not match and thank you. — Alei Osama, Mar 06 '19 at 15:36
Look at the recursive call. It keeps including an additional element in the list for the 3rd argument. Your base case assumes the 3rd argument tends toward the empty list. It can't possibly match. — lurker, Mar 06 '19 at 17:46

repeat · Answer 1 · 2019-03-07T22:49:29.440

Both predicates you presented—code 1 and code 2—are broken.

And the reason why you did not notice that is: queries.

#1) Consider the query shown in this previous "answer":

?- remove(x, [x,a,b,c,x,d], R).
R = [a,b,c,d]                      % okay

Okay? Yes, but there may be more answers. Let's press ;↵!

;  R = [a,b,c,x,d]                 % BAD!
;  R = [x,a,b,c,d]                 % BAD!
;  R = [x,a,b,c,x,d]               % BAD!
;  false.                          % (no more answers)

These three answers are invalid, as each R contains some x.

The bottom like: Don't just look at some query answers. Look at all query answers!

#2) Prolog programs comprise different kinds of clauses: facts, rules, and queries.

Queries are a very—if not the most—important part of your program.

Queries are both documentation and specification. Most importantly, they enable you to delegate the "mechanical" part of program development to the Prolog processor.

So which queries to write?

Start with the most general query:
```
?- remove(A,B,C).
```

Queries you expect to succeed:

?- remove(x,[x,a,x,p],[a,p]).   % x is first element
?- remove(x,[a,x,p,x],[a,p]).   % x is last element
?- remove(x,[a,x,p],[a,p]).

Queries you expect to fail

?- \+ (remove(x,[a,x,p],Ls), dif(Ls,[a,p])).

Ground queries:
```
?- remove(x,[],[]).
```
Non-ground queries (queries with variables):
```
?- remove(X,[a,b,a,c,d,c,a,b],Xs).
```

The bottom line: Without queries you are not writing code, you are only writing text.

#3) Now let's get to fixing code 1: Look at both recursive clauses!

remove(X,[X|Y],Z) :- remove(X,Y,Z).
remove(X,[F|Y],[F|Z]) :- remove(X,Y,Z).

The first rule relates X with the first list [X|Y]. OK!

The second rule does not X with either [F|Y] or [F|Z]. BAD!

By adding a prolog-dif goal dif/2 to the second clause we can build that connection.

#4) Done! Here's the complete code for predicate remove/3:

remove(_X, [], []).
remove(X, [X|Y], Z) :-
   remove(X, Y, Z).
remove(X, [F|Y], [F|Z]) :-
   dif(X, F),
   remove(X, Y, Z).

Great answer. Unfortunately your corrected program does not work in these modes: `remove(a, Y, [b]).` and `remove(X, Y, [b]).` both raise `Stack limit (0.2Gb) exceeded` on SWISH. I have opened a specific question [here](https://stackoverflow.com/q/68885498/2326961) (still unanswered). — Géry Ogam, Aug 25 '21 at 12:50

score 1 · Accepted Answer · answered Mar 06 '19 at 16:04

Consider querying,

?- remove(x, [x,a,b,c,x,d], R).

The problem with code 2 is that at some point, after extracting all the elements in the 2nd list, it becomes empty. At this point, upon recursion, the only possible choice is the first clause because the 2nd and 3rd clause requires that the list to have a head, which it doesn't because its empty.

Thus, it tries to perform unification with the first. Now, the first 2 predicates are fine, but the last one is problematic.

Namely, it tries to unify [] = [d, c, b, a | _free_ ]. Which is not possible because [] is not a 'free variable'

My terminologies might be wrong however... but I believe the essence is there.

How to remove all occurrences?

2 Answers2

Linked