Prolog中切割算子的交换性

Question

我目前正在学习 Prolog，在我正在阅读的其中一篇笔记中给出了如何正确使用 cut 运算符的示例。考虑以下函数从列表中删除特定值的所有元素。

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

由于回溯，这不是函数的正确定义，函数将 return 从删除 a 的 some 元素中获得的列表的所有子列表特定值，但不一定全部。我正在阅读的笔记说解决这个问题的正确方法是用行

替换第二行

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

但是将行替换为

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

不正确。我不确定为什么第二个示例是修复该功能的错误方法。在 swipl 中，用这些修复替换第二项似乎总是 return 与我考虑的测试用例的相同答案。我在这里错过了什么？

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), !. 中的 cut 更糟糕：首先，到目前为止我们所有的假设都必须成立，然后此外第三个参数不能被实例化。否则我们会得到更多不正确的解决方案。

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

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

回想一下我们在这里问的是什么：

User: When removing a from the list [a] what do we get?

Prolog: Nothing, nil, nada.

User: But can't I have instead of nothing just [a]? Please!

Prolog: OK, I give in.

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

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

有希望摆脱所有这些细则吗？幸运的是，有一种方法可以使用 if_/3 from library(reif) for 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).

注意第二个新答案！它说对于所有不同于 a 的 X，列表保持不变。

Prolog中切割算子的交换性

Commutativity of Cut Operator in Prolog

prolog

prolog-cut