2

我知道这个问题已经被问过了，但我只想问一下我的具体实现。我编写这个函数只是为了练习 Prolog 并更好地理解 Prolog。这是我所拥有的：

del(Ele, [H], [H]) :- Ele \= H.
del(Ele, [H|T], [H|New]) :-
    Ele \= H,
    del(Ele, T, [New]).

New这个想法是，如果我要删除的元素不等于，我会将一个元素添加到一个名为的新列表中H。据我了解，我的代码无法正常工作，因为我的代码在到达 where 元素时停止Ele \= H。任何想法如何解决这一问题？

例如，del(5, [3,4,5,6,7], X)将返回 false。

另外，有没有更好的解决方案？将列表中的每个元素继续添加到新列表似乎是一个糟糕的解决方案，因为这对于大列表来说会很慢。我宁愿只保留当前列表中的元素，找到匹配Ele的元素，删除该元素，然后返回列表。

4

2 回答 2

3

您已经描述了一些del/3应该成立的情况。但这些只是Ele与列表中的元素不相等/不可统一的情况。有几样东西不见了：

空列表呢？

什么，如果Ele等于元素？

因此，您需要添加更多子句。（由于冗余原因，稍后您可能还会删除一些）。

如果您使用的是 SWI、B、SICStus 或 YAP，请考虑使用dif/2. (\=)/2

dif/2这就是在这种情况下如此有用的原因。有了dif/2你就会有一个纯粹的单调程序。你可以直接试一试：

?- 德尔（5，[3,4,5,6,7]，X）。
假的。

你有同样的问题。让我重申一下问题所在：您期望某些东西应该成立，但事实并非如此。所以这种关系定义得太狭隘了。如果我概括查询，我可能会得到更好的答案。尝试del(E, [3,4,5,6,7], X).但再次相同false。所以我会尝试一个更一般的查询：

?- 德尔（E，Xs，Ys）。
Xs = Ys, Ys = [_G1076],
差异（E，_G1076）...

对我来说看起来很完美！也许另一个答案：

?- 德尔（E，Xs，Ys）。
Xs = Ys, Ys = [_G1076],
差异（E，_G1076）；
Xs = [_G1133, _G1136],
Ys = [_G1133|_G1136]，
差异（E，_G1136），
差异（E，_G1133） ...

现在我们得到了一个错误的答案。我将对其进行一些实例化以使其更具可读性：

?- del(e, [a,b], Ys)。
Ys = [a|b] ;
错误的。

这个答案显然是不正确的，因为[a|b]它不是一个列表。而且，这可能是最小的错误答案......

我想通过这一点向您展示的是，您通常可以在不逐步进行的情况下找到问题。一旦获得更复杂的控制流（如并发），逐步调试甚至在命令式语言中都不起作用；它在 Prolog 中根本无法扩展。

于 2013-03-19T21:06:43.393 回答
2

让我们追踪：

?- trace, del(5, [3,4,5,6,7], X).
   Call: (7) del(5, [3, 4, 5, 6, 7], _G218) ? creep
   Call: (8) 5\=3 ? creep
   Exit: (8) 5\=3 ? creep
   Call: (8) del(5, [4, 5, 6, 7], [_G344]) ? creep
   Call: (9) 5\=4 ? creep
   Exit: (9) 5\=4 ? creep
   Call: (9) del(5, [5, 6, 7], [[]]) ? creep
   Fail: (9) del(5, [5, 6, 7], [[]]) ? creep
   Fail: (8) del(5, [4, 5, 6, 7], [_G344]) ? creep
   Fail: (7) del(5, [3, 4, 5, 6, 7], _G218) ? creep
false.

所以你可以看到你的代码在到达 5 时实际上是失败的，因为它5 \= 5是错误的。您的第一条规则永远不会匹配，因为列表中有多个项目。第二条规则在找到后“正确”重复出现5 \= 3，5 \= 4但由于您的任何规则都没有5 = 5案例，因此失败发生在那里。

顺便说一下，让我们看看当列表中没有出现 5 时会发生什么：

?- trace, del(5, [3,4,6,7], X).
   Call: (7) del(5, [3, 4, 6, 7], _G350) ? creep
   Call: (8) 5\=3 ? creep
   Exit: (8) 5\=3 ? creep
   Call: (8) del(5, [4, 6, 7], [_G473]) ? creep
   Call: (9) 5\=4 ? creep
   Exit: (9) 5\=4 ? creep
   Call: (9) del(5, [6, 7], [[]]) ? creep
   Fail: (9) del(5, [6, 7], [[]]) ? creep
   Fail: (8) del(5, [4, 6, 7], [_G473]) ? creep
   Fail: (7) del(5, [3, 4, 6, 7], _G350) ? creep
false.

这就是为什么我之前说“正确”的原因：您的归纳案例也不正确。一方面，你有，del(Ele, T, [New])但在上面你有del(Ele, [H|T], [H|New])，所以你要在右边多花时间展开列表（这就是我们的跟踪[[]]在其中的原因）。但是@false 遇到了更大的问题，即您根本不会考虑实际找到要删除的内容的情况。:) 您也不处理列表为空的情况。

不幸的是，遍历数据结构并查看每个项目将是 O(N)。另一个不幸的事实是，在函数式和声明式语言（缺少“可赋值”的语言）中，修改列表意味着复制列表的至少一部分。在 Prolog 中有更有效的方法来解决这个问题（例如，您可以使用差异列表）但它们将共享相同的基本问题。Prolog 效率是一个相当大的话题。我会告诉你不要太担心它，但它有办法很快成为你的关注点。但在这种情况下，不，没有真正更有效的方法使用破坏性更新。

于 2013-03-19T21:14:47.193 回答