exercises/ch01/tree.ml

   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")