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

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].