prolog deleteall doesn't work

Question

I was trying to find out the problem but unsuccessfully Could you tell me what is wrong?

% using accumulator
deleteall(X,Y,Zs) :- deleteall(X,Y, [], Zs).
deleteall(X, [], Zs, Zs).
deleteall(X, [X|Xs], Xs, V).
deleteall(X, [Y|Xs], [Y|Zs], V) :- deleteall(X, Xs, Zs,V).

Answer 1

Singleton variables are always suspicious, and in your case, what's the meaning of V in deleteall(X, [X|Xs], Xs, V).?

Apart that, I don't understand why you are using an accumulator.

Are you assigned to reverse the elements not deleted? Otherwise, here is a deleteall that works...

deleteall(_, [], []).
deleteall(X, [X|Xs], Zs) :- !, deleteall(X, Xs, Zs).
deleteall(X, [Z|Xs], [Z|Zs]) :- deleteall(X, Xs, Zs).

test:

?- deleteall(2,[1,2,3,54,2,1,4,2],X).
X = [1, 3, 54, 1, 4] ;
false.

Answer 2

From you code, it seems that you want delete-all semantics based on unification (an alternative would be to delete only terms that are equal using (==)/2). Are all the list elements (and the elements that you want to delete) always ground? If not, your code can fail whenever the element that you want to delete is partially instantiated and gets further instantiated when unifying with one of the list elements. You can solve this problem by using e.g. double negation in the body instead of head unification. As "chac" already noted, you're also leaving choice-points behind. Using a cut or an if-then-else solves that problem. Another way to improve your code is to move the list to the first argument, allowing Prolog's first-argument indexing to give you better performance (assuming, of course, that calls to the predicate will have the first argument instantiated). Follows a definition along these lines:

delete_all([], _, []).
delete_all([X|Xs], Y, Zs) :-
    (   \+ X \= Y ->
        delete_all(Xs, Y, Zs)
    ;   Zs = [X|Zs0],
        delete_all(Xs, Y, Zs0)
    ).

Answer 3

For a pure solution, consider this answer – note the different argument order.

But your actual question was: What is wrong with your solution?

There is a way to answer this in a manner that is unique to Prolog. In other programming languages, you would have to figure out meaningful test cases. Then, you would use such test cases to see if your implementation works. Of course, that is possible in Prolog too.

But think about the actual cost to figure out those test cases! You would have to understand the entire relation in all its detail. You would have to have all the fine print about the data structures mentally present. That is quite an intellectual effort. Your example is very simple, so that effort appears to be petty. But imagine some further detail added here and there.

So how can we figure out a test case for a predicate without understanding the actual relation?

Simply take the most general query. That is, a goal with distinct variables in all arguments. For your example, that would be deleteall(X, Xs, Ys). Now, our work is done and we can let Prolog fill in the blanks.

?- deleteall(X,Xs,Ys).
   Xs = Ys, Ys = []
;  Xs = [X]
;  false.

With your definition we get two answers. The first answer contains solutions for Xs being the empty list []. The second answer contains solutions for Xs being a one element list. And that is all your relation describes.

What about lists containing two or even more elements? There are no solutions for them. So, your definition is too specific in that respect.

And the second answer holds for all Ys. E.g. also deleteall(1,[1],[2,3]) holds – according to your definition. Even worse: deleteall(1,[1],[1]). No deletion at all. So your definition is here too general.

---

Where's the catch to all this? Well, you have to write pure, monotonic programs. That is, impure built-ins like !/0, (\+)/1, (\=)/2, (\==)/2 and side effecting built-ins must not be used (or used with very special care).