Ocaml list to tree

Question

我想寫一個函數load: 'a option list -> 'a tree，它從給定的列表中恢復二叉樹，它包含後綴順序中的元素。 如果列表不代表任何樹，你的函數應該引發異常 加載（你必須先聲明它）。

樹被定義爲：

type ‘a btree = L of ‘a | N of ‘a btree * ‘a btree 

到目前爲止，我所做的就是：

exception Load ;; 

let rec load l = 
    match l with 
     | [] -> raise Load 
     | Some x::_ -> L x 
     | None::t -> N(?,load t) 
;; 

下面是一個輸入列表的一個例子：

[Some 2; Some 0; None; Some 5; Some 9; Some 20; None; None; None] 

這有點棘手怎麼做。由於該列表是在後綴順序，我想知道是否會更好地使用List.foldright函數？

Answer 1

我想你應該更努力做功課（當然有一些有趣的學習），但你顯然不關心：

let load input = 
    let rec load stack = function 
    | [] -> stack 
    | Some elem :: rest -> load (L elem :: stack) rest 
    | None :: rest -> 
     match stack with 
     | right :: left :: stack -> load (N(left, right) :: stack) rest 
     | [] | [_] -> failwith "incorrect node arity" 
    in 
    match load [] input with 
    | res :: [] -> res 
    | [] -> failwith "no input" 
    | _ :: _ :: _ -> failwith "remaining nodes"