OCaml函数返回最频繁的项

Question

假设我有一个列表： [1;3;4;2;1;5;1] 我需要编写一个函数，它返回出现最频繁的数字，在这种情况下，输出应该是: int: 1 你有什么想法吗？ 这是我目前的代码，但似乎并没有实际作用！ let rec r ls = match ls with |[] -> 0 | hd::tl -> if(hd==(r tl)) then 1 + r tl else r tl;

- ohhreeohh

Answer 1

你可以针对每个数字建立一个出现次数的映射表。这可以通过单次遍历列表来构建。

- gasche

---

这可能听起来很蠢，但我该如何构建一个地图？我在这种语言方面非常新手。 - ohhreeohh

标准库中有一个“Map”模块，您可以使用它。这不是一个愚蠢的问题。 - Jeffrey Scofield

请注意，这对于多态类型不起作用，因为OCaml的标准库没有带有多态键的映射。 - Gordon Gustafson

@gordonGustafson 我不完全理解你的评论，但是如果你想要通用地编写这个函数，你可以通过额外的参数来请求一个比较函数。 - gasche

@gasche 假设我想要一个函数 val map_keys_to_zero : 'a list -> 'a comparator -> 'a Map，它返回一个将 'a list 中的每个元素映射为 0 的 Map。这是否可以使其适用于 任何 'a？我的简短研究表明不行，但作为 OCaml 的初学者，我很可能是错的。 :) - Gordon Gustafson

如果你想返回映射，你需要定义一个函数对象（或使用各种库提供的多态映射）。OP问题只要求最频繁的元素，可以表示为'a list -> ('a -> 'a -> int) -> 'a，并且可以使用局部抽象类型实现：let most_frequent (type a) (elems : a list) cmp = ...。 - gasche

Answer 2

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

1. 小于先前查看的元素中最常见的元素，或者最初为 None 的值，
2. 元素的计数（1），或者最初为 0 的值，
3. 先前查看的元素，最初为排序后列表的头部，
4. 等于先前查看的元素的元素计数，最初为 1。

调用该函数时，将初始累加器和排序后列表的尾部传递给函数。

- lukstafi

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)

- gsg

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

- Dave L.

---

谢谢提供参考，但我更喜欢 gsg 的解释 :-) - lukstafi

Answer 5

晚回答了，但使用Hashtbl可以获得良好的性能，根据这里的基准测试在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);

- RUser4512

---

如果你只是按降序排序你的最后一个元素，那么List.rev调用是不必要的。List.sort (fun x y -> compare (snd y) (snd x)) - undefined