Append list of lists elements in Prolog

Question

I'm learning Prolog for about a week, so I'm a newbie. I'm trying to do a function, that appends, the elements of a list of lists.

So the input would be: [ [[a,b,c],[g,h,i]], [[j,k,l],[m,n,o]], [[s,t,u],[v,w,x]] ].

And the output would be : [ [a,b,c,j,k,l,s,t,u], [g,h,i,m,n,o,v,w,x] ].

Or

Input: [ [[a,b], [c,d]], [[e,f], [g,h]], [[i,j],[k,l]] ].

Output: [ [a,b,e,f,i,j], [c,d,g,h,k,l] ].

It would be important, that it has to work with a lot of elements, not only 3. I wrote this, but it only works with 2 elements, so i can only do it, with pairs.

merge([],[],[]).
merge(L1,[],L1).
merge([H1|T1],[H2|T2],LL):-
   append(H1, H2, HE),
   merge(T1,T2,TE),
   append([HE], TE, LL).

Questions: 1) Is the input a single list with lists of two lists? 2) Do you know that the lists of lists are all of the length 2? — user1812457
So at the end, if the first argument is a list of n lists, each with m sublists in it, the result will be a list with m sublists? — user1812457
BTW, is this a general Prolog question or is it somehow specific to SICSTUS? — user1812457

Unknown Unknown · Accepted Answer · 2016-10-10T11:46:38

If I understand your question correctly...

First, if you know that your input has exactly two levels of nesting in it, and if your Prolog had higher-order predicates for mapping and for folding, and if you could compose them, you could simply write:

merge_foldl([], []).
merge_foldl([X|Xs], R) :-
    reverse([X|Xs], [Y|Ys]),
    foldl(maplist(append), Ys, Y, R).

This works as expected for SWI-Prolog. Here it is with your two examples:

?- merge_foldl([ [[a,b,c],[g,h,i]], [[j,k,l],[m,n,o]], [[s,t,u],[v,w,x]] ], R).
R = [[a, b, c, j, k, l, s, t, u], [g, h, i, m, n, o, v, w, x]].

?- merge_foldl([ [[a,b], [c,d], [e,f]], [[g,h], [i,j], [k,l]] ], R).
R = [[a, b, g, h], [c, d, i, j], [e, f, k, l]].

If you don't have access to neither foldr nor foldl, you would have to hardcode the folding:

merge([], []).
merge([X|Xs], Result) :-
    merge_maplist(Xs, X, Result).

merge_maplist([], Result, Result).

This is not all, but it says that if you are at the end of the list of lists, the last element is the result.

Now you have to define the step where you append to the front of each sublist. This is easier with maplist:

merge_maplist([X|Xs], Prev, Result) :-
    merge_maplist(Xs, X, Result0),
    maplist(append, Prev, Result0, Result).

Note that here we are "emulating" a right fold by using a non-tail-recursive definition: we are doing the appending in reverse, after the recursive step. For a tail-recursive definition (identical to hard-coded left fold), you would have to reverse the original list first!

So you keep on peeling off one list of lists from your input until you are done. Then, you use maplist to apply append/3 to each pair of lists from the previous element and the result so far, to get the final result.

If you don't have access to maplist either, you'd have to hardcode the mapping as well. For the three arguments that append/3 takes:

map_append([], [], []).
map_append([X|Xs], [Y|Ys], [Z|Zs]) :-
    append(X, Y, Z),
    map_append(Xs, Ys, Zs).

and your merge/2 and merge_/3 become:

merge([], []).
merge([X|Xs], Result) :-
    merge_(Xs, X, Result).

merge_([], Result, Result).
merge_([X|Xs], Prev, Result) :-
    merge_(Xs, X, Result0),
    map_append(Prev, Result0, Result).

This is a lot of code for something that can be solved quite nicely if you have higher-order predicates.

Append list of lists elements in Prolog

1 Answers