Prolog如何通过交织将列表的列表构造为单个列表? [英] Prolog How can I construct a list of list into a single list by interleaving?

问题描述

如何将列表的列表构造为带有交织子列表的单个列表? 像recons([[1,2 ,, [3,4]]，X)会给X = [1,3,2,4]吗? 我已经尝试了几个小时，而我的代码总是给我非常奇怪的结果或无限循环， 我的想法是这样的:

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.

推荐答案

我们可以首先考虑正确性，而不是首先考虑效率.

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( [], []).

确实

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.

有时将内部列表中的所有非列表元素(无论嵌套深度如何)收集到一个列表中(没有嵌套结构)可能会很有趣.实际上，这样的列表实际上是树，称为 flattening 或收集树的 fringe .这是一个不同的问题.

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.

这篇关于Prolog如何通过交织将列表的列表构造为单个列表?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！