创建一个空树拉链，但是树没有定义为空

Question

我得到了这个模块类型，我被要求创建一个空的

tree_zipper

，但我认为树拉链的以下实现是不可能的：

module type TREE_ZIPPER = 
  sig
  type 'a ntree
  type 'a context
  type 'a tree_zipper
  val previous_exn : 'a tree_zipper -> 'a tree_zipper
  val next_exn : 'a tree_zipper -> 'a tree_zipper
  val up_exn : 'a tree_zipper -> 'a tree_zipper
  val down_exn : 'a tree_zipper -> 'a tree_zipper
  val update :'a tree_zipper -> 'a ntree -> 'a tree_zipper
  val insert_exn : 'a tree_zipper -> 'a ntree -> 'a tree_zipper
  val insert_down_exn : 'a tree_zipper -> 'a ntree -> 'a tree_zipper
  val insert_prev_exn : 'a tree_zipper -> 'a ntree -> 'a tree_zipper
  val insert_next_exn : 'a tree_zipper -> 'a ntree -> 'a tree_zipper
  val remove_exn : 'a tree_zipper -> 'a tree_zipper
  val from_ntree : 'a ntree -> 'a tree_zipper
end

这个模块结构：

module NTreeZipper : TREE_ZIPPER = 
  struct
    type 'a ntree = Node of 'a * 'a ntree list
    type 'a context = | Top | Context of 'a ntree list * 'a * 'a context * 'a ntree list
    type 'a tree_zipper = TZ of 'a context * 'a ntree
    let previous_exn (TZ(c,t)) = (* on the left, not possible when context is top or left = []*)
      match c with
      | Top -> failwith "root: no left"
      | Context([], v, up, right) -> failwith "left of first child"
      | Context(l::left, v, up, right) -> TZ(Context (left, v, up, t::right), l)
      (* TZ (Context ([], "+", Top, [Node ("*", [Node ("c", []); Node ("d", [])])]),
      Node ("*", [Node ("a", []); Node ("b", [])])) *)
    let next_exn (TZ(c,t)) = (* on the right, not possible when context is top or right = []*)
      match c with
      | Top -> failwith "root: no right"
      | Context(left, v, up, []) -> failwith "right of last child" (*explain*)
      | Context(left, v, up, r::right) -> TZ (Context(t::left, v, up, right), r)
    let down_exn (TZ(c,t)) = 
      match t with (* go to first child *)
      | Node(_,[]) -> failwith "leaf: no children"
      | Node(v,d::ds) -> TZ (Context([],v, c,ds), d)
    let up_exn (TZ(c,t)) = 
      match c with
      | Top -> failwith "root: no parent"
      | Context(l, v, u,r) -> TZ (u, Node(v, (List.rev_append l (t::r))))
    let update (TZ(c,_)) t = TZ(c,t)
    let insert_exn (TZ(c,t)) t1 = (* in-place insert; t1 is a node *)
      match c with
      | Top -> failwith "insert on top"
      | Context (ls, v, u, rs) -> TZ (Context (ls, v, u, t::rs), t1)
    let insert_prev_exn (TZ(c,t)) t1 = 
      match c with
      | Top -> failwith "insert_prev on top"
      | Context(ls, v, u, rs) -> TZ (Context(t1::ls, v, u, rs), t);;
    let insert_next_exn (TZ(c,t)) t1 = 
      match c with
      | Top -> failwith "insert_next on top"
      | Context(ls, v, u, rs) -> TZ(Context(ls, v, u, t1::rs), t)
    (* move down and insert *)
    let insert_down_exn (TZ(c,t)) t1 = 
      match t with
      | Node (_,[]) -> failwith "insert_down on leaf"
      | Node(v,l) -> TZ(Context([],v, c,l), t1)
    (*Remove the focused subtree, and move to the right if possible, else to the left, else upward:*)
    let remove_exn (TZ(c,_)) = (*logic: if right put focus there, else if !right then focus in left, else up*) 
      match c with 
      | Top -> failwith "remove of top"
      | Context(ls,v,u,r::rs) -> TZ(Context(ls,v,u,rs), r) (*has right*)
      | Context(l::ls,v,u,[]) -> TZ(Context(ls,v,u,[]), l) (*has left*)
      | Context([],v,u,[]) -> TZ(u, Node(v,[])) (*has no right or left, [] is the t removed*)
    let from_ntree t = TZ (Top,t)
  end

有了这个实现，是否可以创建一个空的

tree_zipper

？因为

ntree

没有像我所看到的那样定义为空，我的意思是我们可以做像

Node(v, [])

这样的事情，但是对于

v

我们至少有根。

Answer 1

您的

NTreeZipper.ntree

类型是抽象的，因此在模块之外根本无法创建树，而且不，正如您目前推测的那样，您的树类型不允许空树。