Strange results for list manipulation

Question

I'm trying to implement some predicates for list manipulation in Prolog. Everything works as desired. For example

append([],Ys,Ys).
append([X|Xs],Ys,[X|Zs]) :- append(Xs,Ys,Zs). 

Sample query:

?- append([1,2,3],[4,5,6],X).
X = [1,2,3,4,5,6].                   % OK

But I'm having trouble with the 'delete'-predicate. Here's how it's implemented:

delete(X,[Y|Ys],Zs) :- X == Y, delete(X,Ys,Zs).
delete(X,[_X|Ys],[_Z|Zs]) :- delete(X,Ys,Zs).
delete(_X,[],[]).

Sample query with bad result:

?- delete(4,[1,2,3,4],X).
X = [_G8975, _G8978, _G8981].       % BAD

I've tested it with further input and it always returns a list of the expected length so in a way it works. But why am I getting only those cryptic _GXXXX and not the numbers?

Many thanks in advance!

Answer 1

There are several issues in your program. But first, as a beginner:

Stick to the pure monotonic subset of Prolog

In your program, you are using (==)/2 which is no longer in that pure subset. In your case replace it by (=)/2.

Always look at all the answers

Prolog's top-level loops shows you only the first answer. You have to demand for more by pressing ; or SPACE. Your program with (=)/2 gives (with more readable variables):

?- delete(4,[1,2,3,4],X).
   X = [_A,_B,_C]
;  X = [_A,_B,_C,_D]
;  false.

That is: Not only is the first answer unexpected, but there is a second one, with a list of same length as the original one. On the other hand, the first answer included the expected solution. So the program is rather too general.

Reduce the input size

?- delete(4,[4],L).
   L = []
;  L = [_A]
;  false.

The first answer seems now correct, but the second is entirely unexpected. That is, the definition is too general as witnessed by delete(4,[4],[any])

Specialize the program

To localize the program, specialize the program by introducing goals like false, and = as much as possible, and as long as delete(4,[4],[any]) succeeds. I come up with:

?- delete(4,[4],[any]).

delete(X,[Y|Ys],Zs) :- false, X = Y, delete(X,Ys,Zs).
delete(X,[_X|Ys],[_Z|Zs]) :- X = 4, _X = 4, _Z = any,
   delete(X,Ys,Zs).
delete(_X,[],[]) :- _X = 4.

Now it should be evident that in this rule, _X =4, _Z = any should be rather the same, and X = 4, _X = 4 should be different. Inequality is best expressed with dif/2.

delete(_X, [], []).
delete(X, [Y|Ys], [Y|Zs]) :-
   dif(X, Y),
   delete(X, Ys, Zs).
delete(X, [X|Ys], Zs) :-
   delete(X, Ys, Zs).

This definition can now be used in many ways. Like

?- delete(X,Xs,[1,2,3]).
   Xs = [1,2,3], dif(X,3), dif(X,2), dif(X,1)
;  Xs = [1,2,3,X], dif(X,3), dif(X,2), dif(X,1)
;  Xs = [1,2,3,X,X], dif(X,3), dif(X,2), dif(X,1)
; ... .

Note that there are now infinitely many answers!

Answer 2

This answer is inspired by the logically-pure code that @false presented in his answer.

Let's use the meta-predicate tfilter/3 and reified term inequality dif/3 and simply write:

?- Vs0 = [1,2,3,4], tfilter(dif(4),Vs0,Vs).
Vs0 = [1,2,3,4],
Vs  = [1,2,3  ].                      % succeeds deterministically

?- Vs0 = [1,2,3,4,2,3,4], tfilter(dif(2),Vs0,Vs).
Vs0 = [1,2,3,4,2,3,4],
Vs  = [1,  3,4,  3,4].                % succeeds deterministically

The implementation of delete/3 boils down to:

delete(E,Vs0,Vs) :-
   tfilter(dif(E),Vs0,Vs).

Like @false's code this implementation is monotone, which makes the predicate versatile and enables you to get logically sound answers even when working with non-ground terms.

Finally, let's have a quite general query and look at all answers:

?- Vs0 = [X,Y,Z], delete(E,Vs0,Vs).
Vs0 = [X,Y,Z],     E=X ,     E=Y ,     E=Z , Vs = [     ] ;
Vs0 = [X,Y,Z],     E=X ,     E=Y , dif(E,Z), Vs = [    Z] ;
Vs0 = [X,Y,Z],     E=X , dif(E,Y),     E=Z , Vs = [  Y  ] ;
Vs0 = [X,Y,Z],     E=X , dif(E,Y), dif(E,Z), Vs = [  Y,Z] ;
Vs0 = [X,Y,Z], dif(E,X),     E=Y ,     E=Z , Vs = [X    ] ;
Vs0 = [X,Y,Z], dif(E,X),     E=Y , dif(E,Z), Vs = [X,  Z] ;
Vs0 = [X,Y,Z], dif(E,X), dif(E,Y),     E=Z , Vs = [X,Y  ] ;
Vs0 = [X,Y,Z], dif(E,X), dif(E,Y), dif(E,Z), Vs = [X,Y,Z].

Answer 3

One cryptic way to get rid of cryptic variable names is to use numbervars/3, for example,

?- length(X, 3).
X = [_G2019, _G2022, _G2025].

?- length(X, 3), numbervars(X, 0, _).
X = [A, B, C].

Now to your delete/3. Apart from other minor problems, like unusual order of the arguments, unusual order of the clauses, etc, you have one major problem: in the second clause, you put a new, anonymous variable where the element of the original list should have been.

delete(X, [Y|Ys], [Y|Zs]) :- delete(X, Ys, Zs).

With this in the second clause, it sort of works:

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

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

There are further problems with your implementation. You can look at the implementation of the same predicate in library(lists) from SWI-Prolog: read the documentation, too!