Prolog中Cut运算符的交换性

Question

我正在学习Prolog,在我正在阅读的一个例子中给出了如何正确使用切割算子的例子.请考虑以下函数从列表中删除特定值的所有元素.

rm(_,[],[]).
rm(A,[A|L],R) :- rm(A,L,R).
rm(A,[B|L],[B|R]) :- rm(A,L,R).

由于回溯,这不是函数的正确定义,并且函数将返回从删除特定值的某些元素获得的列表的所有子列表,但不一定全部返回.我正在阅读的笔记说,解决这个问题的正确方法是用线替换第二行

rm(A,[A|L],R) :- !, rm(A,L,R)

但那取代了这条线

rm(A,[A|L],R) :- rm(A,L,R), !

是不正确的.我不确定为什么第二个例子是修复函数​​的错误方法.在swipl中,用这些修复替换第二个术语似乎总是在我考虑的测试用例中返回相同的答案.我在这里错过了什么？

Answer 1

您的示例是一个很好的例子来说明为什么在这里使用切割从来都不是一个好主意.

rm(A,[A|L],R) :- !, rm(A,L,R).如果第一个和第二个参数都被充分实例化,那么使用才有意义.但是如果它们没有得到充分的实例化,那么你会得到一个不完整的答案:

?- rm(X, [a], R).
   X = a, R = [].       % incomplete

这显然错过一个答案,因为它限制X为a只.但如果X是其他任何东西,我们会得到不同的结果,即:

?- X = b, rm(X,[a],R).
R = [a].

使用最后的切割rm(A,[A|L],R) :- rm(A,L,R), !.更糟糕:首先,到目前为止我们所有的假设都必须保持,然后另外第三个参数不能被实例化.否则我们会得到其他不正确的解

?- rm(a,[a],R).
R = [].

?- rm(a,[a],[a]).
true                 % incorrect

回想一下我们在这里问的问题:

用户:a从列表中删除[a]我们得到了什么？

Prolog:没什么,没有,nada.

用户:但我不能只有而不是[a]吗？请!

Prolog:好的,我放弃了.

这不是您想要实施会计系统的方式.

所以削减的两种用途都很糟糕.但第二个显然更糟,因为它有更多的前提条件要记住,而且效率低下.另一方面,在某些情况下您可以使用这些谓词.但通常很难记住何时这是安全的.因此,这种削减是永久的错误来源.

有没有希望摆脱所有这些细则？幸运的是,有一个出路使用if_/3来自library(reif)于SICStus | SWI.下载并说:

:- use_module(reif).

rm(_,[],[]).
rm(A,[X|Xs], Ys0) :-
   if_(A = X, Ys0 = Ys, Ys0 = [X|Ys]),
   rm(A, Xs, Ys).

该计划效率相当,但没有任何上述缺陷:

?- rm(X, [a], R).
   X = a,
   R = []
;  R = [a],
   dif(X, a).

注意第二个新答案!它表示,对于所有X不同的a,列表保持不变.