Prolog：如何在有或没有剪枝运算符的情况下避免冗余的选择点（非确定性）。

Question

首先，我已经阅读了关于在Prolog中使用cuts的所有其他帖子，并且确实看到了与使用它们相关的问题。然而，对于我来说仍然存在一些不清楚的地方，我想一劳永逸地解决这个问题。

在下面的简单示例中，我们通过递归迭代列表并检查每个第二个元素是否等于1。在这样做时，递归过程可能会以以下任一基本情况之一结束：空列表或剩余一个元素的列表。

base([]).
base([_]).
base([_,H|T]) :- H =:= 1, base(T).

当执行时：

?- time(base([1])).
   % 0 inferences, 0.000 CPU in 0.000 seconds (74% CPU, 0 Lips)
   true ;
   % 2 inferences, 0.000 CPU in 0.000 seconds (83% CPU, 99502 Lips)
   false.

?- time(base([3,1,3])).
   % 2 inferences, 0.000 CPU in 0.000 seconds (79% CPU, 304044 Lips)
   true ;
   % 2 inferences, 0.000 CPU in 0.000 seconds (84% CPU, 122632 Lips)
   false.

在这种情况下，我总是在第二个基本情况（即表示列表中仅剩一个元素的情况）中使用显式的剪枝运算符，如下所示，以消除冗余的选择点。

base([]).
base([_]) :- !.
base([_,H|T]) :- H =:= 1, base(T).

现在我们得到：

?- time(base([1])).
   % 1 inferences, 0.000 CPU in 0.000 seconds (81% CPU, 49419 Lips)
   true.

?- time(base([3,1,3])).
   % 3 inferences, 0.000 CPU in 0.000 seconds (83% CPU, 388500 Lips)
   true.

我了解这种截断行为是特定于规则位置的，并且可以被视为不良实践。

然而，接下来我们可以将情况重新定位如下：

base([_,H|T]) :- H =:= 1, base(T).
base([_]).
base([]).

这也可以去除冗余的选择点而不使用cut，但是当然，我们只会将选择点转移到带有偶数位数字列表的查询中，例如以下内容：

?- time(base([3,1])).
% 2 inferences, 0.000 CPU in 0.000 seconds (82% CPU, 99157 Lips)
true ;
% 2 inferences, 0.000 CPU in 0.000 seconds (85% CPU, 96632 Lips)
false.

这显然也不是一个解决方案。但我们可以通过以下方式对规则进行调整，使其更具有可行性：

base([_,H|T]) :- H =:= 1, base(T), !.
base([_]).
base([]).

这实际上将不留下任何选择点。看一些查询：

?- time(base([3])).
% 1 inferences, 0.000 CPU in 0.000 seconds (81% CPU, 157679 Lips)
true.

?- time(base([3,1])).
% 3 inferences, 0.000 CPU in 0.000 seconds (83% CPU, 138447 Lips)
true.

?- time(base([3,1,3])).
% 3 inferences, 0.000 CPU in 0.000 seconds (82% CPU, 393649 Lips)
true.

然而，需要再强调一遍，这种切割行为之所以能正确地运作，是因为规则的顺序。如果有人将基本情况重新排列回如下原始形式：

base([]).
base([_]).
base([_,H|T]) :- H =:= 1, base(T), !.

即使这样，我们仍会得到不想要的行为：

?- time(base([1])).
   % 0 inferences, 0.000 CPU in 0.000 seconds (83% CPU, 0 Lips)
   true ;
   % 2 inferences, 0.000 CPU in 0.000 seconds (84% CPU, 119546 Lips)
   false.

在这些情况下，我总是在第二个基本情况中使用单个剪切符号，因为只有我一个人经过我的代码，而且我已经习惯了这种用法。然而，在我的另一个SO帖子的回答中，有人告诉我这不是推荐使用剪切符号的方式，我应该尽量避免使用它。

这就引出了我的双重问题：

