以下を末尾再帰バージョンに変換するにはどうすればよいですか。
sum(void,0).
sum(t(V,L,R),S) :-
sum(L,S1),
sum(R,S2),
S is V + S1 + S2.
分岐は 2^n の大きさであるため、単一のアキュムレータを維持することは不可能のようです。
考えられる解決策は、反復ごとにアキュムレータに新しいアキュムレータをリストに追加させることです。多分上記の解決策は最適ですか?
前もって感謝します。
以下を末尾再帰バージョンに変換するにはどうすればよいですか。
sum(void,0).
sum(t(V,L,R),S) :-
sum(L,S1),
sum(R,S2),
S is V + S1 + S2.
分岐は 2^n の大きさであるため、単一のアキュムレータを維持することは不可能のようです。
考えられる解決策は、反復ごとにアキュムレータに新しいアキュムレータをリストに追加させることです。多分上記の解決策は最適ですか?
前もって感謝します。
はい、ツリー内の各ノードに対して sum/2 述語を正確に 1 回呼び出すため、ソリューションは最適です (呼び出しを減らすことはできません)。いいえ、アキュムレータを使用して自分でスタックを実装することにより、末尾再帰にすることができます。
これが例です(テストされていません)。平坦化述語は sum と統合できますが、ここではわかりやすくするために区別しています (どちらも末尾再帰です)。
flatten([], Acc, Acc).
flatten([void|ToGo], Acc, Result) :-
flatten(ToGo, Acc, Result).
flatten([t(V,L,R)|ToGo], Acc, Result) :-
flatten([L,R|ToGo], [t(V,L,R)|Acc], Result).
flatten(Root, Result) :-
flatten([Root], [], Result).
sum([], Result, Result).
sum([t(V,_,_)|ToGo], Acc, Result) :-
NewAcc is Acc+V,
sum(ToGo, NewAcc, Result).
sum(Tree, Result) :-
flatten(Tree, FlatTree),
sum(FlatTree, 0, Result).