CODEWITHSUNDEEP
ocaml
user1787222
user1787222

Reputation: 87

count number of duplicates in a list in OCaml

I have a list like: 

let lst = ["cat"; "dog"; "cow"; "dog"; "cat"; "horse"; "dog"];;

I want to count the number of same elements and have the output in a list of tuples (element, count) like:

[("cat", 2); ("dog", 3); ("cow", 1); ("horse", 1)]

I tried using List.fold_left but found that the folding function will be complex. Any suggestion?

Upvotes: 1

Views: 4597

Answers (3)

Drake Petersen
Drake Petersen

Reputation: 171

A way to preserve order and performance:

    let count lst = 
      let sorted = List.sort (compare) lst in
      List.fold_right (fun ele acc -> match acc with 
                                      | [] -> [(ele, 1)]
                                      | (ele', c)::t -> 
                                           if ele = ele' 
                                           then (ele, c+1)::t
                                           else (ele,1)::(ele',c)::t) sorted []

Upvotes: 0

BLUEPIXY
BLUEPIXY

Reputation: 40145

let count l =
    let hash = Hashtbl.create 10 in
    List.iter (fun key -> if Hashtbl.mem hash key then Hashtbl.replace hash key ((Hashtbl.find hash key) + 1) else Hashtbl.add hash key 1) l;
    Hashtbl.fold (fun k v ls -> (k, v) :: ls) hash []

Upvotes: 1

Jackson Tale
Jackson Tale

Reputation: 25812

If you don't care about performance, then it can be like this:

let count_dup l =
  let scan_count x l = List.fold_left (fun (c,acc) y -> if x = y then c+1,acc else c,y::acc) (1,[]) l in
  let rec count acc = function
    | [] -> List.rev acc
    | hd::tl -> let c,r = scan_count hd tl in count ((hd,c)::acc) r
  in 
  count [] l

If you care about performance, but don't care about the order, then it is better that you sort the list first, then scan once.

let count_dup' l = 
  let sl = List.sort compare l in
  match sl with
    | [] -> []
    | hd::tl -> 
      let acc,x,c = List.fold_left (fun (acc,x,c) y -> if y = x then acc,x,c+1 else (x,c)::acc, y,1) ([],hd,1) tl in
      (x,c)::acc

Upvotes: 2

Related Questions