Lin Jiayin
Lin Jiayin

Reputation: 499

How to append a list of lists in prolog

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]

Upvotes: 1

Views: 906

Answers (4)

repeat
repeat

Reputation: 18726

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

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

Upvotes: 2

lurker
lurker

Reputation: 58244

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.

Upvotes: 1

repeat
repeat

Reputation: 18726

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

Upvotes: 1

CapelliC
CapelliC

Reputation: 60014

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

Upvotes: 0

Related Questions