Splice in sublists in a list, without using flatten/2

Question

I want to make one list of multiple sublists without using the flatten predicate in Prolog.

This is my code:

acclistsFromList([],A,A).
acclistsFromList([H|T],Listwithinlist,A):-
  not(is_list(H)), 
  acclistsFromList(T,Listwithinlist,A).
acclistsFromList([H|T],Listwithinlist,A):-
  is_list(H), 
  append([H],Listwithinlist,Acc2), 
  acclistsFromList(T,Acc2,A).

I get this as output

?- listsFromList([1,2,[a,b,c],3,4,[d,e]],X). 
X = [[d, e], [a, b, c]] ;

But I want this:

?- listsFromList([1,2,[a,b,c],3,4,[d,e]],X).
X = [a, b, c, d, e] .

?- listsFromList([1,[],2,3,4,[a,b]],X).
X = [a, b] .

?- listsFromList([[[[a]]],b,c,d,e,[f]],X).
X = [f, a] .

?- listsFromList([[[[a]],b,[c]],d,e,[f]],X).
X = [f, a, b, c] .

What is the best way to reach this result, without using flatten?

Answer 1

The second clause of the acclistsFromList/3 does not do anything with H if it has verified that H is not a list, but you need to prepend the result with H.

acclistsFromList([H|T], Listwithinlist, [H|A]) :-
    \+ is_list(H),
    acclistsFromList(T, Listwithinlist, A).

but this is not sufficient. Since you prepend to the accumulator, the result is reversed. You do not need an accumulator here anyway:

acclistsFromList([], []).
acclistsFromList([H|T], [H|A]) :-
    \+ is_list(H),
    acclistsFromList(T, A).
acclistsFromList([H|T], Result):-
    is_list(H),
    append(H, Res1, Result),
    acclistsFromList(T, Res1).

or without the "scalar" elements:

acclistsFromList([], []).
acclistsFromList([H|T], A) :-
    \+ is_list(H),
    acclistsFromList(T, A).
acclistsFromList([H|T], Result):-
    is_list(H),
    append(H, Res1, Result),
    acclistsFromList(T, Res1).

This furthermore does not recurse on lists. A list of lists of lists will thus not be flattened. I leave it as an exercise to implement this.

Answer 2

This is a one-liner,

foo(X,L) :- 
  findall(Z, (member(A,X),is_list(A),member(Z,A)), L).

(as seen here).

To deal with multi-layered nested lists, we need to use a recursive predicate,

nembr(Z,A) :-    % member in nested lists
  is_list(A), member(B,A), nembr(Z,B)
  ;
  \+ is_list(A), A=Z.

then use it instead of that final member call in findall's goal:

bar(X,L) :- 
  findall(Z, (member(A,X),is_list(A),nembr(Z,A)), L).

testing:

10 ?- foo([1,2,[a,b,c],3,4,[d,e]],X).
X = [a, b, c, d, e].

11 ?- bar([1,2,[a,b,c],3,4,[d,e]],X).
X = [a, b, c, d, e].

12 ?- bar([1,2,[a,b,[[[c]]]],3,4,[d,e]],X).
X = [a, b, c, d, e].

Answer 3

In case you want to roll your own, here's breadth-first enumeration of arbitrarily nested lists:

bfs( XS, L) :- bfs( s(z), [XS|Q], Q,  L, []).

bfs( z, _, _, Z, Z).
bfs( s(N), [[]   |P], Q,  L, Z) :- bfs( N, P, Q,  L, Z).
bfs( s(N), [[A|B]|P], Q,  L, Z) :-
  is_list(A)                                     % if is_list(A), 
  -> Q = [A|R], bfs( s(s(N)), [B|P], R,  L, Z)   % then      enqueue A, 
  ;  L = [A|R], bfs(   s(N),  [B|P], Q,  R, Z).  % otherwise produce A

The first argument is the distance between read and write point on the queue. When they meet the queue has become exhausted and we stop. Both the input queue and the output list are maintained as difference list pairs of head and tail variables.

Trying it out:

12 ?- bfs( [[[6]],1,2,[4,[[[[[7]]]]],5],3], A).
A = [1, 2, 3, 4, 5, 6, 7] .

You will need to augment it to skip the non-lists in the top level.

Answer 4

A solution that uses an "open list" to append the elements encountered while walking the list-of-lists, which is essentially a tree, in prefix fashion.

The indicated examples indicate that non-list elements at depth 0 shall be discarded, and the other elements sorted by depth. However, no precise spec is given.

Indeed, one would expect the result of flattening

[[[[a]],b,[c]],d,e,[f]]

