收集一般树的叶子

Question

我正在尝试编写一个谓词 leaves/2 来收集 Prolog 中一般树中的所有叶子。我有一个类似的二叉树谓词，但我一直在尝试将其概括为多路树或一般树（其中一个节点可以有无限数量的子节点）。这是一个二叉树（其中叶节点由 l(_) 表示）：

leaves( l(X), [X|T], T ).
leaves( tree(L,R), A, C ) :-
  leaves(L,A,B),
  leaves(R,B,C).
leaves(Tree,L) :-
  leaves(Tree,L,[]).

查询

leaves(tree(tree(l(3),l(2)),l(6)),Leaves)

正确returns

Leaves = [3,2,6]

当我尝试将其概括为多路树时，我陷入了一个节点包含整个树列表的事实。我曾尝试递归 'unpack' 这样的树列表，然后使用上述谓词的变体逐渐处理它，但它不起作用，因为我发现很难将树列表与节点隔离以便处理它分开。

因此，通用树可以表示一个句子，其中每个节点包含一个句法类别，而叶子包含实际的单词，如下所示：

tree( s, [ tree(np,[l(the),l(dog)]), tree(vp,[l(barks)]) ] )

以这个通用树作为参数的类似查询应该会产生 Leaves=[the,dog,barks]。我试图找到一个与二叉树风格相同的实现，而不使用 append/2、DCG 或类似的东西。

Answer 1

可能的解决方案如下：

leaves(Tree, Leaves) :-
    leaves(Tree, [], Leaves).
  
leaves(l(X), L, [X|L]).

leaves(tree(_, Children), L0, L) :-
    leaves(Children, L0, L).

leaves([], L, L).

leaves([Child|Children], L0, L) :- 
    leaves(Children, L0, L1),
    leaves(Child, L1, L).

示例：

?- leaves(tree(s, [tree(np, [l(the), l(dog)]), tree(vp, [l(barks)])]), Leaves).
Leaves = [the, dog, barks].

收集一般树的叶子

Collect leaves in general tree

tree

prolog