如何使用尾递归在序言中实现展平列表? [英] How to implement flatten list in prolog ,with tail recursion?
问题描述
如何在prolog中使用尾递归实现扁平化列表?
How to implement flatten list in prolog ,with tail recursion ?
这是带有简单递归的 flatten/2 代码(即没有回溯的意思):
This is code for flatten/2 with simple recursion (that is mean without back-tracking):
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 返回列表中所有成员的相加，并带有回溯:
I'm trying to do the same algorithm but with tail recursion (Accumulator). For exemple, the predicate sum/2 returns the addition of all member of the list, with backtracking:
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).
推荐答案
你可能想阅读尾递归优化
You might want to read up on tail recursion optimization
尾递归优化/消除与累加器几乎没有关系.它与调用堆栈上的当前帧是否可以重用有关.如果可以，递归调用将有效地转换为迭代.如果它不能被重用，一个新的帧就必须被压入堆栈，带来令人讨厌的副作用，[最终]你会抛出一个堆栈溢出异常.
Tail recursion optimization/elimination has little to nothing to do with accumulators. It has to do with whether or not the current frame on the call stack can be reused. If it can, the recursive call is effectively converted into iteration. If it can't be reused, a new frame has to be pushed on the stack with the nasty side effect that [eventually] you will throw a stack overflow exception.
这是尾递归并优化为迭代:
This is tail recursive and gets optimized into iteration:
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 .
区别在于前者，在递归调用之后没有使用任何本地的东西，因此可以重用堆栈帧.在后者中，必须保留堆栈帧的内容，因此必须为递归调用分配一个新的堆栈帧.
The difference is that in the former, no use is made of anything local following the recursive call, and so the stack frame can be reused. In the latter, the contents of the stack frame must be preserved, and so a new stack frame must be allocated for the recursive call.
但是，以下内容应该适合您.
However, the following should do the job for you.
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.
你应该注意到它不是完全的尾递归.每次遇到嵌套列表时，它都必须保存当前状态，以便在递归调用以展平子列表后可以从中断的地方继续.
You should note that it's not completely tail recursive. Every time a nested list is encountered, it's got to save the current state, so it can continue from where it left off after the recursive call to flatten the sublist.
这篇关于如何使用尾递归在序言中实现展平列表?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
