list - 最も頻繁に返す OCaml 関数

Question

リストがあると仮定します：

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

最も頻繁に表示される数値を返す関数を作成する必要があります。この場合、出力は次のようになります。

整数: 1

何か案は？これは私がこれまでに持っているものですが、実際には何もしていないようです!

let rec r ls = ls と一致させます

|[] -> 0

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

Answer 1

番号ごとに、リストに表示される回数のマップを作成できます。これは、リストを 1 回走査するだけで作成できます。

Answer 2

リストを並べ替えます。アキュムレータに以下が含まれる末尾再帰関数を記述します。

1. 以前に見た要素よりも小さいものの中で最も頻度の高い要素、またはNone最初に、
2. 要素の数 (1)、または0最初は、
3. 以前に見た要素、最初はソートされたリストの先頭、
4. 1最初は、以前に調べた要素に等しい要素の数。

初期アキュムレータとソートされたリストの末尾を渡して関数を呼び出します。

Answer 3

基本的に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))