Пролог Как я могу создать список списков в один список путем чередования?

Question

Как я могу создать список из списка в один список с чередованием подсписков? как разведки ([[1,2],[3,4]],X) даст X= [1,3,2,4]? Я пытался часами, и мой код всегда давал мне очень странные результаты или бесконечный цикл, что я думал примерно так:

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

Я знаю, что это совершенно неправильно, но я не знаю, как это исправить.

Answer 1

Вместо того, чтобы думать об эффективности в первую очередь, мы можем думать о правильности в первую очередь.

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

это ясно, но что еще?

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

Но когда это заканчивается? Когда там больше ничего нет

interleaving_join( [], []).

В самом деле,

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.

Это предполагает, что мы хотим присоединиться только к спискам внутри списка, какими бы ни были элементы, например [[...],[...]] --> [...], В частности, нам все равно, могут ли элементы быть списками или нет.

Иногда может быть интересно собрать все элементы, не входящие в список, во внутренних списках, хотя и глубоко вложенные, в один список (без структуры вложенности). На самом деле такие списки на самом деле являются деревьями, и это называется выравниванием или сбором деревьев. Это другая проблема.