List equality checker (regardless of element order)

permEqual.ml

(* Checks if the two given int lists are the same, regardless of their order *)
(* val permEqual : int list -> int list -> bool = <fun>
# permEqual [] [];;
- : bool = true
# permEqual [1] [2];;
- : bool = false
# permEqual [1;2;3;4] [2;3;1;4];;
- : bool = true
# permEqual [1;2;3;4] [2;2;3;4];;
- : bool = false
#  *)

let permEqual f s =
  (* building an int map *)
  let 
    module IntMap = Map.Make(struct type t = int let compare = compare end) 
  in
  (* building an empty Map *)
  let dict = IntMap.empty in
  let rec aux f s dict =
    match f, s with
                     (* checking if all the keys in the map are 0 *)
        [], []    -> IntMap.for_all (fun k v -> v = 0) dict
                     (* subtract one from the key if exists, assign -1 if not *)
      | [], y::ys -> let 
                       dict = IntMap.add y ((if IntMap.mem y dict 
                                             then (IntMap.find y dict)
                                             else 0) - 1) dict
                     in 
                       aux [] ys dict
                     (* add one to the key if exists, assign 1 if not *)
      | x::xs, _  -> let 
                       dict = IntMap.add x ((if IntMap.mem x dict 
                                             then (IntMap.find x dict) 
                                             else 0) + 1) dict
                     in 
                       aux xs s dict
  in
    aux f s dict;;