list - 删除 Prolog 中元素的第一次出现

Question

我正在尝试从 Prolog 中的列表中删除第一次出现的元素。

我的代码:

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

不起作用:

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

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

求助! :-)

另一个尝试更接近:

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

但在第一次出现后删除 X:

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

Answer 1

@chamini2 给出的实现不纯，并且在使用非基础术语时可能变得逻辑上不合理。考虑以下两个查询:

?- 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).

让我们再次运行上面的查询，这次改进了实现:

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

---

编辑 2015-05-07

remove_1st_x/3 的上述实现在确定性成功时留下了一个无用的选择点。让我们在保留 logical-purity 的同时摆脱这种低效率!

使用 if_/3 和具体化的等式 (=)/3(又名 equal_truth/3)，由 @false 中的 an answer 定义到问题“Prolog union for A U B U C”，我们可以这样定义remove_1st_x/3:

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

让我们再次运行上面的查询!请注意，所有成功都是确定性的。

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