From f76c63f8cff09c1de6619d49e0a761e3bb6c8618 Mon Sep 17 00:00:00 2001
From: Siraaj Khandkar <siraaj@khandkar.net>
Date: Tue, 17 Apr 2018 23:57:14 -0400
Subject: [PATCH] Complete 1.01.e.1.a - binary tree member

---
 README.md                 |  4 ++--
 exercises/ch01/.gitignore |  1 +
 exercises/ch01/Makefile   |  4 +++-
 exercises/ch01/tree.ml    | 42 +++++++++++++++++++++++++++++++++++++++
 exercises/ch01/tree.mli   |  0
 5 files changed, 48 insertions(+), 3 deletions(-)
 create mode 100644 exercises/ch01/tree.ml
 create mode 100644 exercises/ch01/tree.mli

diff --git a/README.md b/README.md
index f711a2e..97ae9f6 100644
--- a/README.md
+++ b/README.md
@@ -16,8 +16,8 @@ Project Plan
 | [x]    | 1.01.p     | --- Program                              | 002   | --       | --     | 2018-04-16 | ---------- |
 | [x]    | 1.01.p.1   | ---- interpreter: maxargs                | ---   | --       | --     | 2018-04-17 | 2018-04-17 |
 | [x]    | 1.01.p.2   | ---- interpreter: interp                 | ---   | --       | --     | 2018-04-17 | 2018-04-17 |
-| [ ]    | 1.01.e     | --- Exercises                            | 002   | --       | --     | ---------- | ---------- |
-| [ ]    | 1.01.e.1.a | ---- tree member                         | ---   | --       | --     | ---------- | ---------- |
+| [-]    | 1.01.e     | --- Exercises                            | 002   | --       | --     | ---------- | ---------- |
+| [x]    | 1.01.e.1.a | ---- tree member                         | ---   | --       | --     | ---------- | ---------- |
 | [ ]    | 1.01.e.1.b | ---- tree key/val                        | ---   | --       | --     | ---------- | ---------- |
 | [ ]    | 1.01.e.1.c | ---- demo unbalanced behaviour           | ---   | --       | --     | ---------- | ---------- |
 | [ ]    | 1.01.e.1.d | ---- find functional balanced tree       | ---   | --       | --     | ---------- | ---------- |
diff --git a/exercises/ch01/.gitignore b/exercises/ch01/.gitignore
index 9622b7e..626a10c 100644
--- a/exercises/ch01/.gitignore
+++ b/exercises/ch01/.gitignore
@@ -1 +1,2 @@
 straight_line_program_interpreter
+tree
diff --git a/exercises/ch01/Makefile b/exercises/ch01/Makefile
index 65c4991..0dc75b0 100644
--- a/exercises/ch01/Makefile
+++ b/exercises/ch01/Makefile
@@ -5,7 +5,9 @@ OCAMLC_BYTE    := ocamlc.opt   $(OCAMLC_OPTIONS)
 
 .PHONY: build clean
 
-build : straight_line_program_interpreter
+build : \
+	straight_line_program_interpreter \
+	tree
 
 %: %.ml %.cmo %.cmi
 	$(OCAMLC_BYTE) -o $@ $*.cmo
diff --git a/exercises/ch01/tree.ml b/exercises/ch01/tree.ml
new file mode 100644
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")
diff --git a/exercises/ch01/tree.mli b/exercises/ch01/tree.mli
new file mode 100644
index 0000000..e69de29
-- 
2.20.1