How to implement flatten list in prolog ,with tail recursion? -

How to implement flatten list in prolog ,with tail recursion? -

how implement flatten list in prolog ,with tail recursion ?

this code flatten/2 simple recursion (that 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].

i'm trying same algorithm tail recursion (accumulator). exemple, predicate sum/2 returns add-on of fellow member of list, backtracking:

sum([x],[x]). sum([h|t],s) :- sum(t,s1), s h + s1 .

the same algo tail recursion

sum1(l,s) :- sum1(l,0,s). sum1([],acc,acc). sum1([h|t],acc,s) :- acc1 acc+h, s(t,acc1,s).

you might want read on tail recursion optimization

what tail phone call optimization? https://www.princeton.edu/~achaney/tmve/wiki100k/docs/tail_recursion.html

tail recursion optimization/elimination has little nil accumulators. has whether or not current frame on phone call stack can reused. if can, recursive phone call converted iteration. if can't reused, new frame has pushed on stack nasty side effect [eventually] throw stack overflow exception.

this tail recursive , gets optimized iteration:

write_list( [] ) . write_list( [x|xs] ) :- write(x),nl, write_list(xs).

this not:

factorial(1,1) . factorial(n,f) :- n > 1 , n1 n-1 , factorial(n1,f1) , f n1+f1 .

the difference in former, no utilize made of local next recursive call, , stack frame can reused. in latter, contents of stack frame must preserved, , new stack frame must allocated recursive call.

however, next should job you.

flatten( xs , fs ) :- % flatten list of via accumulator... flatten( xs , [] , rs ) , % - invoke worker predicate accumulator seeded empty list. reverse(rs,fs) % - since flattened list built in reverse order, you'll need reverse after work done. . flatten( [] , fs , fs ) . % if source list exhausted, our work done. flatten( [x|xs] , ts , fs ) :- % otherwise... is_list(x) , % - if head of list list ! , % - eliminate selection point. flatten(x,ts,t1) , % - flatten sublist invoking worker predicate on sublist flatten(xs,t1,fs) % - , go on . % flatten( [x|xs] , ts , fs ) :- % finally, list head must unbound or other non-list thing. flatten(xs,[x|ts],fs) % - prepend accumulator , continue. . % is_list( x ) :- var(x) , ! , fail . % unbound variables manifestly not lists. is_list( [] ) . % empty lislt is. is_list( [_|_] ). % , non-empty list.

you should note it's not tail recursive. every time nested list encountered, it's got save current state, can go on left off after recursive phone call flatten sublist.

prolog tail-recursion