Prolog 递归的顺序重要吗？

Question

我对一个问题的两种解决方案之间的区别有疑问。该问题要求将列表转换为截断列表，如下所示：

?- reduce([a,a,a,b,b,c,c,b,b,d,d],Z).
Z = [a,b,c,b,d].

第一个解决方案需要一个额外的步骤来反转列表：

reduce([X|Xs],Z) :-
   reduce(X,Xs,Y,[X]),
   reverse(Y,Z).

reduce(X,[L|Ls],Y,List) :-
    (  X=L
    -> reduce(X,Ls,Y,List)
    ;  reduce(L,Ls,Y,[L|List])
    ).
reduce(_,[],Y,Y).

第二种方案不需要reverse/2:

reduced([X|Xs],Result) :- 
    reduced(Xs,List),
    List=[A|_],
    (  A=X
    -> Result=List
    ;  Result=[X|List]
    ),
    !.
reduced(Result,Result).

在一系列语句之前或之后执行递归时，优化注意事项是什么？条件的顺序重要吗？我倾向于认为预先进行所有递归是可行的方法，尤其是因为这里有必要向后构建列表。

Answer 1

当你优化任何东西时，一定要先测量！（我们大多数人往往会忘记这一点......）

优化 Prolog 时，请注意以下事项：

尾递归往往做得更好（所以你的 "before or after series of statements" 问题来了）；
避免创建不需要的选择点（这取决于 Prolog 实现）
使用最佳算法（例如，如果不需要，请不要遍历列表两次）。

"optimized" 或多或少标准的 Prolog 实现的解决方案看起来可能会有点不同。我将其命名为 list_uniq（类似于命令行 uniq 工具）：

list_uniq([], []). % Base case
list_uniq([H|T], U) :-
    list_uniq_1(T, H, U). % Helper predicate

list_uniq_1([], X, [X]).
list_uniq_1([H|T], X, U) :-
    (   H == X
    ->  list_uniq_1(T, X, U)
    ;   [X|U1] = U,
        list_uniq_1(T, H, U1)
    ).

它与@CapelliC 的reduce0/2 不同，因为它使用滞后来避免[X|Xs] 和[=15= 固有的不确定性] 在第一个参数中。

现在声明它是 "optimized":

恰好遍历链表一次（不需要倒序）
它是尾递归的
它不会创建和丢弃选择点

您将获得与@CapelliC 相同的 12 个推论，如果您使用更长的列表，您将开始看到差异：

?- length(As, 100000), maplist(=(a), As),
   length(Bs, 100000), maplist(=(b), Bs),
   length(Cs, 100000), maplist(=(c), Cs),
   append([As, Bs, Cs, As, Cs, Bs], L),
   time(list_uniq(L, U)).
% 600,006 inferences, 0.057 CPU in 0.057 seconds (100% CPU, 10499893 Lips)
As = [a, a, a, a, a, a, a, a, a|...],
Bs = [b, b, b, b, b, b, b, b, b|...],
Cs = [c, c, c, c, c, c, c, c, c|...],
L = [a, a, a, a, a, a, a, a, a|...],
U = [a, b, c, a, c, b].

与@CapelliC 的回答reduce0、reduce1、reduce2 相同的查询：

% reduce0(L, U)
% 600,001 inferences, 0.125 CPU in 0.125 seconds (100% CPU, 4813955 Lips)
% reduce1(L, U)
% 1,200,012 inferences, 0.393 CPU in 0.394 seconds (100% CPU, 3050034 Lips)
% reduce2(L, U)
% 2,400,004 inferences, 0.859 CPU in 0.861 seconds (100% CPU, 2792792 Lips)

因此，通过削减 (!) 创建和丢弃选择点也是有代价的。

然而，就目前而言，list_uniq/2 对于第一个参数不为基础的查询可能是错误的：

?- list_uniq([a,B], [a,b]).
B = b. % OK

?- list_uniq([a,A], [a]).
false. % WRONG!

reduce0/2 和 reduce1/2 也可能是错误的：

?- reduce0([a,B], [a,b]).
false.

?- reduce1([a,B], [a,b]).
false.

至于reduce2/2，这个我不太确定：

