Some doubts about how work this particular query of a delete from a list predicate

Question

I have a doubt about how work this query for this del/3 predicate:

/* BASE CASE: If I delete X from List and X is the HEAD of List, NewList is
              the Tail of List
*/
del(X, [X|Tail], Tail).

/* GENERAL CASE: If the head of List is not X then the program have to delete
                 X in the Tail of List
*/
del(X, [Y|Tail], [Y|Tail1]) :- del(X, Tail, Tail1).

The predicate logic is very simple: delete X item form a list creating a new list without X: if X is in the head of the list the newlist is its tail. Otherwise, if the X item is not in the head of the list, try to find it (and delete) in the Tail creating a new tail Tail1.

Ok, so I have no problem with the predicate logic but I am having some problem trying to understand how work this query (I have to use it in another program):

del([Top1|Stack1], [[a,b,c],[],[]], Stacks1).

So this query have to delete [Top1|Stack1] from [[a,b,c],[],[]] that is a list of stacks (in this particular case I have 3 stacks: [a,b,c] and 2 empty stacks: []) generating so a new list of stacks named Stacks1

If I try to execute a trace of the query I obtain this:

[trace]  ?- del([Top1|Stack1], [[a,b,c],[],[]], Stacks1).
   Call: (7) del([_G389|_G390], [[a, b, c], [], []], _G412) ? creep
   Exit: (7) del([a, b, c], [[a, b, c], [], []], [[], []]) ? creep
Top1 = a,
Stack1 = [b, c],
Stacks1 = [[], []] .

I have some difficulties to understand why: [Top1|Stack1] is unified with the first stack [a, b, c]

EDIT: I think that maybe work in this way: The list of Stacks is: [[a,b,c],[],[]] that is a list of lists wherein the first list is: [a,b,c] (that is the head of this list of list**

So when I write: [Top1|Stack1] happens that:

Top1 = [a,b,c] *Stack1 = [[],[]]*

So happens that Top1 is the first stack in the stacks list and Stack1 is the list of others stacks.

So when I write the predicate:

 del([Top1|Stack1], Stacks, Stacks1).

(where, for example: Stacks = [[a,b,c],[],[]])

It work in this way:

It unifiest Top1 with the first stack in stack list: [a,b,c] and delete it from Stacks list...

My dount is related on Prolog semantic viz when I execute a simple query as:

del(b, [a,b,c], NewList).

it delete b item from the list and NewList=[a,c]

but when I have that the field of the item that have be delete is something like: [Head|Tail] is it the Head item that have be to deleted?

Will Ness Will Ness · Accepted Answer · 2013-05-09T12:33:44

The query D=[[a,b,c],[],[]], del([A|B], D, C) picks any list matching [A|B] from among D's elements. The only possibility here is [A|B]=[a,b,c] and the leftovers are C=[[],[]].

In general del fully backtracks, finding all possibilities one by one. Here there is only one possibility.

To better understand del, try this:

2 ?- del(X,[A,B,C],D).
X = A,
D = [B, C] ;
X = B,
D = [A, C] ;
X = C,
D = [A, B] ;
false.

It isn't trying to "find" X; it's just picking it one by one from among the possibilities (the 2nd argument). That's what the predicate says that it is / does.

Of course if the lists are instantiated to ground terms, some might not match and will be rejected, creating an impression of a value being searched for:

4 ?- del(b, [a,b,c,d], R).
R = [a, c, d] ;
false.

5 ?- del(b, [a,b,X,d], R).
R = [a, X, d] ;
X = b,
R = [a, b, d] ;
false.

The term [A|B] just matches any non-empty list (or a logical variable):

6 ?- del([A|B], [[a],b,X,d], R).
A = a,
B = [],
R = [b, X, d] ;
X = [A|B],
R = [[a], b, d] ;
false.

7 ?- del([A|B], [[a],b,[],d], R).
A = a,
B = [],
R = [b, [], d] ;
false.

So e.g. del([A|B], [[1,2,3], [4,5], [], [6]], R) will pick any non-empty list from the 4 lists given in the 2nd argument of this sample call, and while it does that, it will bind A to the head element and B to the rest of elements of the list that was picked.

This predicate is known as select/3 in the wild. :)

Illustration:

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

     X        X
     --------------------
              T        T
              a        a
              i        i
              l        l

del(X, [Y|Tail], [Y|Tail1]) :- del(X, Tail, Tail1).

              Y        Y
     --------------------
              T        T
       /      .        a
     X -      .        i
       \      .        l
              .        1
              l

Some doubts about how work this particular query of a delete from a list predicate

1 Answers