Prolog: How does delete predicate supply even the beginning of the list

Question

I am certainly misunderstanding something about how Prolog works. This question is specific, though I'm looking for an explanation rather than a straight-up solution for a programming problem; a "how" question rather than a "give-me-the-code" question.

Here is the definition for the Prolog delete predicate I am asking about.

delete(A, [A|B], B).  
delete(A, [B, C|D], [B|E]) :-  
    delete(A, [C|D], E).  

My misunderstanding is that it seems to me that a call such as

delete(a, [3,a,b,c,d], X).  

should successfully return [3,b,c,d] (which it does), but that a call such as

delete(a,[1,2,3,a,b,c,d], X)  

should fail to return solutions. However, this latter call does in fact return a good solution of [1,2,3,b,c,d].

The reasons it seems this way to me is as follows. (I think we're now getting closer to whatever it is I'm failing to understand about Prolog.) With reference to this portion of the definition,

delete(A, [B, C|D], [B|E]) . . . 

it looks like only a single element (namely B) preceding the head (namely C) will ever be included in the response. That is why I can't understand how

delete (a, [1,2,3,a,b,c,d], X)

manages to return an answer that includes not only 3, but also 1 and 2, as part of the solution list, yet it does (as in [1,2,3,b,c,d]). Can anyone explain how Prolog works with lists, in this very specific scenario, in a way that shows why it considers 1 and 2 as part of the solution, and not only the 3? Thanks so much.

Answer 1

As a small piece of background, we can consider a singly-linked list to consist of two "constructors": [], the empty list, and [H|T], where H is some sort of value present at the head of the list and T, the tail, the list of what remains after H.

There are two clauses here. The first one is this:

delete(A, [A|B], B).

I would probably frame this a little differently, as delete(Head, [Head|Tail], Tail). This is the clause that enables unifications such as:

?- delete(3, [3,a,b,c,d], X).
X = [a, b, c, d] 

This works because [H|T]=[3,a,b,c,d] will unify H=3 and T=[a,b,c,d]. Try it.

Now let's take a moment and think about how Prolog chooses a clause. At every step, Prolog is essentially attempting a unification. So when presented with delete(a, [1,2,3,a,b,c,d], X), Prolog proceeds by attempting to unify delete(H, [H|T], T) with delete(a, [1,2,3,a,b,c,d], X). This cannot succeed, because a != 1. So Prolog makes another attempt with the second clause, and we find ourselves here:

delete(A, [B, C|D], [B|E]) :-  
    delete(A, [C|D], E).  

Now with the example, Prolog is going to try to unify the head of the clause with delete(A=a, [B=1,C=2|D=[3,a,b,c,d]], [B=1|E]). This succeeds because there is no particular reason why A cannot equal a, B cannot equal 1, C cannot equal 2, and D cannot equal [3,a,b,c,d]. So now Prolog advances to delete(A, [C|D], E) and it will attempt to call delete(a, [2,3,a,b,c,d], E). If you enable trace in your REPL, you will see this at work:

?- trace.
true.

[trace]  ?- delete(a, [1,2,3,a,b,c,d], X).
   Call: (8) delete(a, [1, 2, 3, a, b, c, d], _3240) ? creep
   Call: (9) delete(a, [2, 3, a, b, c, d], _3498) ? creep

You see by the second call that Prolog is now interested in finding delete(a, [2,3,a,b,c,d], _4120) and this is a new variable, not the variable from the previous call. I can assure you the same thing will happen several more times before something new happens.

   Call: (9) delete(a, [2, 3, a, b, c, d], _3498) ? creep
   Call: (10) delete(a, [3, a, b, c, d], _3510) ? creep

On the next call, however, the first clause can be activated:

   Call: (11) delete(a, [a, b, c, d], _3522) ? creep
   Exit: (11) delete(a, [a, b, c, d], [b, c, d]) ? creep

This time, the variable was unified with something. This is because your first clause is a base case. Now looking back at your definition, you can see that the third argument in the second clause is [B|E], which means it will acquire a value when both B and E have been unified with something. So the remainder of the trace is exits of that clause with this variable having been unified with something. Each time, what's happening is simply the B that was stripped off the list prior to the recursive call being prepended on the result:

   Exit: (10) delete(a, [3, a, b, c, d], [3, b, c, d]) ? creep
   Exit: (9) delete(a, [2, 3, a, b, c, d], [2, 3, b, c, d]) ? creep
   Exit: (8) delete(a, [1, 2, 3, a, b, c, d], [1, 2, 3, b, c, d]) ? creep
X = [1, 2, 3, b, c, d] .

And there you have it.

Answer 2

Let's see what happens with the query in question:

?- delete(a,[1,2,3,a,b,c,d], X).

Since a and 1 can not be unified, the first rule fails. However, the second rule matches with, A=a, B=1, C=2 and D=[3,a,b,c,d]. Hence, the recursive goal is called:

delete(a,[2|[3,a,b,c,d]],E)

Again, the first rule doesn't match, because a differs from 2. The second rule succeeds again, this time with A=a, B=2, C=3 and D=[a,b,c,d]. Hence, the recursive call:

delete(a,[3|[a,b,c,d]],E)

Yet again, the first rule fails and the second succeeds with A=a, B=3, C=a and D=[b,c,d]. Hence, the recursive call:

delete(a,[a|[b,c,d]],E)

Now, in head of the first rule, a=a is successfully unified, so the rule succeeds with A=a, B=[b,c,d]. Going back through the recursions this yields:

E=[b,c,d], B=3 therefore [B|E]=[3|[b,c,d]]=[3,b,c,d] 

E = [3,b,c,d], B=2 therefore [B|E]=[2|[3,b,c,d]]=[2,3,b,c,d] 

E = [2,3,b,c,d], B=1 therefore [B|E]=[1|[2,3,b,c,d]]=[1,2,3,b,c,d] 

So Prolog tells you, that there's indeed a solution:

?- delete(a,[1,2,3,a,b,c,d], X).
X = [1, 2, 3, b, c, d]

Now you ask if there are any other solutions by pressing ;

?- delete(a,[1,2,3,a,b,c,d], X).
X = [1, 2, 3, b, c, d] ;

Prolog goes back to the open choice-point and follows the recursive rule until D=[]. The next recursive call fails for the first rule, since []=[A|B] can not be unified. It also fails for the second rule, because []=[B,C|D] can not be unified either. So Prolog dutifully reports, that there are no more solutions:

?- delete(a,[1,2,3,a,b,c,d], X).
X = [1, 2, 3, b, c, d] ;
false.