OCaml function that returns most frequent

Question

Assuming I have a list:

[1;3;4;2;1;5;1]

I need to write a function that returns the number that appears the most frequent, in this case the output should be

int: 1

Any ideas? This is what I have so far, but it doesnt seem to be doing anything, really!

let rec r ls = match ls with

|[] -> 0

| hd::tl -> if(hd==(r tl)) then 1 + r tl else r tl;

Answer 1

You could build a map, for each number, of the number of times it appears in the list. This can be built by a single traversal of the list.

Answer 2

Sort the list. Write a tail recursive function whose accumulator contains:

1. the most frequent element of those smaller than the previously looked at element, or None initially,
2. the count of the element (1), or 0 initially,
3. the previously looked at element, the head of the sorted list initially,
4. the count of elements equal to the previously looked at element, 1 initially.

Call the function passing the initial accumulator and the tail of the sorted list.

Answer 3

This is quite simple if you bring equal elements together with a sort and set up a nice loop invariant. The idea is to scan over runs of equal elements, testing at the end of each run whether it is the longest so far.

The trick to making it easy is to do a preloop match to get the edge case (an empty list) out of the loop.

let most_frequent_elt list =
  let rec loop maxelt maxcount elt count = function
    | [] -> if count > maxcount then elt else maxelt
    | x::xs ->
        if elt = x then loop maxelt maxcount elt (count + 1) xs
        else if count > maxcount then loop elt count x 1 xs
        else loop maxelt maxcount x 1 xs in
  match List.sort compare list with
   | [] -> None
   | x::xs -> Some (loop x 0 x 1 xs)

Answer 4

Basically implementing lukstafi's answer (using mutable fields):

type 'a accumulator = { mutable curr: 'a option; mutable cnt: int; 
  mutable el: 'a option; mutable max: int; }

let rec process acc = function
  | [] -> acc.el
  | hd::tl -> 
    if Some(hd) = acc.curr then begin
      acc.cnt <- (acc.cnt + 1);
      if acc.cnt > acc.max then
        acc.max <- acc.cnt;
        acc.el <- Some(hd)
    end
    else begin
      acc.cnt <- 1;
      acc.curr <- Some hd
    end;
    process acc tl

let option2string = function | None -> "" | Some v -> string_of_int v

let () = 
  let sorted = List.sort compare [1;3;4;2;1;5;1] in
  let init = { curr = None; cnt = 0; el = None; max = 0 } in
  print_endline (option2string (process init sorted))

Answer 5

Late answer, but with Hashtbls you can have a good performance, according to the benchmarks here count unique elements in list in OCaml.

Then, adding a simple sort on the elements and their number of occurences, you obtain the most common element in the list.

module IntHash =
  struct
    type t = int
        let equal i j = i=j
        let hash i = i land max_int
  end

module IntHashtbl = Hashtbl.Make(IntHash)


let count_unique_elements_int_hashtbl list =
  let counter = IntHashtbl.create 10000 in
  let update_counter x =
    if IntHashtbl.mem counter x then
      let current_count = IntHashtbl.find counter x in
      IntHashtbl.replace counter x (succ current_count)
    else
      IntHashtbl.replace counter x 1
  in
  List.iter update_counter list;
  IntHashtbl.to_seq counter
  |> List.of_seq


let most_common_element_in_int_list list =
  count_unique_elements_int_hashtbl list
  |> List.sort (fun x y -> compare (snd x) (snd y)) 
  |> List.rev
  |> List.hd
  |> fst 

let () =
  assert (most_common_element_in_int_list [1;2;1] = 1);
  assert (most_common_element_in_int_list [6;1;2;1;6;6] = 6);