remove first occurrence of an element in Prolog

Question

I'm trying to remove the first occurrence of an element from a list in Prolog.

My code:

remove_first_X(X,[X|Xs],Xs). %remove X
remove_first_X(X,[Y|Xs],[Y|Xs]) :-
   remove_first_X(X,Xs,Xs).

Doesn't work:

?- remove_first_X(1,[1,2,3],[2,3]).
true.

?- remove_first_X(1,[2,1,3],[2,3]).
false.

Please help! :-)

Another attempt is closer:

remove_first_X(X,[X|Xs],Xs).
remove_first_X(X,[Y|Xs],[Y|Ys]) :-
   remove_first_X(X,Xs,Ys).

But removes X after its first occurrence:

?- remove_first_X(1,X,[2,1,0]).
X = [1, 2, 1, 0] ;
X = [2, 1, 1, 0] ;
X = [2, 1, 1, 0] ;
X = [2, 1, 0, 1] ;
false.

By first occurrence, you mean the first term that's equal to the term you're searching for OR the first term that unifies with the term you're searching for? This clarification becomes relevant when the list contains non-ground terms and helps in selecting the best answer to the problem you're trying to solve. — Paulo Moura

repeat repeat · Accepted Answer · 2015-05-04T15:21:54

The implementation given by @chamini2 is impure, and can become logically unsound when working with non-ground terms. Consider the following two queries:

?- E=1, remove_first_X(E,Xs,[2,1,0]).
E = 1, Xs = [1,2,1,0] ;
E = 1, Xs = [2,1,1,0] ;
false.

?- remove_first_X(E,Xs,[2,1,0]), E=1.
E = 1, Xs = [1,2,1,0] ;
false.                                    % one solution is missing!

prolog-dif to the rescue! By replacing (\=)/2 with dif/2, the code gets logically pure:

remove_1st_x(X,[X|Xs],Xs).
remove_1st_x(X,[Y|Xs],[Y|Ys]) :- 
    dif(X,Y),
    remove_1st_x(X,Xs,Ys).

Let's run above queries again, this time with the improved implementation:

?- E=1, remove_1st_x(E,Xs,[2,1,0]).
E = 1, Xs = [1,2,1,0] ;
E = 1, Xs = [2,1,1,0] ;
false.

?- remove_1st_x(E,Xs,[2,1,0]), E=1.
E = 1, Xs = [1,2,1,0] ;
E = 1, Xs = [2,1,1,0] ;
false.

That's better! And the other queries given by the OP also work like they should:

?- remove_1st_x(1,[1,2,3],[2,3]).
true ;
false.

?- remove_1st_x(1,[2,1,3],[2,3]).
true ;
false.

?- remove_1st_x(1,X,[2,1,0]).
X = [1,2,1,0] ;
X = [2,1,1,0] ;
false.

Edit 2015-05-07

Above implementation of remove_1st_x/3 leaves behind a useless choice-point when it could succeed deterministically. Let's get rid of that inefficiency while preserving logical-purity!

Using if_/3 and reified equality (=)/3 (a.k.a. equal_truth/3), as defined by @false in an answer to question "Prolog union for A U B U C", we can define remove_1st_x/3 like this:

remove_1st_x(E,[X|Xs],Ys) :-
   if_(X=E, Xs=Ys, (Ys=[X|Ys0],remove_1st_x(E,Xs,Ys0))).

Let's run above queries again! Note that all succeed deterministically.

?- remove_1st_x(1,[2,1,3],Ys).
Ys = [2,3].

?- remove_1st_x(1,[2,1,3],[2,3]).
true.

?- remove_1st_x(1,[1,2,3],[2,3]).
true.

remove first occurrence of an element in Prolog

2 Answers

Edit 2015-05-07