2
\$\begingroup\$

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?

\$\endgroup\$
3
  • 1
    \$\begingroup\$ Currently binary trees are an abstract type, and cannot be created. \$\endgroup\$ Commented Apr 25, 2023 at 22:54
  • 1
    \$\begingroup\$ I might suggest a Btree module which contains a Tree module with the definition of a tree and operations on it, and a Zipper module. \$\endgroup\$ Commented Apr 25, 2023 at 22:55
  • \$\begingroup\$ Thanks, that s a good point. \$\endgroup\$ Commented Apr 25, 2023 at 23:04

1 Answer 1

4
\$\begingroup\$

Abstract types

Because you have constrained BTreeZipper1 with the BTreeZipper signature, where no details about type 'a bin_tree are specified, 'a BTreeZipper1.bin_tree is an abstract type. Thus no actual trees can be constructed by the user of this module.

This makes the entire exercise rather fruitless.

To repair this you either need to make this type not abstract, or offer functions which form an interface for the creation and manipulation of binary trees.

If the tree is meant to be a binary search tree, then having it be an abstract type makes the most sense, because your interface can ensure the sorting invariant, and if you wish to put in the work, that the tree remains balanced, which is key to efficiency.

\$\endgroup\$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.