Prolog:避免使用和不使用cut运算符的冗余选择点(非确定性)

Question

首先,我已经阅读了有关Prolog削减使用的所有其他帖子,并且肯定会看到与使用它们相关的问题.但是,对我来说仍然有些不清楚,我想一劳永逸地解决这个问题.

在下面的简单示例中,我们递归遍历列表并检查每个第2个元素是否等于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([]).

这也可以在不使用剪切的情况下消除冗余选择点,但当然,我们只需将选择点转移到具有偶数位数的列表的查询,如下所示:

?- 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帖子中的一个答案中告诉我,这不是剪切算子的推荐用法,我应尽量避免使用它.

这让我想到了我的双边问题:

• 如果切割,无论其存在的规则的位置如何,都会改变行为,但不是解决方案(如上例所示),它仍然被认为是不好的做法吗？

• 如果我想取消上面例子中的典型冗余选择点以使谓词完全确定,那么还有其他推荐的方法来实现这一点而不是使用剪切吗？

提前致谢!

Answer 1

总是尽量避免!/0.几乎无一例外,!/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逻辑纯度,同时仍保持可接受的性能.