tree - OCaml 选项值树

Question

我的任务是编写一个 'a btree -> 'a option list 类型的函数，该函数将给定的树存储在 'a option 类型的元素列表中code> 按后缀顺序(postorder)。

内部节点将由None表示，值为x的外部节点(叶子)将由Some x表示。

到目前为止，叶子的操作很容易，但是如何将其放入'a选项列表中？

type 'a btree = L of 'a | N of 'a btree * 'a btree ;;

let rec store t =
    match t with
        | L x -> Some x
        | N (a,b) -> None ???   
;;

我知道的第二个匹配案例是不正确的，但是如何解决它？

Answer 1

如果您查看第一个案例，您会发现它也不完全存在；它返回'a option，但您希望该函数返回'a option list。

显然您将返回一个列表，因此首先修复该问题:

let rec store = function
  | L x -> [Some x]
  | N (a,b) -> [None] (* ??? *)

现在让我们修复第二种情况；我们想要将 None 附加到我们的输出中，但在此之前，我们需要子树的节点:

let rec store = function
  | L x -> [Some x]
  | N (a,b) -> (store a) @ (store b) @ [None]

@ 具有类型

'a list -> 'a list -> 'a list

即它将列表连接在一起。我们想要连接左子树的结果列表，然后是右子树，最后是这个内部节点的结果。