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

Question

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

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

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 .

the same algo with tail recursion is

sum1(L,S) :- sum1(L,0,S).

sum1([],Acc,Acc).
sum1([H|T],Acc,S) :- Acc1 is Acc+H, s(T,Acc1,S).

Answer 1

You might want to read up on tail recursion optimization

• What Is Tail Call Optimization?
• https://en.wikipedia.org/wiki/Tail_recursion

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).

This is not:

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.