首页 文章

为什么这个Prolog谓词有效？

提问于
浏览 次
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).

这个想法是等于（[1,2,3]，[1,2,1,3]）应该返回true . 但是，根据上面的定义，我期望发生的事情如下：

  • equals（[1,2,3]，[1,2,1,3]）匹配第一个规则，并调用equals（[2,3]，[2,1,3]]） .

  • equals（[2,3]，[2,1,3]]）匹配第二个规则并调用contains（[2,3]，[2,1,3]），contains（[2,1,3] ，[2,3]） .

  • 包含（[2,3]，[2,1,3]）失败，等于返回No.

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

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

prolog

2 回答

  • 2

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

    看看第一步，第1步 .

    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的一个非常基础的部分 . 我很惊讶你在没有理解的情况下走到这一步 .

    回复于
  • 3

    您的代码非常奇怪，但我建议您使用跟踪谓词进行测试 . 这是一个例子：

    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
    回复于

相关问题