prolog - 如果存在剪切 '!'，执行有何不同？

Question

counter([],[]).
counter([H|T],[[H,C1]|R]) :- counter(T,[[H,C]|R]),!, C1 is C+1.
counter([H|T],[[H,1]|R]) :- counter(T,R).

“!”的作用是什么？因为我在上面和下面的代码中都得到了相同的输入输出？

 counter([],[]).
 counter([H|T],[[H,C1]|R]) :- counter(T,[[H,C]|R]),C1 is C+1.
 counter([H|T],[[H,1]|R]) :- counter(T,R).

我是 Prolog 的新手。

Answer 1

What is the effect of the "!"

切割修剪了搜索空间。也就是说，在其他纯粹和单调的程序中，切割将删除一些解决方案或答案。只要这些都是多余的就好了。这听起来很天真和有用，不是吗？我们来看一下!

以免我忘记，使用 [E,Nr]表示成对是相当不寻常的，最好使用成对 E-Nr .

我们现在将比较 counter_cut/2和 counter_sans/2 .

| ?- counter_cut([a,a],Xs).
     Xs = [[a,2]].

| ?- counter_sans([a,a],Xs).
     Xs = [[a, 2]]
  ;  Xs = [[a, 1], [a, 1]].     % <<< surprise !!!

所以切割版本的解决方案更少。似乎是解决方案 counter_cut/2保留是正确的。在这种非常特殊的情况下。它总是会选择正确的吗？我将尝试一个最低限度的更一般的查询:

| ?- counter_cut([a,B],Xs).
     B = a,
     Xs = [[a, 2]].

| ?- counter_sans([a,B],Xs).
     B = a,
     Xs = [[a, 2]]
  ;  Xs = [[a, 1], [B, 1]].

再次，_sans更健谈，这一次，它甚至更正确；最后一个答案包括 B = b .换句话说，

| ?- counter_cut([a,B], Xs), B = b.
     fails.              % incomplete !

| ?- counter_sans([a,B], Xs), B = b.
     B = b,
     Xs = [[a,1],[b,1]].

所以有时 _cut版本更好，有时_sans .或者更直接地说:两者都错了，但是 _sans -version 至少包括所有解决方案。

这是一个“净化”版本，它只是将最后一条规则重写为两种不同的情况:一种用于列表的末尾，另一种用于更远的不同元素。

counter_pure([],[]).
counter_pure([H|T],[[H,C1]|R]) :- counter_pure(T,[[H,C]|R]), C1 is C+1.
counter_pure([H],[[H,1]]).
counter_pure([H,D|T],[[H,1]|R]) :- dif(H,D), counter_pure([D|T],R).

从效率的角度来看，这不是太出名。

下面是一个有理树统一系统的效率测试用例:

?- Es = [e|Es], counter(Es, Dict).
resource_error(stack).

相反，实现应该平滑循环，至少直到这个宇宙结束。严格来说，该查询必须产生资源错误，但前提是它计数到一个比 10^100000000 大得多的数字之后。 .