Prolog:使用和不使用 cut 运算符避免冗余选择点(非确定性)
Prolog : avoid redundant choice points (non-determinism) with and without cut operator
首先,我已经阅读了 SO 上所有其他关于 Prolog 中削减的使用的 posts,并且肯定看到了与使用它们相关的问题。但是,我还有一些不明之处,我想一劳永逸地解决这个问题。
在下面的简单示例中,我们递归地遍历一个列表并检查是否每个第二个元素都等于 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 post 上的一个回答中被告知,不推荐使用 cut 运算符,我应该尽量避免使用它。
这让我想到了我的二分问题:
如果剪切,无论它在规则中的位置如何,都会改变行为,但不会改变解决方案(如上例所示),它仍然被认为是不好的做法吗?
如果我想去掉上面示例中的典型冗余选择点以使谓词完全确定,是否有其他推荐的方法来完成此操作而不是使用削减?
提前致谢!
诀窍是 "currying" 超过规则中的无限数量:
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]).
对
primes([5]) :- !.
primes([7]) :- !.
primes([11]) :- !.
总是尽量避免!/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] .
None 您发布的版本可以做到这一点,因为您使用的是不纯的或非声明性谓词(!/0
、(=:=)/2
)!
在对列表进行推理时,几乎总是可以单独使用模式匹配来区分大小写。如果那不可能,请使用例如 if_/3
以获得逻辑纯度,同时仍保持可接受的性能。
首先,我已经阅读了 SO 上所有其他关于 Prolog 中削减的使用的 posts,并且肯定看到了与使用它们相关的问题。但是,我还有一些不明之处,我想一劳永逸地解决这个问题。
在下面的简单示例中,我们递归地遍历一个列表并检查是否每个第二个元素都等于 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 post 上的一个回答中被告知,不推荐使用 cut 运算符,我应该尽量避免使用它。
这让我想到了我的二分问题:
如果剪切,无论它在规则中的位置如何,都会改变行为,但不会改变解决方案(如上例所示),它仍然被认为是不好的做法吗?
如果我想去掉上面示例中的典型冗余选择点以使谓词完全确定,是否有其他推荐的方法来完成此操作而不是使用削减?
提前致谢!
诀窍是 "currying" 超过规则中的无限数量:
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]).
对
primes([5]) :- !.
primes([7]) :- !.
primes([11]) :- !.
总是尽量避免!/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] .
None 您发布的版本可以做到这一点,因为您使用的是不纯的或非声明性谓词(!/0
、(=:=)/2
)!
在对列表进行推理时,几乎总是可以单独使用模式匹配来区分大小写。如果那不可能,请使用例如 if_/3
以获得逻辑纯度,同时仍保持可接受的性能。