CODEWITHSUNDEEP
prologtail-recursiontail-call-optimization
bill williams
bill williams

Reputation: 53

Prolog Tail call optimization for flattening a tree

I want to flatten a tree in prolog using tail recursion.I have done it with append list with recursive calls. I want to optimize my version. This is my function which uses recursive call.I want to make it tail call optimized.

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]]

Can anyone help me please.I am new to prolog. TIA

Upvotes: 2

Views: 226

Answers (1)

false
false

Reputation: 10102

You are not actually flattening. This would do so:

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

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

That is as tail-recursive as it could be.

Upvotes: 2

Related Questions