CODEWITHSUNDEEP
listprolog
jamprad
jamprad

Reputation: 55

remove first occurrence of an element in Prolog

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.

Upvotes: 3

Views: 2356

Answers (2)

repeat
repeat

Reputation: 18726

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!

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 !

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.

Upvotes: 4

chamini2
chamini2

Reputation: 2918

try the adding one thing to the second attempt

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

What happen in the example you ran was that

  • For X = [1, 2, 1, 0] it simply tried the first clause of remove_first_X
  • The next element was by going in the second clause and again to the first one, you can see that nothing prohibits that X = Y, that's something you should make sure of.

Upvotes: 2

Related Questions