简单的Prolog从列表中删除

Question

我正在尝试在Prolog中执行删除列表元素的练习。下面是我的代码：

deleteall([],X,[]).
deleteall([H|T],X,Result) :- 
    H==X,
    deleteall(T,X,Result).
deleteall([H|T],X,[H|Result]) :- deleteall(T,X,Result).

当我进行测试时，首先得到了一个好的答案（即去除所有X后的答案）。但是然后回溯会给我提供所有其他的列表变体，其中一些或没有X的实例被删除。

为什么会这样呢？为什么H==X的情况会落入最后一个子句？

- interstar

---

感谢interstar的提问，关于如何删除，我也在进行同样的练习。在prolog中，我以前没有使用过==运算符。我已经理解了你的解决方案。我们可以通过将第一句中的X替换为_来避免单例变量，并且应该在第二和第三个情况下加上!运算符以改进代码。 - Yone

Answer 1

当您使用(==)/2进行比较时，您需要在第三条规则中使用相反的符号，即(\==)/2。另一方面，这样的定义不再是纯关系。为了看清这一点，请考虑deleteall([X],Y,Zs)，X=Y。 对于一个纯关系，我们需要使用(=)/2和dif/2。许多Prolog，如SWI、YAP、B、SICStus都提供dif/2。

deleteall([],X,[]).
deleteall([H|T],X,Result) :- 
    H=X,
    deleteall(T,X,Result).
deleteall([H|T],X,[H|Result]) :-
    dif(H,X),
    deleteall(T,X,Result).

请看deleteall([X,Y],Z,Xs)的答案！

编辑（四年后）：

更加高效，但在相同的纯粹基础上，可以使用if_/3和(=)/3来编写：

deleteall([], _X, []).
deleteall([E|Es], X, Ys0) :-
   if_( E = X, Ys0 = Ys, Ys0 = [E|Ys] ),
   deleteall(Es, X, Ys).

- false

---

@Dunes：请阅读链接以了解它是等于 /3 而不是等于 /2！ - false

你的 = 谓词没有三个参数。它们都是以 A = B 的形式出现的。也许你应该在回答中提供 (=)/3 的文档链接以及它的作用。 - Dunes

这里确切地有一个链接来文档化它！就是调用if_/3它。对(=)/3的确切调用将是 call(A = B, T)，其结果为 call(=(A,B,T))。 - false

啊，我明白了。然而，=/3不是ISO的一部分。我认为这是Sicstus特有的。就像if/3一样，我最初没有意识到。虽然SWI似乎有一个兼容模块，但它并没有按照你所建议的实现。https://www.swi-prolog.org/pldoc/doc/_SWI_/library/dialect/sicstus.pl?show=src#if/3 对于更高效的答案，最好说明使用哪种方言。 - Dunes

这里应该使用 if_/3 而不是 if/3，并且没有涉及方言。所有内容都在上面的链接中定义！请仔细阅读。而且 SWI 绝对不是 ISO 的良好参考。 - false

Answer 2

最后一条规则表示，从列表中删除X时，头元素可以保留（与其值无关）。Prolog可以在任何时候使用这个规则，独立于前面的条件是否为真。如果另一个规则失败，或者您指示它这样做（例如通过在顶层发出;以获取下一个解决方案），Prolog可以回溯到此规则。如果添加了一个条件，即头元素不等于X，则应该能够工作。请注意保留HTML标签。

- Aasmund Eldhuset

---

Prolog子句按从左到右，自上而下的顺序执行，尽管解释器可能在失败时回溯到后续子句。 - Fred Foo

@larsmans：我删除了第一句话。中间的那句可能不完全正确，你可以随意编辑它。 - Aasmund Eldhuset

@larsmans：谢谢。至少，我最初的句子开头是正确的：“我已经有一段时间没有做过任何Prolog了”;-) - Aasmund Eldhuset

好的。谢谢您的纠正。不过实际上我不太确定您想表达什么。如果顺序确实很重要，那么在X == H的情况下我们为什么会执行最后一个子句呢？第二个子句不是已经捕获了这种情况吗？ - interstar

也许我不理解“回溯(backtracking)”的含义。我以为它会跟踪所有备选的正确解决方案。实际上，它只是指“在匹配一个子句后尝试匹配下一个”吗？ - interstar