?- reduce2([a,A], [a,a]).
A = a.

相反，使用中 if_/3 的定义：

list_uniq_d([], []). % Base case
list_uniq_d([H|T], U) :-
    list_uniq_d_1(T, H, U). % Helper predicate

list_uniq_d_1([], X, [X]).
list_uniq_d_1([H|T], X, U) :-
    if_(H = X,
        list_uniq_d_1(T, H, U),
        (   [X|U1] = U,
            list_uniq_d_1(T, H, U1)
        )
    ).

有了它：

?- list_uniq_d([a,a,a,b], U).
U = [a, b].

?- list_uniq_d([a,a,a,b,b], U).
U = [a, b].

?- list_uniq_d([a,A], U).
A = a,
U = [a] ;
U = [a, A],
dif(A, a).

?- list_uniq_d([a,A], [a]).
A = a ;
false. % Dangling choice point

?- list_uniq_d([a,A], [a,a]).
false.

?- list_uniq_d([a,B], [a,b]).
B = b.

?- list_uniq_d([a,A], [a,a]).
false.

需要更长的时间，但谓词似乎正确。使用与其他时间相同的查询：

% 3,000,007 inferences, 1.140 CPU in 1.141 seconds (100% CPU, 2631644 Lips)

Answer 2

分析似乎是回答效率问题的更简单方法：

% my own
reduce0([], []).
reduce0([X,X|Xs], Ys) :- !, reduce0([X|Xs], Ys).
reduce0([X|Xs], [X|Ys]) :- reduce0(Xs, Ys).

% your first
reduce1([X|Xs],Z) :- reduce1(X,Xs,Y,[X]), reverse(Y,Z).
reduce1(X,[L|Ls],Y,List) :-
    X=L -> reduce1(X,Ls,Y,List);
    reduce1(L,Ls,Y,[L|List]).
reduce1(_,[],Y,Y).

% your second
reduce2([X|Xs],Result) :- 
    reduce2(Xs,List),
    List=[A|_],
    (A=X -> Result=List;
    Result=[X|List]),!.
reduce2(Result,Result).

SWI-Prolog 提供 time/1：

4 ?- time(reduce0([a,a,a,b,b,c,c,b,b,d,d],Z)).
% 12 inferences, 0.000 CPU in 0.000 seconds (84% CPU, 340416 Lips)
Z = [a, b, c, b, d].

5 ?- time(reduce1([a,a,a,b,b,c,c,b,b,d,d],Z)).
% 19 inferences, 0.000 CPU in 0.000 seconds (90% CPU, 283113 Lips)
Z = [a, b, c, b, d] ;
% 5 inferences, 0.000 CPU in 0.000 seconds (89% CPU, 102948 Lips)
false.

6 ?- time(reduce2([a,a,a,b,b,c,c,b,b,d,d],Z)).
% 12 inferences, 0.000 CPU in 0.000 seconds (83% CPU, 337316 Lips)
Z = [a, b, c, b, d].

你的第二个谓词和我的一样，而第一个似乎留下了一个选择点...

考虑到 Prolog 实施的解析策略，条件顺序是最重要的。在天真的实现中，像我的 IL, tail recursion optimization 只有在递归调用是最后一个时才被识别，并且在之前有一个 cut。只是为了确保它是确定性的...

Answer 3

此答案是的直接跟进。

估计if_/3编译后的运行时间，我用手动编译的 if_/3 制作了 list_uniq_e/2 就像@Boris 的 list_uniq_d/2 一样。

list_uniq_e([], []). % Base case
list_uniq_e([H|T], U) :-
    list_uniq_e_1(T, H, U). % Helper predicate

list_uniq_e_1([], X, [X]).
list_uniq_e_1([H|T], X, U) :-
    =(H,X,Truth),
    list_uniq_e_2(Truth,H,T,X,U).

list_uniq_e_2(true ,H,T,_,   U ) :- list_uniq_e_1(T,H,U).
list_uniq_e_2(false,H,T,X,[X|U]) :- list_uniq_e_1(T,H,U).

让我们比较一下运行时间（SWI Prolog 7.3.1，Intel Core i7-4700MQ 2.4GHz）！

