Implement balanced binary tree and refactor

[tiger.ml.git] / exercises / ch01 / tree.ml

diff --git a/exercises/ch01/tree.ml b/exercises/ch01/tree.ml
index 6b0ab43..521b6cf 100644 (file)
--- a/exercises/ch01/tree.ml
+++ b/exercises/ch01/tree.ml
@@ -1,6 +1,4 @@
-module Array = ArrayLabels
-
-module type TREE = sig
+module type S = sig
   type ('k, 'v) t
 
   val empty : ('k, 'v) t
@@ -10,49 +8,6 @@ module type TREE = sig
   val get : ('k, 'v) t -> k:'k -> 'v option
 
   val member : ('k, 'v) t -> k:'k -> bool
-end
-
-module BinaryTree : TREE = struct
-  type ('k, 'v) t =
-    | Node of 'k * 'v * ('k, 'v) t * ('k, 'v) t
-    | Leaf
-
-  let empty = Leaf
 
-  let rec set t ~k ~v =
-    match t with
-    | Leaf -> Node (k, v, Leaf, Leaf)
-    | Node (k', v', l, r) when k < k' -> Node (k', v', set l ~k ~v, r)
-    | Node (k', v', l, r) when k > k' -> Node (k', v', l, set r ~k ~v)
-    | Node (k, _, l, r) -> Node (k, v, l, r)
-
-  let rec get t ~k =
-    match t with
-    | Leaf -> None
-    | Node (k', _, l, _) when k < k' -> get l ~k
-    | Node (k', _, _, r) when k > k' -> get r ~k
-    | Node (_, v, _, _) -> Some v
-
-  let rec member t ~k =
-    match t with
-    | Leaf -> false
-    | Node (k', _, l, _) when k < k' -> member l ~k
-    | Node (k', _, _, r) when k > k' -> member r ~k
-    | Node _ -> true
+  val to_dot : ('k, 'v) t -> k_to_string:('k -> string) -> string
 end
-
-let () =
-  let tree_a = BinaryTree.empty in
-  let tree_a = BinaryTree.set tree_a ~k:"k1" ~v:"v1" in
-  let tree_a = BinaryTree.set tree_a ~k:"k2" ~v:"v2" in
-  assert (BinaryTree.member tree_a ~k:"k1");
-  assert (BinaryTree.member tree_a ~k:"k2");
-  assert (Some "v1" = BinaryTree.get tree_a ~k:"k1");
-  assert (Some "v2" = BinaryTree.get tree_a ~k:"k2");
-  let tree_b =
-    Array.fold_left
-      (Sys.argv)
-      ~init:BinaryTree.empty
-      ~f:(fun t k -> BinaryTree.set t ~k ~v:())
-  in
-  Printf.printf "%B\n" (BinaryTree.member tree_b ~k:"a")