to be

[b,f,c,a]

via the "sorted-by-depth" pair list of Depth-Value pairs:

[3-a,1-b,2-c,1-f]

But the question poster requests this result instead:

[f, a, b, c]

I don't really know whether this is an error or not.

:- debug(flatwalker).

flatwalker(ListIn,ListOut) :-
   Tip=Fin,                            % 2 unbound variables
   %                                   % designating the same memory
   %                                   % cell. Hold the Tip, grow at Fin.
   flatwalker_2(0,ListIn,Fin,TerFin),  % Elements are appended at Fin.
   %                                   % The final Fin is found in TerFin
   %                                   % on success.
   TerFin=[],                          % Unify TerFin with [], closing
   %                                   % the list at Tip.
   keysort(Tip,Sorted),                % Sort the closed list at Tip
   %                                   % by pair key, i.e. by depth.
   %                                   % keysort/2 is stable and keeps
   %                                   % duplicates.
   debug(flatwalker,"Got : ~q",[Tip]),
   maplist([_-V,V]>>true,Sorted,ListOut). % Remove depth values.

% ---
% flatwalker_2(+Depth,+TreeIn,+Fin,+TerFin)
% Depth:  Input integer, indicates current tree depth.
% TreeIn: The list to flatten at this depth (it's a node of the tree,
%         which may or may not contain subtrees, i.e. lists)
% Fin:    Always an unbound variable denoting the end of an open list to
%         which we will append.
%         ("points to an empty memory cell at the fin of the open list")
%         Works as an accumulator as a new Fin, advanced by 1 cell at each
%         append operation is handed to the next flatwalker_2/4
%         activation.
% TerFin: When flatwalker_2/ is done, the final Fin is unified with 
%         TerFin so that it can be passed to flatwalker/2.
% ---

% We make the guards explicit and cut heavily.
% Optimizing the guards (if so desired) is left as an exercise.

flatwalker_2(_,[],Fin,Fin) :- !.       % Done as TreeIn is empty. 
                                       % Unify Fin with TerFin.

flatwalker_2(0,[X|Xs],Fin,TerFin) :-   % Case of X is nonlist at depth 0:
   %                                   % discard!
   \+is_list(X),!,
   flatwalker_2(0,Xs,Fin,TerFin).      % Continue with the rest of the
                                       % list at this depth.

flatwalker_2(D,[X|Xs],Fin,TerFin) :-   % Case of X is nonlist at
   %                                   % depth > 0: keep!
   D>0,\+is_list(X),!,
   Fin=[D-X|Fin2],                     % Grow the result list at its
   %                                   % Fin by D-X.
   flatwalker_2(D,Xs,Fin2,TerFin).     % Continue with the rest of the
                                       % list at this depth.

flatwalker_2(D,[X|Xs],Fin,TerFin) :-   % Case of X is a list at any
   %                                   % depth.
   is_list(X),!,
   DD is D+1,
   flatwalker_2(DD,X,Fin,Fin2),        % Collect one level down
   flatwalker_2(D,Xs,Fin2,TerFin).     % On return, continue with the 
                                       % rest of the list at this depth.

Some plunit tests:

:- begin_tests(flatwalker).

test("empty",true(Out == [])) :-
   flatwalker([],Out).

test("simple",true(Out == [])) :-
   flatwalker([1,2,3],Out).

test("with empties",true(Out == [])) :-
   flatwalker([[],1,[],2,[],3,[]],Out).

test("test 1",true(Out == [a, b, c, d, e])) :-
   flatwalker([1,2,[a,b,c],3,4,[d,e]],Out).

test("test 2",true(Out == [a, b])) :-
   flatwalker([1,[],2,3,4,[a,b]],Out).
   
test("test 3",true(Out == [f, a])) :-
   flatwalker([[[[a]]],b,c,d,e,[f]],Out).

test("test 4",true(Out == [f, a, b, c])) :-
   flatwalker([[[[a]],b,[c]],d,e,[f]],Out).
   
:- end_tests(flatwalker).

And so:

?- run_tests.
% PL-Unit: flatwalker 
% Got : []
.
% Got : []
.
% Got : []
.
% Got : [1-a,1-b,1-c,1-d,1-e]
.
% Got : [1-a,1-b]
.
% Got : [3-a,1-f]
.
% Got : [3-a,1-b,2-c,1-f]
ERROR: flatwalker.pl:66:
        test test 4: wrong answer (compared using ==)
ERROR:     Expected: [f,a,b,c]
ERROR:     Got:      [b,f,c,a]
 done
% 1 test failed
% 6 tests passed
false.