Complete 1.01.e.1.a - binary tree member

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

diff --git a/exercises/ch01/tree.ml b/exercises/ch01/tree.ml
new file mode 100644 (file)
index 0000000..7cc7d8c
--- /dev/null
+++ b/exercises/ch01/tree.ml
@@ -0,0 +1,42 @@
+module Array = ArrayLabels
+
+module type TREE = sig
+  type 'a t
+
+  val empty : 'a t
+
+  val add : 'a t -> 'a -> 'a t
+
+  val member : 'a t -> 'a -> bool
+end
+
+module BinaryTree : TREE = struct
+  type 'a t =
+    | Node of 'a * 'a t * 'a t
+    | Leaf
+
+  let empty = Leaf
+
+  let rec add t x =
+    match t with
+    | Leaf -> Node (x, Leaf, Leaf)
+    | Node (x', left, right) when x < x' -> Node (x', add left x, right)
+    | Node (x', left, right) when x > x' -> Node (x', left, add right x)
+    | (Node _) as t' -> t'
+
+  let rec member t x =
+    match t with
+    | Leaf -> false
+    | Node (x', left, _) when x < x' -> member left x
+    | Node (x', _, right) when x > x' -> member right x
+    | Node _ -> true
+end
+
+let () =
+  let tree =
+    Array.fold_left
+      (Sys.argv)
+      ~init:BinaryTree.empty
+      ~f:(fun t str -> BinaryTree.add t str)
+  in
+  Printf.printf "%B\n" (BinaryTree.member tree "a")