list - 在 Prolog 中将普通树转换为列表

Question

所以我正在学习编程范式类(class)，我们正在学习 Prolog。最后一个练习是将一般的树结构展平为列表。一般来说，这意味着每个节点可以分支任意次数。以下是定义树的一组事实和规则:

leaf(_).
gnode([]).
gnode([leaf(_)|T]):-
    gnode(T).
gnode([gnode(X)|T]):-
    gnode(X),
    gnode(T).

因此，我的解决方案 gtree_list 需要返回叶子中的元素，或者在 gnode 的情况下返回一个列表(这些都应该计算为正确):

gtree_list(leaf(example),example).

gtree_list(gnode( [leaf(5),leaf(4)] ), [5,4]).

gtree_list(gnode( [gnode( [leaf(5)] ),leaf(4)] ), [[5],4]).

gtree_list(gnode( [] ), [] ).

所以 leaf 是元素，gnode 是列表。我当前的实现是这样的:

gtree_list( leaf( L), L ).
gtree_list( gnode( []), [] ).
gtree_list( gnode( [X|Y]), R ):-
    gtree_list( X, R1 ),
    gtree_list( gnode(Y), R2 ),
    append( [R1], R2, R ).

它将所有示例评估为真实，因此一切都很好。我的问题是，当我要求它从嵌套列表中创建树时，它失败了。所以，我剩下以下内容:

gtree_list(gnode( [gnode( [leaf(5) ]),leaf(4) ]), [ [5],4 ]). 

评估结果为真，

gtree_list(gnode( [gnode( [leaf(5)]),leaf(4) ]),X). 

返回X=[[5],4]，但是

gtree_list( X, [[5],4] ). 

无法生成正确的树。它从最简单的到最复杂的构建，所以它是:

X = leaf( [[5],4] ); 
X = gnode( [leaf([5]), leaf(4)] ); 

然后我希望它返回X = gnode( [gnode([leaf(5)]), leaf(4)] )，但它从来没有这样做。在任何树中，在经历了所有可能的解决方案之后，它都会无限循环，这是预期的，但显然我的递归无法弄清楚如何对嵌套列表进行逆向工程，这是一个要求。

我错过了什么？

Answer 1

内联append，第二个参数也有机会指导推理:

gtree_list( leaf( L), L ).
gtree_list( gnode( []), [] ).
gtree_list( gnode( [X|Y]), [R1|R2] ):-
    gtree_list(     X,      R1    ),
    gtree_list( gnode(Y),      R2 ).

这似乎使它起作用:

2 ?- gtree_list( gnode( [gnode( [leaf(5) ]), leaf(4)]), [ [5], 4]). 
true ;
false.

3 ?- gtree_list( gnode( [gnode( [leaf(5)]), leaf(4)]), X). 
X = [[5], 4] ;
false.

4 ?- gtree_list( X, [[5], 4]). 
X = leaf([[5], 4]) ;
X = gnode([leaf([5]), leaf(4)]) ;
X = gnode([gnode([leaf(5)]), leaf(4)]) ;
false.