Removing element from a list

Question

I know this question has been asked already, but I just want to ask about my specific implementation. I'm writing this function just to practice Prolog and better understand Prolog. Here's what I have:

del(Ele, [H], [H]) :- Ele \= H.
del(Ele, [H|T], [H|New]) :-
    Ele \= H,
    del(Ele, T, [New]).

The idea is that I will add an element to a new list called New if the element I want to delete is not equal to H. From what I understand, my code isn't working because my code stops when I reach an element where Ele \= H. Any ideas how to fix this?

For example, del(5, [3,4,5,6,7], X) will return false.

Also, are there any better solutions? It seems like a bad solution to keep adding every element in a list to a new list, since this would be slow for a large list. I'd rather just keep the elements currently in the list, find element(s) that match Ele, remove that element, and then return the list.

Answer 1

You have described some cases where del/3 should hold. But these are only cases where Ele is not equal/unifiable to the elements in the list. There are several things missing:

What about the empty list?

What, if Ele is equal to the element?

So you need to add further clauses. (Later you might also remove some, for reasons of redundancy).

If you are using SWI, B, SICStus, or YAP, consider to use dif/2 in place of (\=)/2. prolog-dif

Here is the reason why dif/2 is so helpful in this case. With dif/2 you would have a pure monotonic program. And you could try it out directly:

?- del(5, [3,4,5,6,7], X).
false.

The same problem you had. Let me just restate what the problem is: You expect that something should hold, but it does not. So the relation is too narrowly defined. If I generalize the query, I might get a better answer. Try del(E, [3,4,5,6,7], X). but again the same false. So I'll try an even more general query:

?- del(E, Xs, Ys).
Xs = Ys, Ys = [_G1076],
dif(E, _G1076) ...

Looks perfect to me! Maybe another answer:

?- del(E, Xs, Ys).
Xs = Ys, Ys = [_G1076],
dif(E, _G1076) ;
Xs = [_G1133, _G1136],
Ys = [_G1133|_G1136],
dif(E, _G1136),
dif(E, _G1133) ...

Now we got an incorrect answer. I will instantiate it a bit to make it better readable:

?- del(e, [a,b], Ys).
Ys = [a|b] ;
false.

This answer is clearly incorrect because [a|b] is not a list. And, it's probably the smallest incorrect answer...

What I want to show you by this is that you can most often locate problems without going through it step-by-step. Step-by-step debugging does not even work in imperative languages once you get a more complex control flow (like concurrency) ; and it does not scale at all in Prolog.

Answer 2

Let's trace:

?- trace, del(5, [3,4,5,6,7], X).
   Call: (7) del(5, [3, 4, 5, 6, 7], _G218) ? creep
   Call: (8) 5\=3 ? creep
   Exit: (8) 5\=3 ? creep
   Call: (8) del(5, [4, 5, 6, 7], [_G344]) ? creep
   Call: (9) 5\=4 ? creep
   Exit: (9) 5\=4 ? creep
   Call: (9) del(5, [5, 6, 7], [[]]) ? creep
   Fail: (9) del(5, [5, 6, 7], [[]]) ? creep
   Fail: (8) del(5, [4, 5, 6, 7], [_G344]) ? creep
   Fail: (7) del(5, [3, 4, 5, 6, 7], _G218) ? creep
false.

So you can see your code is actually failing when it gets to the 5 because 5 \= 5 is false. Your first rule is never matched because the list has more than one item in it. The second rule recurs "correctly" after finding 5 \= 3 and 5 \= 4 but since you have no 5 = 5 case in any of your rules, the failure happens there.

Incidentally, let's see what happens when 5 does not occur in the list:

?- trace, del(5, [3,4,6,7], X).
   Call: (7) del(5, [3, 4, 6, 7], _G350) ? creep
   Call: (8) 5\=3 ? creep
   Exit: (8) 5\=3 ? creep
   Call: (8) del(5, [4, 6, 7], [_G473]) ? creep
   Call: (9) 5\=4 ? creep
   Exit: (9) 5\=4 ? creep
   Call: (9) del(5, [6, 7], [[]]) ? creep
   Fail: (9) del(5, [6, 7], [[]]) ? creep
   Fail: (8) del(5, [4, 6, 7], [_G473]) ? creep
   Fail: (7) del(5, [3, 4, 6, 7], _G350) ? creep
false.

This is why I said "correctly" before: your inductive case isn't right either. For one thing, you have del(Ele, T, [New]) but up above you have del(Ele, [H|T], [H|New]) so you're unwrapping the list an extra time on the right (this is why our trace has [[]] in it). But @false hit the larger issue which is that you simply never account for the case where you actually find what you are looking to delete. :) You also don't handle the case where the list is empty.

It is an unfortunate fact of life that traversing data structures and looking at each item is going to be O(N). Another unfortunate fact is that in functional and declarative languages (languages that lack "assignables") modifying a list means copying at least part of the list. There are more efficient ways to go about this in Prolog (you could use difference lists, for instance) but they will share the same basic problem. Prolog efficiency is a rather large topic. I'd tell you to not worry about it too much up front, but it has a way of becoming your concern pretty quickly. But in this case, no, there isn't really a substantially more efficient approach using destructive updates.