function - Ocaml 树函数

Question

我有一棵包含两个元素的树。由以下数据结构定义：

type ('a,' b) tree =
      empty
    | node of 'a * (' a, 'b) tree sheet;;
    | node of 'b * (' a, 'b) tree sheet;;

现在我必须编写一个函数 split: ('a,' b) tree -> 'a sheet *' b list，它会覆盖第一个列表中的所有元素节点 a 和第二个列表中的所有元素节点 b。

Answer 1

您的代码不正确，所以我假设您的树类型是：

type ('a, 'b) tree =
| Empty
| AlphaNode of 'a * ('a, 'b) tree
| BetaNode of 'b * ('a, 'b) tree

let split tree =
let rec split_ tree a b = match tree with
| Empty -> (a, b)
| AlphaNode (sheet, tree) -> split_ tree (sheet::a) b
| BetaNode (sheet, tree) -> split_ tree a (sheet::b) in
split_ tree [] [];;

split_ 函数只是为了便于阅读和方便。没有它，您每次都必须使用两个空列表进行调用。