首先，list_uniq_d/2：

% 3,000,007 inferences, 0.623 CPU in 0.623 seconds (100% CPU, 4813150 Lips)

接下来，list_uniq_e/2：

% 2,400,003 inferences, 0.132 CPU in 0.132 seconds (100% CPU, 18154530 Lips)

为了完整起见reduce0/2、reduce1/2和reduce2/2:

% 600,002 inferences, 0.079 CPU in 0.079 seconds (100% CPU, 7564981 Lips)
% 600,070 inferences, 0.141 CPU in 0.141 seconds (100% CPU, 4266842 Lips)
% 600,001 inferences, 0.475 CPU in 0.475 seconds (100% CPU, 1262018 Lips)

不错！而且...这不是该行的结尾---就优化 if_/3 而言:)

Answer 4

希望这是 than my 的更好后续！

首先，再次引用@Boris 的代码（100% 原创）：

list_uniq_d([], []). % Base case
list_uniq_d([H|T], U) :-
    list_uniq_d_1(T, H, U). % Helper predicate

list_uniq_d_1([], X, [X]).
list_uniq_d_1([H|T], X, U) :-
    if_(H = X,
        list_uniq_d_1(T, H, U),
        (   [X|U1] = U,
            list_uniq_d_1(T, H, U1)
        )
    ).

加上更多用于基准测试的代码：

bench(P_2) :-
   length(As, 100000), maplist(=(a), As),
   length(Bs, 100000), maplist(=(b), Bs),
   length(Cs, 100000), maplist(=(c), Cs),
   append([As, Bs, Cs, As, Cs, Bs], L),
   time(call(P_2,L,_)).

现在，让我们介绍模块 re_if:

:- module(re_if, [if_/3, (=)/3, expand_if_goals/0]).

:- dynamic expand_if_goals/0.

trusted_truth(_=_).  % we need not check truth values returned by (=)/3

=(X, Y, R) :- X == Y,    !, R = true.
=(X, Y, R) :- ?=(X, Y),  !, R = false.  % syntactically different
=(X, Y, R) :- X \= Y,    !, R = false.  % semantically different
=(X, Y, R) :- R == true, !, X = Y.
=(X, X, true).
=(X, Y, false) :- dif(X, Y).

:- meta_predicate if_(1,0,0).
if_(C_1,Then_0,Else_0) :-
   call(C_1,Truth),
   functor(Truth,_,0),          % safety check
   (  Truth == true -> Then_0
   ;  Truth == false , Else_0
   ).

:- multifile system:goal_expansion/2.
system:goal_expansion(if_(C_1,Then_0,Else_0), IF) :-
   expand_if_goals,
   callable(C_1),           % nonvar && (atom || compound)
   !,
   C_1 =.. Ps0,
   append(Ps0,[T],Ps1),
   C_0 =.. Ps1,
   (  trusted_truth(C_1)
   -> IF = (C_0,               ( T == true -> Then_0 ;             Else_0))
   ;  IF = (C_0,functor(T,_,0),( T == true -> Then_0 ; T == false, Else_0))
   ).

现在……*鼓声*……瞧瞧:)

$ swipl
Welcome to SWI-Prolog (Multi-threaded, 64 bits, Version 7.3.3-18-gc341872)
Copyright (c) 1990-2015 University of Amsterdam, VU Amsterdam
SWI-Prolog comes with ABSOLUTELY NO WARRANTY. This is free software,
and you are welcome to redistribute it under certain conditions.
Please visit http://www.swi-prolog.org for details.

For help, use ?- help(Topic). or ?- apropos(Word).

?- compile(re_if), compile(list_uniq).
true.

?- bench(list_uniq_d).
% 2,400,010 inferences, 0.865 CPU in 0.865 seconds (100% CPU, 2775147 Lips)
true.

?- assert(re_if:expand_if_goals), compile(list_uniq).
true.

?- bench(list_uniq_d).
% 1,200,005 inferences, 0.215 CPU in 0.215 seconds (100% CPU, 5591612 Lips)
true.

Prolog 递归的顺序重要吗？

Prolog Does the order of recursion matter?

optimization

recursion

memory-management

prolog