logo标签列表

在Prolog中删除第一个出现的元素

listprolog
3
我是一个有用的助手，可以帮您进行文本翻译。
我正在尝试从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.
你所说的“第一次出现”，是指与你正在搜索的项相等的第一个术语或者与你正在搜索的项统一的第一个术语？当列表包含非基础术语时，这种澄清变得相关，并有助于选择解决问题的最佳答案。 - Paulo Moura
2个回答
4
@chamini2提供的实现是不纯的，当使用非ground项时可能会变得逻辑上不正确。考虑以下两个查询：
？- 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。%缺少一个解决方案！ 拯救了这个问题！通过将\=/2替换为dif/2，代码变得逻辑纯粹：
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。
好多了！ OP 给出的其他查询也可以像应该的那样工作：
?- 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的上述实现在能够确定性地成功时留下了一个无用的选择点。让我们消除这种低效率，同时保持！

使用if_/3和具有显式等价性的(=)/3（又名equal_truth/3），如@false在问题“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.
2
尝试在第二次尝试中添加一个东西。
remove_first_X(X,[X|Xs],Xs).
remove_first_X(X,[Y|Xs],[Y|Ys]) :- 
    X \= Y,
    remove_first_X(X,Xs,Ys).

在您运行的示例中发生的情况是：
  • 对于 X = [1, 2, 1, 0]，它只尝试了remove_first_X的第一个子句。
  • 接下来的元素是通过进入第二个子句再次返回到第一个子句实现的，您可以看到没有任何禁止X=Y的东西，这是您应该确保的。
1
我过于假设模式匹配了.. 我应该多读一些资料。谢谢!!! - jamprad
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接