3

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.
false
  • 10,264
  • 13
  • 101
  • 209
jamprad
  • 55
  • 6
  • 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 May 04 '15 at 15:30

2 Answers2

4

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.
Community
  • 1
  • 1
repeat
  • 18,496
  • 4
  • 54
  • 166
2

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.
chamini2
  • 2,820
  • 2
  • 24
  • 37