5

(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?

false
  • 10,264
  • 13
  • 101
  • 209
interstar
  • 26,048
  • 36
  • 112
  • 180
  • 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. – Yone May 09 '17 at 17:26

2 Answers2

7

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).
false
  • 10,264
  • 13
  • 101
  • 209
  • @Dunes: Please read the link to see that it **is** `(=)/3` and not `(=)/2`! – false Aug 20 '22 at 16:33
  • 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. – Dunes Aug 20 '22 at 16:43
  • 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))`. – false Aug 20 '22 at 16:46
  • 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. https://www.swi-prolog.org/pldoc/doc/_SWI_/library/dialect/sicstus.pl?show=src#if/3 Might be best to state which dialect you using for the more efficient answer. – Dunes Aug 20 '22 at 17:08
  • 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. – false Aug 20 '22 at 17:20
2

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.

Fred Foo
  • 355,277
  • 75
  • 744
  • 836
Aasmund Eldhuset
  • 37,289
  • 4
  • 68
  • 81
  • Oh! For some reason I kind of assumed it was. (Ie. the listing counted.) That would explain a LOT of problems I'm having. – interstar Jun 22 '11 at 14:36
  • 2
    -1. Prolog clauses are executed in left-to-right, top-down order, although the interpreter may backtrack into following clauses upon failure. – Fred Foo Jun 22 '11 at 14:44
  • 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. – false Jun 22 '11 at 14:47
  • @larsmans: I removed the first sentence. The middle sentence is probably not entirely correct; feel free to edit it. – Aasmund Eldhuset Jun 22 '11 at 14:54
  • @larsmans: Thanks. At least, the very opening of my initial sentence was correct: "It's been a while since I did any prolog" ;-) – Aasmund Eldhuset Jun 22 '11 at 15:26
  • 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? – interstar Jun 25 '11 at 01:28
  • 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"? – interstar Jun 25 '11 at 01:33