I am given this module type, and I am asked to create an empty tree_zipper, but I think it's not possible with the following implementation of 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
and this module struct:
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
With this implementation, is it possible to create an empty tree_zipper? Because ntree is not defined over being empty as I can see, I mean we can do something like Node(v, []), but what with v we at least have the root.
Your NTreeZipper.ntree type is abstract, so outside of the module there is no way to create a tree at all, and no, as you've correctly surmised, your tree type does not allow for an empty tree.
As for creating a to_ntree function (assuming we have a way to create an ntree in the first place), the case where the context is Top is straightforward.
let to_ntree = function
| TZ (Top, t) -> t
It's not much more complicated in the remaining case, which we can match on. You then are basically reversing the logic in from_ntree
let to_ntree = function
| TZ (Top, t) -> t
| TZ (Context (ls, v, u, rs), t) -> ...