How to append a list of lists in prolog

Question

I want to append a list of list like this : append(Ls,L) ,the first element of L is the first element of the first list in Ls,the second element of L is the first element of the second list in Ls, and so on for all the lists in Ls. After this, the next element of L is the second element of the first list in Ls, and so on, until two elements have been taken from all the lists in Ls. After this, come the third elements of all the lists in Ls, and so on, until all the elements of all the lists in Ls are included in L.

forexample: I have a list Ls=[[a,b],[c,d],[e,f]] and want to get this L=[a,c,e,b,d,f] or I have Ls=[[1,2,3],[4,5,6]] and I want to get L=[1,4,2,5,3,6]

Answer 1

If you want to practise implementing recursive predicates, you could proceed like this using dcg:

matrix_transposed_items(Mss,Xs) :-
   notlonger_than(Mss,Xs),
   phrase(matrix_tconcat(Mss),Xs).

matrix_tconcat([]) --> [].
matrix_tconcat([Cs|Css]) -->
   row_rows_rest_(Cs,Css,Mss),
   matrix_tconcat(Mss).

row_rows_rest_([],Css,[]) --> 
   { emptylists(Css) }.
row_rows_rest_([X|Xs],Xss,[Xs|Mss]) -->
   [X],
   nonemptyrows_rest(Xss,Mss).

nonemptyrows_rest([],[]) --> [].
nonemptyrows_rest([[X|Xs]|Xss],[Xs|Mss]) -->
   [X],
   nonemptyrows_rest(Xss,Mss).

Above code is based on three auxiliary predicates which can be defined like this:

nil_or_cons([]).
nil_or_cons([_|_]).

notlonger_than([],Bs) :-
   nil_or_cons(Bs).
notlonger_than([_|As],[_|Bs]) :-
   notlonger_than(As,Bs).

emptylists([]).
emptylists([[]|Xs]) :-
   emptylists(Xs).

Let's run some queries! First, we use some quadratic matrix:

?- matrix_transposed_items([[1,2,3],[4,5,6],[7,8,9]],Xs).
Xs = [1,4,7,2,5,8,3,6,9].                            % succeeds deterministically

Next, the non-quadratic use-cases the OP gave:

?- matrix_transposed_items([[a,b],[c,d],[e,f]],Ls).
Ls = [a,c,e,b,d,f].                                  % succeeds deterministically

?- matrix_transposed_items([[1,2,3],[4,5,6]],Ls).
Ls = [1,4,2,5,3,6].                                  % succeeds deterministically

Let's try going the "other direction", too!

?- matrix_transposed_items(Mss,[1,2,3,4,5,6,7,8,9,10]).
  Mss = [[1,2,3,4,5,6,7,8,9,10]]
; Mss = [[1,3,5,7,9],[2,4,6,8,10]]
; Mss = [[1,6],[2,7],[3,8],[4,9],[5,10]]
; Mss = [[1],[2],[3],[4],[5],[6],[7],[8],[9],[10]]
; false.                                             % terminates universally

Answer 2

This is not a relational solution, but illustrates a recursive approach to the problem:

zipflat(Lists, Result) :-
    zipflat_aux(Lists, ResultLists),
    append(ResultLists, Result).

zipflat_aux(Lists, [Heads|ZipTails]) :-
    maplist(head_tail, Lists, Heads, Tails),
    zipflat_aux(Tails, ZipTails), !.
zipflat_aux([[]|_], []).

head_tail([H|T], H, T).

The cut (!) eliminates the unneeded choice point.

Answer 3

since append/2 has a different meaning, let's call it zip/2

zip([A|As], Zip) :-
    findall(Es, (   nth1(P, A, _),
            findall(E, (member(L, [A|As]), nth1(P, L, E)), Es)
    ), Ts), append(Ts, Zip) /*flatten(Ts, Zip)*/ .

Answer 4

If you use SWI-Prolog, you can proceed like this:

?- use_module(library(clpfd),[transpose/2]).
true.

Here's the sample query the OP gave:

?- Mss=[[1,2,3],[4,5,6]], transpose(Mss,Tss), append(Tss,Xs).
Mss = [[1,2,3],[4,5,6]], Tss = [[1,4],[2,5],[3,6]], Xs = [1,4,2,5,3,6].