list - 返回最频繁的 OCaml 函数

Question

假设我有一个清单：

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

我需要编写一个函数来返回出现频率最高的数字，在这种情况下，输出应该是

诠释：1

有任何想法吗？这是我到目前为止所拥有的，但它似乎并没有做任何事情，真的！

让 rec r ls = 匹配 ls

|[] -> 0

| hd::tl -> if(hd==(r tl)) 然后 1 + r tl 否则 r tl;

Answer 1

您可以为每个数字构建一个地图，说明它在列表中出现的次数。这可以通过列表的单次遍历来构建。

Answer 2

对列表进行排序。编写一个尾递归函数，其累加器包含：

1. 那些比先前查看的元素更小的元素中最常见的元素，或者None最初，
2. 元素 (1) 的计数，或0最初，
3. 先前查看的元素，最初是排序列表的头部，
4. 元素的数量等于先前查看的元素，1最初。

调用传递初始累加器和排序列表尾部的函数。

Answer 3

如果您将相等的元素与排序组合在一起并设置一个很好的循环不变量，这将非常简单。这个想法是扫描相同元素的运行，在每次运行结束时测试它是否是迄今为止最长的。

让它变得简单的诀窍是进行预循环匹配以使边缘情况（一个空列表）脱离循环。

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

基本上实现 lukstafi 的答案（使用可变字段）：

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

迟到的答案，但使用Hashtbls 你可以有一个很好的表现，根据这里的基准计算 OCaml 中列表中的唯一元素。

然后，对元素及其出现次数进行简单排序，即可获得列表中最常见的元素。

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);