在Prolog中丢弃

Question

我正在努力理解Prolog中的递归,但它肯定与其他语言中的递归不同(我使用PHP,Java和C,只是说).

所以,是的,我一直在阅读有关它的所有教程,但我仍然没有得到具体的,相当复杂的案例.

例如,为了获得列表中元素的出现次数,我们有:

occurrence([], _, 0).
occurrence([H | T], H, N) :- !, occurrence(T, H, N1), N is N1 + 1.
occurrence([_ | T], H, N) :- occurrence(T, H, N).

可以使用以下方式调用:

occurrence([1,4,9,1,2],1,R).

它应该导致:

?- R=2

现在,为什么第3行甚至会发生？它在做什么？我写了这个程序而没有看到答案,我在第二行之后完成了.当然,它不会工作.

另一方面,为什么在那里发生"切割"？比如,我一直试图在每次通话后打印出结果,我只是越来越困惑.

Answer 1

第3行处理列表头部与您要查找的项目不匹配的情况.假设你已经传递了第一个元素,你最终会在递归调用occurrence/3中看到:

occurrence([4,9,1,2], 1, 1).

哪条规则匹配？规则1不匹配,因为我们没有空列表.规则2不匹配,因为4\= 1.第三个规则适用于这种情况,它只是说,你没有在这里找到1,所以请继续查看列表的尾部([9,1,2] ]).

剪切是因为第三个规则将匹配任何列表.切割会让您选择.有什么选择？您在列表的头部和您正在寻找的元素中具有相同的值,因为这是必须匹配的模式才能输入此规则的主体.如果省略切割,则在将列表的头部与所寻找的元素统一后,您将允许选择点,这意味着您将获得多个具有R = 2的统一的解,然后R = 1,然后R这是因为每个1也可以像第三个规则一样被忽略.

你可以通过使第三条规则成为条件来摆脱削减:

occurrence([H1|T], H2, N) :- H1 \= H2, occurrence(T, H2, N).

您还可以使用条件表达式并将一个规则组合为规则2和3:

occurrence([H|T], S, N) :- 
  (H = S 
     -> occurrence(T, S, N1), N is N1 + 1 
      ; occurrence(T, S, N)
  ).

这可能会更有效率; 条件表达式不会像附加规则体那样创建选择点.Prolog不是通灵的,因此它无法检测到规则是相互排斥的.我更喜欢具有多个可读性规则的逻辑公式.

希望这可以帮助.