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.