How prolog deals with this step-by-step?

Question

I'm trying to understand prolog but I am stuck with one example, can you explain to me how is prolog going through this call:

eli(2,[2,2,1],L).

using those facts:

eli(X,[],[]).
eli(X,[Y],[Y]).
eli(X,[X,X|L],L1) :- eli(X,L,L1).
eli(X,[Y|L],[Y|L1]) :- eli(X,L,L1).

The results are:

L = [1]
L = [1]
L = [2, 2, 1]
L = [2, 2, 1]

and I'm not really sure why.

Thanks in advance!

Answer 1

It looks like your predicate is mean to delete two consecutive appearance of any element.

First clause, if the target list is empty, return the empty list. In this case the X variable in the fact is not necessary. Replace X by te anonymous variable.

eli(_,[],[]).

Second clause is similar to the first, but it matches the target list if it contains only one element. Variable X is also not necessary.

eli(_,[Y],[Y]).

Third clause, if the target list contains two or more elements, and in the Head of the list both elements are equal to X, don't copy this two elements to the Result list, and make a recursive call to the eli/3 predicate in the body of the rule, to continue the search.

eli(X,[X,X|L],L1) :- eli(X,L,L1), !.

In this case we add the cut predicate, to avoid backtracking after this rule succeeded. Otherwise you may get undesired results, like L = [2, 2, 1] in your test.
And the last clause, copy the element in the Head of the Target list to the Result list, and continue the recursive call, this will stop when the Target list is empty or contains only one element (your first two clauses).

eli(X,[Y|L],[Y|L1]) :- eli(X,L,L1).

Now this is your predicate eli/3:

eli(_,[],[]).
eli(_,[Y],[Y]).
eli(X,[X,X|L],L1) :- eli(X,L,L1), !.
eli(X,[Y|L],[Y|L1]) :- eli(X,L,L1).

Test:

?- eli(2,[2,2,1],L).
L = [1]

?- eli(2,[1,2,2,3],L).
L = [1, 3]