- 如果一个剪切符号，无论其出现在规则的位置如何，都会改变行为但不改变解决方案（就像上面的例子一样），那么它是否仍被认为是不良实践？ - 如果我想要摆脱像上面例子中典型的多余选择点，以使谓词完全确定，除了使用剪切符号之外，还有其他推荐的方法来完成这个目标吗？

提前感谢！

- SND

---

你真的是要求 H =:= 1 吗？请注意，如果 H 没有被实例化，这个目标会产生一个错误。 - false

说实话，我并没有真正考虑代码示例中的具体测试，而是更多地参考了存在两个不同基本情况的情况。我添加了等于一的测试只是为了在递归过程中发生一些事情，这可以帮助我澄清我的问题。 - SND

Answer 1

尽力避免使用!/0, 因为这几乎总是完全破坏了程序的声明性语义。
所有可以通过模式匹配表达的内容应该用模式匹配来表达。例如：

every_second([]).
every_second([_|Ls]) :-
        every_second_(Ls).
every_second_([]).
every_second_([1|Rest]) :- every_second(Rest).

就像你的不纯版本一样，对于你发布的示例，没有任何选择点：

?- every_second([1]).
true.
?- every_second([3,1]).
true.
?- every_second([3,1,3]).
true.

请注意，在此版本中，所有谓词都是完全纯洁且可用于所有方向。与逻辑关系所期望的一样，该关系也适用于最通用的查询并且产生答案：

?- every_second(Ls).
Ls = [] ;
Ls = [_G774] ;
Ls = [_G774, 1] ;
Ls = [_G774, 1, _G780] ;
Ls = [_G774, 1, _G780, 1] .

由于您使用了不纯或不声明性的谓词(!/0, (=:=)/2)，因此您发布的任何版本都无法做到这一点！
在处理列表时，您几乎总是可以仅使用模式匹配来区分不同情况。如果无法实现此操作，例如在保留可接受性能的同时保持逻辑纯洁性，可以使用if_/3等方法。

- mat

---

我不同意。! 可以在安全的地方使用，如果你想要获得效率，有时候你应该使用它。变通方法通常会产生更少可读性的代码，这将以可读性为代价换取效率，这是错误的交易方向。 - Bakuriu

您的不同意似乎仅限于那些没有在您所附加评论的帖子中提到的陈述。它并未说“！/0”不能用于安全的地方，也没有说您必须不使用“！/0”来提高效率，也没有说所有或仅少数变通方法会产生更易读的代码，当然也没有说为了效率而牺牲可读性是正确的方向。实际的帖子中是否有任何您不同意的内容？ - mat

Answer 2

技巧在于“柯里化”规则中的未绑定数量：

base([]). 
base([_|Q]) :- base2(Q).

base2([]). 
base2([H|Q]) :- H =:= 1, base(Q).

然而，说“删减是不好的”这样的规则是错误的。事实上，我最喜欢的做法是：

base([]) :- !. 
base([_]) :- !. 
base([_,H|Q]) :- !, H =:= 1, base(Q).

考虑这个 primes(++) 的例子：

primes([5]).
primes([7]).
primes([11]).

vs

primes([5]) :- !.
primes([7]) :- !.
primes([11]) :- !.

- pasaba por aqui

---

您最喜欢的版本在base(Xs), Xs = [2]上出现错误。 - false

好的，请说出来。这一点毫不明显。 - false

剪枝并不总是不好的。但是过度鼓励初学者大量使用剪枝也是不好的，如果它们只是被用来“让谓词工作”，那么应该避免使用。这就像在C语言中说goto语句不好一样，它们不都是不好的，但是如果你让一个初学者自由使用goto并且没有明确的指导方针告诉他们何时需要使用它们，那么会导致非常糟糕的编程习惯和结构混乱的代码。因此，在解决方案中，最好解释“为什么”剪枝是必要的，而不仅仅是“随意使用”。 :) - lurker