list - Prolog 如何通过交错将列表列表构造成单个列表？

Question

如何将列表列表构造成一个带有交错子列表的列表？像 recons([[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.

这假设我们只想加入列表中的列表，无论元素是什么，比如[[...],[...]] --> [...]. 特别是，我们不关心元素本身是否是列表。

有时将内部列表中的所有非列表元素（无论嵌套多深）收集到一个列表中（没有嵌套结构）可能会很有趣。事实上，这样的列表实际上是树，这就是所谓的flattening或收集树的边缘。这是一个不同的问题。