Simple Prolog delete from list

Question

(This is NOT a coursework question. Just my own personal learning.)

I'm trying to do an exercise in Prolog to delete elements from a list. Here's my code :

deleteall([],X,[]).
deleteall([H|T],X,Result) :- 
    H==X,
    deleteall(T,X,Result).
deleteall([H|T],X,[H|Result]) :- deleteall(T,X,Result).

When I test it, I first get a good answer (ie. with all the Xs removed.) But then the backtracking offers me all the other variants of the list with some or none of the instances of X removed.

Why should this be? Why do cases where H==X ever fall through to the last clause?

Folium

Thank you interstar for asking how to delete, I was doing the same excercise. I haven't had used == operator before in prolog. I have understood your solution. We can improve by replacing X to _ in the first sentence to avoid singleton variable. Also we should put ! operator on the second and third cases. – Jez

Answer 1

The last clause says that when removing X from a list, the head element may stay (independently of its value). Prolog may use this clause at any time it sees fit, independently of whether the condition in the preceding clause is true or not backtrack into this clause if another clause fails, or if you direct it to do so (e.g. by issuing ; in the top-level to get the next solution). If you add a condition that the head element may not equal X, it should work.

Edit: Removed the incorrect assertion I originally opened with.

Sophia

Oh! For some reason I kind of assumed it was. (Ie. the listing counted.) That would explain a LOT of problems I'm having. – Folium

-1. Prolog clauses are executed in left-to-right, top-down order, although the interpreter may backtrack into following clauses upon failure. – Galumph

The order of clauses is not entirely unordered. They are considered in a fixed order. But your point behind is true: As long as there is no ! in your clauses, every clause will contribute its answers. Only non-termination and errors may hide further answers. – Escalera

@larsmans: I removed the first sentence. The middle sentence is probably not entirely correct; feel free to edit it. – Sophia

@larsmans: Thanks. At least, the very opening of my initial sentence was correct: "It's been a while since I did any prolog" ;-) – Sophia

OK. Thanks for the correction. Though actually I'm no longer sure quite what you're saying. If the order is important, how come we ever execute the last clause in situations where X == H. Won't the second clause have already caught that? – Folium

Maybe I don't understand what "backtracking" means. I thought it tracked all alternative correct solutions. Does it actually just mean "after matching one clause try matching the next"? – Folium

Answer 2

When you are using (==)/2 for comparison you would need the opposite in the third rule, i.e. (\==)/2. On the other hand, such a definition is no longer a pure relation. To see this, consider deleteall([X],Y,Zs), X = Y.

For a pure relation we need (=)/2 and dif/2. Many Prologs like SWI, YAP, B, SICStus offer dif/2.

deleteall([],X,[]).
deleteall([H|T],X,Result) :- 
    H=X,
    deleteall(T,X,Result).
deleteall([H|T],X,[H|Result]) :-
    dif(H,X),
    deleteall(T,X,Result).

Look at the answers for deleteall([X,Y],Z,Xs)!

Edit (after four years):

More efficiently, but in the same pure vein, this can be written using if_/3 and (=)/3:

deleteall([], _X, []).
deleteall([E|Es], X, Ys0) :-
   if_( E = X, Ys0 = Ys, Ys0 = [E|Ys] ),
   deleteall(Es, X, Ys).

Escalera

@Dunes: Please read the link to see that it is (=)/3 and not (=)/2! – Escalera

None of your = predicates have three terms though. They're all in the form A = B. Perhaps you should provide a link to documentation for (=)/3 and what is does in your answer. – Mahan

There is exactly a link above to document this! It is if_/3 that calls it. The exact call to (=)/3 will be call(A = B, T) which results in call(=(A,B,T)). – Escalera

Ah, I see. However, =/3 is not part of the ISO. I think it's sicstus specific. As is if/3, which I didn't initially realise. Though SWI seems to have a compatibility module with it, but it's not implemented as you suggest. swi-prolog.org/pldoc/doc/_SWI_/library/dialect/… Might be best to state which dialect you using for the more efficient answer. – Mahan

It's if_/3 and not if/3. And no dialect is involved here. All is defined in the link above! Please read it. And SWI is definitely not a good reference w.r.t ISO. – Escalera