-module Array = ArrayLabels
+module type S = sig
+ type ('k, 'v) t
-module type TREE = sig
- type 'a t
+ val empty : ('k, 'v) t
- val empty : 'a t
+ val set : ('k, 'v) t -> k:'k -> v:'v -> ('k, 'v) t
- val add : 'a t -> 'a -> 'a t
+ val get : ('k, 'v) t -> k:'k -> 'v option
- 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
+ val member : ('k, 'v) t -> k:'k -> bool
- 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
+ val to_dot : ('k, 'v) t -> k_to_string:('k -> string) -> string
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")