Commit | Line | Data |
---|---|---|
f76c63f8 SK |
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") |