open List

module type Map = sig
  type ('a,'b) t 
  val empty : ('a,'b) t 
  val update : ('a,'b) t -> 'a -> 'b -> ('a,'b) t
  val get_keys : ('a,'b) t -> 'a list
  val get : ('a,'b) t -> 'a -> 'b option
  val string_of_map : 
       ('a -> string) -> ('b -> string) -> ('a,'b) t -> string
end

module ListMap = struct
  type ('a,'b) t = ('a * 'b) list
  let empty = []
  let update m k v = 
    if mem_assoc k m then (k,v)::remove_assoc k m else (k,v)::m
  let get_keys m = 
    let (result,_) = split m in
	result 
  let get m k = 
    if mem_assoc k m then Some(assoc k m) else None
  let string_of_map string_of_key string_of_value m =
    let strings = map (fun (k,v) -> string_of_key k ^ 
			" -> " ^ string_of_value v) m in
	"{" ^ String.concat "; " strings ^ "}"
end

module Histogramm(M : Map) = struct
  let rec histo his = function
    [] -> his
  | x::xs -> 
      match M.get his x with
	    None   -> histo (M.update his x 1) xs
	  | Some n -> histo (M.update his x (n+1)) xs
  let histo liste = histo M.empty liste
end

module ListHistogramm = Histogramm(ListMap)

open ListHistogramm

let t = histo [2;3;2;5;3;4;2;1;5]