Prolog How can I construct a list of list into a single list by interleaving?

Question

How can I construct a list of a list into one single list with interleaving sublists? like recons([[1,2],[3,4]],X) will give X= [1,3,2,4]? I have been trying hours and my code always gave me very strange results or infinite loop, what I thinking was something like this:

recons([[A|R],REST],List):-
    recons(R,REST),
    append(A,[R|REST],List).

I know its completely wrong, but I don`t know how to fix this.

Answer 1

Instead of thinking about efficiency first, we can think about correctness first of all.

interleaving_join( [[]|X], Y):- 
    interleaving_join( X,  Y).

that much is clear, but what else?

interleaving_join( [[H|T]|X],         [H|Y]):- 
               append(    X, [T], X2),
               interleaving_join( X2,    Y).

But when does it end? When there's nothing more there:

interleaving_join( [], []).

Indeed,

2 ?- interleaving_join([[1,2],[3,4]], Y).
Y = [1, 3, 2, 4] ;
false.

4 ?- interleaving_join([[1,4],[2,5],[3,6,7]], X).
X = [1, 2, 3, 4, 5, 6, 7] ;
false.

This assumes we only want to join the lists inside the list, whatever the elements are, like [[...],[...]] --> [...]. In particular, we don't care whether the elements might themselves be lists, or not.

It might sometimes be interesting to collect all the non-list elements in the inner lists, however deeply nested, into one list (without nesting structure). In fact such lists are actually trees, and that is known as flattening, or collecting the tree's fringe. It is a different problem.