3

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

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 中，用这些修复替换第二个术语似乎总是在我考虑的测试用例上返回相同的答案。我在这里想念什么？

4

1 回答 1

5

你的例子是一个完美的例子来说明为什么在这里使用 cut从来都不是一个好主意。

只有当第一个和第二个参数都被充分实例化时，使用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].

在结尾处使用 cutrm(A,[A|L],R) :- rm(A,L,R), !.更糟糕：首先，到目前为止我们所有的假设都必须成立，然后第三个参数不能被实例化。否则我们会得到额外的错误解决方案。

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

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

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

用户：a从列表中删除时，[a]我们会得到什么？

序言：什么都没有，没有，nada。

用户：但我不能只拥有而不是没有[a]吗？请！

Prolog：好的，我让步。

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

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

有没有希望摆脱所有这些精美的印刷品？幸运的是，对于SICStus |使用if_/3from有一条出路。斯威。下载它并说：library(reif)

:- 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，列表保持不变。

于 2017-04-22T22:14:14.420 回答