1

我有以下代码： 请记住，虽然此代码适用于列表，但这些列表表示集合，因此 [1,1,2,2,3,3] 和 [1,2,3] 应该是等效的。

%contains(L1, L2), returns true if L1 contains L2
contains(_, []).
contains(L1, [Head|Tail]) :- member(Head, L1), contains(L1, Tail).
%equals(L1, L2), returns true if L1 is equal to L2
equals([X|L1],[X|L2]) :- equals(L1, L2).
equals(L1, L2) :- contains(L1, L2), contains(L2, L1).

这个想法是 equals([1,2,3],[1,2,1,3]) 应该返回 true。但是，根据上述定义，我期望发生的情况如下：

  1. equals([1,2,3],[1,2,1,3]) 匹配第一条规则，并调用 equals([2,3],[2,1,3]])。
  2. equals([2,3],[2,1,3]]) 匹配第二条规则并调用 contains([2,3], [2,1,3]), contains([2,1,3], [2,3]）。
  3. contains([2,3], [2,1,3]) 失败，equals 返回 No。

然而它仍然有效。其他试图混淆它的尝试也是如此。有人可以向我解释一下吗？

（Prolog 实现：SWI-Prolog 版本 2.7.12）

4

2 回答 2

3

Prolog 使用一种称为“回溯”的技术。

看看第一步，你的第一步。

Prolog 有两个可以在这里使用的规则，如果它使用你在解释中选择的规则，它总是会失败。但是一旦失败，Prolog 将回溯并尝试替代规则：

等于([1,2,3],[1,2,1,3]) :- 包含([1,2,3],[1,2,1,3]), 包含([1,2, 1,3],[1,2,3])

通过在找到错误答案后反复回溯，最终 Prolog 找到了一个正确的解决方案，因此它知道答案是正确的。

如果尝试了所有可能的应用规则的方法，但没有找到正确的答案，那么答案一定是错误的。

这是 Prolog 的一个非常基本的部分。我很惊讶你在不理解的情况下走到了这一步。

于 2009-06-29T22:23:52.373 回答
2

您的代码很奇怪，但是我可以建议您使用跟踪谓词进行测试。这是示例：

4 ?- trace([equals,contains]).
%         equals/2: [call, redo, exit, fail]
%         contains/2: [call, redo, exit, fail]
true.

[debug] 5 ?- equals([1,2,3],[1,2,1,3]).
 T Call: (7) equals([1, 2, 3], [1, 2, 1, 3])
 T Call: (8) equals([2, 3], [2, 1, 3])
 T Call: (9) equals([3], [1, 3])
 T Call: (10) contains([3], [1, 3])
 T Fail: (10) contains([3], [1, 3])
 T Fail: (9) equals([3], [1, 3])
 T Redo: (8) equals([2, 3], [2, 1, 3])
 T Call: (9) contains([2, 3], [2, 1, 3])
 T Call: (10) contains([2, 3], [1, 3])
 T Fail: (10) contains([2, 3], [1, 3])
 T Fail: (9) contains([2, 3], [2, 1, 3])
 T Fail: (8) equals([2, 3], [2, 1, 3])
 T Redo: (7) equals([1, 2, 3], [1, 2, 1, 3])
 T Call: (8) contains([1, 2, 3], [1, 2, 1, 3])
 T Call: (9) contains([1, 2, 3], [2, 1, 3])
 T Call: (10) contains([1, 2, 3], [1, 3])
 T Call: (11) contains([1, 2, 3], [3])
 T Call: (12) contains([1, 2, 3], [])
 T Exit: (12) contains([1, 2, 3], [])
 T Exit: (11) contains([1, 2, 3], [3])
 T Exit: (10) contains([1, 2, 3], [1, 3])
 T Exit: (9) contains([1, 2, 3], [2, 1, 3])
 T Exit: (8) contains([1, 2, 3], [1, 2, 1, 3])
 T Call: (8) contains([1, 2, 1, 3], [1, 2, 3])
 T Call: (9) contains([1, 2, 1, 3], [2, 3])
 T Call: (10) contains([1, 2, 1, 3], [3])
 T Call: (11) contains([1, 2, 1, 3], [])
 T Exit: (11) contains([1, 2, 1, 3], [])
 T Exit: (10) contains([1, 2, 1, 3], [3])
 T Exit: (9) contains([1, 2, 1, 3], [2, 3])
 T Exit: (8) contains([1, 2, 1, 3], [1, 2, 3])
 T Exit: (7) equals([1, 2, 3], [1, 2, 1, 3])
true
于 2009-06-30T20:58:50.883 回答