type ordering = LT | EQ | GT;;

module type ORDER =
  sig
    type t
    val compare: t -> t -> ordering
  end;;


module StringOrder: ORDER with type t = string =
  struct
    type t = string
    let compare s1 s2 = if s1<s2 then LT else
                          if s1>s2 then GT else EQ
  end;;

module IntOrder: ORDER with type  t = int =
  struct
    type  t = int
    let compare i1 i2 = if i1<i2 then LT else
                          if i1>i2 then GT else EQ
  end;;


module type DICTIONARY =
  sig
    type key
    (* type of keys *)
    type 'a t
    (* type of dictionaries *)
    exception DuplicatedKey of key
    (* error in insert *)
    val empty: unit -> 'a t
    (* empty dictionary *)
    val lookup: 'a t -> key -> 'a option
    val insert: 'a t -> key * 'a -> 'a t
    val delete: 'a t -> key -> 'a t
    val update: 'a t -> key * 'a -> 'a t
  end;;

module Dictionary (Key : ORDER) : DICTIONARY with type key = Key.t =
  struct
    type key = Key.t
    type 'a t = (key * 'a) list
    exception DuplicatedKey of key

    let empty() = []

    let rec lookup xs key =
      match xs with
        (k, v)::t -> (match Key.compare key k with
                        LT -> None
                      | EQ -> Some v
                      | GT -> lookup t key)
      | [] -> None

    let rec insert xs (key, value) =
      match xs with
        (k, v)::t as l -> (match Key.compare key k with
                             LT -> (key, value)::l
                           | EQ -> raise (DuplicatedKey key)
                           | GT -> (k, v)::(insert t (key, value)))
      | [] -> [key, value]

    let rec delete xs key =
      match xs with
        (k, v)::t as l -> (match Key.compare key k with
                             LT -> l
                           | EQ -> t
                           | GT -> (k, v)::(delete t key))
      | [] -> []

    let rec update xs (key, value) =
      match xs with
        (k, v)::t as l -> (match Key.compare key k with
                        LT -> (key, value)::l
                      | EQ -> (key, value)::t
                      | GT -> (k, v)::(update t (key, value))
                     )
      | [] -> [key, value]
  end;;


module StringDict = Dictionary(StringOrder);;

module IntDict = Dictionary(IntOrder);;

StringDict.lookup
  (StringDict.insert
     (StringDict.insert
        (StringDict.empty())
        ("a", 10))
     ("b", 20))
  "a";;

IntDict.lookup
  (IntDict.insert
     (IntDict.insert
        (IntDict.empty())
        (1, "jeden"))
     (2, "dwa"))
  1;;

let ( <| ) d (k,x) = StringDict.update d (k,x);;

let dict = StringDict.empty();;

let dict = dict <| ("kot", "cat")
           <| ("slon", "elephant")
           <| ("pies", "dog")
           <| ("ptak", "bird");;

StringDict.lookup dict "kot";;

StringDict.lookup (StringDict.update dict ("kot", "kotek")) "kot" ;;

let dict = StringDict.delete dict "ptak";;

StringDict.lookup dict "pies";;