Prolog爲扁平化樹調用尾部優化

Question

我想使用尾遞歸來扁平化prolog中的一棵樹。我已經用遞歸調用來追加列表。我想優化我的版本。這是我使用遞歸調用的函數。我想讓它的尾部調用優化。

fl_t(lf(A),[A]). 
fl_t(tr(A,B,C),S4):- fl_t(A,X1),fl_t(C,X2),append(X2,[Y],X3),append(X3,X1,S4). 

Input : fl_t(lf(a),Result) 
Output : Result=[a] 

Input : fl_t(tr(lf([1, 2]), 3, leaf([4, 5])),Result) 
Output : Result = [[1,2],3,[4,5]] 

任何人都可以幫助我please.I新來的序言。 TIA

Answer 1

你實際上並不平坦。這將這樣做：

fl_t(T, Xs) :- 
    phrase(fl(T), Xs). 

fl(lf(A)) --> [A]. 
fl(tr(A, B, C)) --> 
    fl(A), 
    [B], 
    fl(C). 

這是作爲尾遞歸，因爲它可能是。