Menu
(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?
588
This predicate can be used to select an element from a list, delete an element or insert it. The definition of this Prolog library predicate is: delete(A, [A|B], B). delete(A, [B, C|D], [B|E]) :- delete(A, [C|D], E).
drop(L, N, X):- drop2(L, N, X, N).
Although lists in Prolog cannot be modified, it is possible to add elements to the end of a list with an unspecified length. In this way, items can be "appended" to a list without creating another list: :- initialization(main). append_to_list(List,Item) :- append_to_list(List,Item,0).
That's what it means, but not because it happens to be true in Haskell. [] is an empty list. Note that [x|y] is different than both of these. Also, since x and y start with lower case, they ate atoms, not variables. [X|Y] is a list of one or more elements.
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).
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.
33
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
