I am looking for a review of my Binary Tree Zipper implementation on Ocaml. These are the defined operations:
- get (gets the substructure, or the trees after the focus element)
- bempty creates an empty BTZ (binary tree zipper)
- bnext
- bprev
- bdown
- bup
- bupdate
- bremove
- to_btree (BTZ to binary tree)
- from_btree (binary tree to BTZ)
module type BTreeZipper =
sig
type 'a bin_tree
type 'a context
type 'a btree_zipper
exception EmptyZT
val get : 'a btree_zipper -> 'a bin_tree (* returns the sublist starting at focus position*)
val bempty : 'a btree_zipper
val bnext : 'a btree_zipper -> 'a btree_zipper
val bprev : 'a btree_zipper -> 'a btree_zipper
val bdown : 'a btree_zipper -> 'a btree_zipper
val bup : 'a btree_zipper -> 'a btree_zipper
val bupdate : 'a btree_zipper -> 'a bin_tree -> 'a btree_zipper
val bremove : 'a btree_zipper -> 'a btree_zipper
val from_btree : 'a bin_tree -> 'a btree_zipper
val to_btree : 'a btree_zipper -> 'a bin_tree
end
module BTreeZipper1 : BTreeZipper =
struct
type 'a bin_tree = | Leaf | Node of 'a * 'a bin_tree * 'a bin_tree
type 'a context = | Top | Context of 'a bin_tree * 'a * 'a context * 'a bin_tree
type 'a btree_zipper = BTZ of 'a context * 'a bin_tree
exception EmptyZT
let get (BTZ(c, t)) = t
let bempty : 'a btree_zipper = BTZ(Top, Leaf)
let bnext (BTZ(c, t)) =
match c with
| Top -> failwith "root: no right"
| Context(left, v, up, Leaf) -> failwith "no right"
| Context(left, v, up, right) -> BTZ (Context(t, v, up, right), right)
let bprev (BTZ(c, t)) =
match c with
| Top -> failwith "root: no left"
| Context(Leaf, v, up, right) -> failwith "no left"
| Context(left, v, up, right) -> BTZ(Context (left, v, up, t), left)
let bdown (BTZ(c, t)) =
match t with (* go to left child *)
| Leaf -> raise EmptyZT (* (BTZ(c, Leaf) => c = Top) => BTZ(Top, Leaf) = bempty*)
| Node(_,Leaf, Leaf) -> failwith "leaf: no children"
| Node(v,l,r) -> BTZ (Context(Leaf, v, c, r), l)
let bup (BTZ(c, t)) =
match c with
| Top -> failwith "root: no parent"
| Context(l, v, u, r) -> BTZ (u, Node(v, l, r))
let bupdate (BTZ(c, t)) t1 = BTZ(c, t1)
let bremove (BTZ(c, t)) =
match c with
| Top -> failwith "remove on top"
| Context(Leaf,v,u,Leaf) -> BTZ(u, Node(v, Leaf, Leaf)) (*has no right or left*)
| Context(l,v,u, Leaf) -> BTZ(Context(Leaf,v,u,Leaf), l) (*has left*)
| Context(l,v,u,r) -> BTZ(Context(Leaf,v,u,Leaf), r) (*has right*)
let from_btree t = BTZ (Top, t)
let rec to_btree btz =
match btz with
| BTZ(Top, t) -> t
| BTZ(_,_) -> to_btree (bup btz)
end
Does it need any improvement?
Btreemodule which contains aTreemodule with the definition of a tree and operations on it, and aZippermodule. \$\endgroup\$