| 1 | module Array = ArrayLabels |
| 2 | |
| 3 | module type TREE = sig |
| 4 | type 'a t |
| 5 | |
| 6 | val empty : 'a t |
| 7 | |
| 8 | val add : 'a t -> 'a -> 'a t |
| 9 | |
| 10 | val member : 'a t -> 'a -> bool |
| 11 | end |
| 12 | |
| 13 | module BinaryTree : TREE = struct |
| 14 | type 'a t = |
| 15 | | Node of 'a * 'a t * 'a t |
| 16 | | Leaf |
| 17 | |
| 18 | let empty = Leaf |
| 19 | |
| 20 | let rec add t x = |
| 21 | match t with |
| 22 | | Leaf -> Node (x, Leaf, Leaf) |
| 23 | | Node (x', left, right) when x < x' -> Node (x', add left x, right) |
| 24 | | Node (x', left, right) when x > x' -> Node (x', left, add right x) |
| 25 | | (Node _) as t' -> t' |
| 26 | |
| 27 | let rec member t x = |
| 28 | match t with |
| 29 | | Leaf -> false |
| 30 | | Node (x', left, _) when x < x' -> member left x |
| 31 | | Node (x', _, right) when x > x' -> member right x |
| 32 | | Node _ -> true |
| 33 | end |
| 34 | |
| 35 | let () = |
| 36 | let tree = |
| 37 | Array.fold_left |
| 38 | (Sys.argv) |
| 39 | ~init:BinaryTree.empty |
| 40 | ~f:(fun t str -> BinaryTree.add t str) |
| 41 | in |
| 42 | Printf.printf "%B\n" (BinaryTree.member tree "a") |