如何使用尾递归在序言中实现展平列表？

Question

如何使用尾递归在序言中实现展平列表？

这是带有简单递归的 flatten/2 代码（即没有回溯的意思）：

flatten([], []).
flatten([L|Ls], FlatL) :-
    !,
    flatten(L, NewL),
    flatten(Ls, NewLs),
    append(NewL, NewLs, FlatL).
flatten(L, [L]).

?- flatten([1, [2,3], [4]], X).
X=[1,2,3,4].

我正在尝试使用尾递归（累加器）执行相同的算法。例如，谓词sum/2返回列表中所有成员的相加，并带有回溯：

sum([X],[X]).
sum([H|T],S) :- sum(T,S1), S is H + S1 .

与尾递归相同的算法是

sum1(L,S) :- sum1(L,0,S).

sum1([],Acc,Acc).
sum1([H|T],Acc,S) :- Acc1 is Acc+H, s(T,Acc1,S).

Answer 1

您可能想阅读尾递归优化

• 什么是尾调用优化？
• https://en.wikipedia.org/wiki/Tail_recursion

尾递归优化/消除与累加器几乎没有关系。它与调用堆栈上的当前帧是否可以重用有关。如果可以，递归调用将有效地转换为迭代。如果它不能被重用，一个新的帧必须被推入堆栈，带来令人讨厌的副作用，[最终]你会抛出一个堆栈溢出异常。

这是尾递归并优化为迭代：

write_list( [] ) .
write_list( [X|Xs] ) :-
  write(X),nl,
  write_list(Xs).

这不是：

factorial(1,1) .
factorial(N,F) :-
  N > 1 ,
  N1 is N-1 ,
  factorial(N1,F1) ,
  F is N1+F1 .

不同之处在于前者，在递归调用之后没有使用任何本地的东西，因此可以重用堆栈帧。在后者中，必须保留堆栈帧的内容，因此必须为递归调用分配一个新的堆栈帧。

但是，以下内容应该适合您。

flatten( Xs , Fs ) :-       % to flatten a list of via an accumulator...
  flatten( Xs , [] , Rs ) , % - invoke the worker predicate with the accumulator seeded as the empty list.
  reverse(Rs,Fs)            % - since the flattened list will be built in reverse order, you'll need to reverse it after all the work is done.
  .

flatten( []     , Fs , Fs ) .  % if the source list is exhausted, our work is done.
flatten( [X|Xs] , Ts , Fs ) :- % otherwise...
  is_list(X) ,                 % - if the head of the list is itself a list
  ! ,                          % - eliminate the choice point.
  flatten(X,Ts,T1) ,           % - flatten the sublist by invoking the worker predicate on the sublist
  flatten(Xs,T1,Fs)            % - and then continue
  .                            %
flatten( [X|Xs] , Ts , Fs ) :- % finally, the list head must be unbound or some other non-list thing.
  flatten(Xs,[X|Ts],Fs)        % - prepend it to the accumulator and continue.
  .                            %

is_list( X     ) :- var(X) , ! , fail . % unbound variables are manifestly not lists.
is_list( []    ) .                      % but the empty lislt is.
is_list( [_|_] ).                       % and so is a non-empty list.

您应该注意它不是完全尾递归的。每次遇到嵌套列表时，它都必须保存当前状态，因此它可以在递归调用以展平子列表后从停止的地方继续。