Prolog: How does delete/3 works?

Question

for sure all Prolog fans heard about the delete or remove predicate.

del(X,[X|Tail],Tail).
del(X,[H|Old],[H|New]) :- del(X,Old,New).

I have problems to understand whats going on. The first row will be used, if the first element in the list is the searched element. Then the list will be cut in Head (X) and the Tail and Tail is the result. But at which point the first X will be compared with the X from the X|Tail? At the second row, i even don't understand, when the X and H will be compared, if X = H?

I hope someone can tell that for a Prolog beginner.

Isabelle Newbie Isabelle Newbie · Accepted Answer · 2020-07-03T13:45:20

First let's note that this definition implements a very particular sense of deleting an element: del(Element, List, Rest) only succeeds if the Element actually appears in the List, otherwise it fails:

?- del(a, [a, b, c], Rest).
Rest = [b, c] ;
false.

?- del(x, [a, b, c], Rest).
false.

This will be important in a moment.

But at which point the first X will be compared with the X from the X|Tail?

X occurs twice in the head of the clause, and these two occurrences must unify. You could read

del(X, [X | Tail], Tail).

as something similar to:

del(X1, [X2 | Tail], Tail) :-
    X1 = X2.

So the "comparison" of X against itself is implicit in the fact that it occurs multiple times in different arguments. This clause will not match a goal like del(a, [b | Xs], Ys) for example: Prolog would have to unify the first occurrence of X with a and the second occurrence of X with b, and this is not possible. So if the element of interest is not unifiable with the first element of the list, the first clause cannot apply. The second clause must apply.

If, however, the element does unify with the first element of the list, then the remaining list is just the Tail, i.e., if the first clause succeeds, then it deletes exactly one occurrence from the list it is given.

At the second row, i even don't understand, when the X and H will be compared, if X = H?

They will not be compared! It doesn't matter to this clause whether X is unifiable with H or not. If this clause succeeds, then the first element of the list will be preserved, no matter if it is equal to X or not. However, this is a recursive clause. It can only succeed if some recursive call eventually ends in a non-recursive clause that succeeds. The only non-recursive clause is the first one, for which we know that it will delete exactly one occurrence of X. So the second clause doesn't need to care about the list element it looks at, because its role is to preserve all the non-deleted elements. Actual deletion is the role of the first clause.

However, this not caring about the element only succeeds if the first clause will succeed, which is only the case if the rest of the list contains an element that can be deleted. If it does not, the entire recursive call fails. This is the reason for the somewhat unintuitive behavior that the element to be deleted must be present in the original list.

Prolog: How does delete/3 works?

1 Answers