如何获取此树中的叶子列表？ OCaml中的问题

Question

我们得到一个类型为的树：

type ('nonterminal, 'terminal) parse_tree =
  | Node of 'nonterminal * ('nonterminal, 'terminal) parse_tree list
  | Leaf of 'terminal

和形式：

let t = (Node ("+", [Leaf 3; Node ("*", [Leaf 4; Leaf 5])])

并且我们被要求编写一个函数，该函数将树作为参数并返回它找到的叶子列表（从左到右），所以留下t = [3; 4; 5]

现在这就是我所拥有的，但它给了我一个错误，我不确定我应该如何解决这个问题：

let rec getleaf tree = 
  match tree with
  |Leaf a -> [a]
  | Node (a, Leaf (h)::t) -> h::getleaf t;;

先感谢您。

Answer 1

列表模式h :: t将h绑定到列表的头部（单个元素），将t绑定到列表的尾部（它本身就是一个列表）。因此，代码中的名称t将匹配解析树列表。但getleaf期待一个单一的解析树作为其论据。

更新

通常要做的就是让getleaf接受一棵树。在Node的代码中，您必须具有任意数量的递归调用，然后组合这些调用以生成该一个节点的结果。

处理多个递归调用的最惯用的方法是使用折叠（恕我直言）。你也可以使用List.map（它会给出一个列表列表），然后使用List.concat来回到单个列表。这更容易思考（恕我直言），但它做了一些不必要的计算。

您可能想要考虑是否需要维护叶子的顺序。