module type MAP = sig
  type key
  type 'a t

  val empty : 'a t
  val add : key -> 'a -> 'a t -> 'a t
  val find : key -> 'a t -> 'a option

  val iter : (key -> 'a -> unit) -> 'a t -> unit
  val to_list : 'a t -> (key * 'a) list
end

module type ORD = sig
  type t
  val compare : t -> t -> int
end

module Make_list_map(Ord: ORD) : (MAP with type key = Ord.t) = struct
  type key = Ord.t
  
  type 'a t = (key * 'a) list

  let empty = []
  let add key data l = (key,data) :: l
  let find key l = List.assoc_opt key l
  let iter fn l = List.iter (fun (k,v) -> fn k v) l
  let to_list l = l
end

module Make_tree_map(Ord: ORD) : (MAP with type key = Ord.t) = struct
  type key = Ord.t

  type 'a t = Empty | Node of key * 'a * 'a t * 'a t

  let empty = Empty

  let rec add k v = function
    | Empty -> Node (k, v, Empty, Empty)
    | Node (key, value, l, r) ->
      match Ord.compare k key with
      | 0 -> Node (k, v, l, r)
      | n when n < 0 -> Node (key, value, add k v l, r)
      | _ -> Node (key, value, l, add k v r)

  let rec find k = function
    | Empty -> None
    | Node (key, value, left, right) ->
      match Ord.compare k key with
      | 0 -> Some value
      | n when n < 0 -> find k left
      | _ -> find k right 

  let rec iter f = function
    | Empty -> ()
    | Node (key, value, left, right) ->
      iter f left;
      f key value;
      iter f right 

  let rec to_list = function
    | Empty -> []
    | Node (key, value, left, right) ->
      to_list left @ [(key, value)] @ to_list right
end

module Fruit = struct
  type t =
    | Apple
    | Pear
    | Kiwi

  let to_string = function
    | Apple -> "apple"
    | Pear -> "pear"
    | Kiwi -> "kiwi"

  let compare a b = String.compare (to_string a) (to_string b)
end

module Age : sig
  type t = private int
  val v : int -> t
  val compare : t -> t -> int
end = struct
  type t = int
  let v age = min (max age 10) 100
  let compare a b = a - b
end  

module FruitTree = Make_tree_map(Fruit)
module FruitList = Make_list_map(Fruit)
module AgeTree   = Make_tree_map(Age)
module AgeList   = Make_list_map(Age)