A simple recursive solution will also work. Recursion is done by the head of the input list. In the non-trivial case, when the head is a list itself, we just append the rest of the flattened list to it. In the code below, it has not flattened Rest
yet in append(H, Rest, Out)
, but it will be, after the recursive call of g(In, Rest)
. Cut after the append call ensures that backtracking won't consider the last case, where the head will appear in the output as-is.
% Base case, empty list.
g([], []).
% First recursive case: head is list.
% Append remaining elements to it.
g([H|In], Out):-
append(H, Rest, Out), !,
g(In, Rest).
% Second recursive case: head is not list.
% Will appear as-is in the output.
g([H|In], [H|Out]):-
g(In, Out).