создать гистограмму OCaml

Question

Моя задача - создать гистограмму, которая выводит количество раз, когда элемент, который он есть в списке.

Input:[2;2;2;3;4;4;1] 
Output[(2, 3); (2, 2); (2, 1); (3, 1); (4, 2); (4, 1); (1, 1)] 
Expected output : [(2, 3); (3, 1); (4, 2); (1, 1)] 

My code: 

let rec count a ls = match ls with 
    |[]    -> 0 
    |x::xs when x=a -> 1 + count a xs 
    |_::xs   -> count a xs 

let rec count a = function 
    |[]    -> 0 
    |x::xs when x=a -> 1 + count a xs 
    |_::xs   -> count a xs 

let rec histo l = match l with 
|[] -> [] 
|x :: xs -> [(x, count x l)] @ histo xs ;; 

Что я сделал не так?

Answer 1

Проблема в том, что xs содержит потенциально элементы, которые равны x. Это то, что вы видите в своем выпуске: (2,3) означает, что в списке 3 раза 2; xs тогда равно [2; 2; 3; 4; 4; 1] ... и так далее.

Также (не влияет на заключение): у вас есть 2 определения количества, но они идентичны.

Для реализации гистограммы, используйте Hashtbl:

let h = Hashtbl.create 1000;;  
List.iter (fun x -> let c = try Hashtbl.find h x with Not_found -> 0 in Hashtbl.replace h x (c+1)) your_list;; 
Hashtbl.fold (fun x y acc -> (x,y)::acc) h [];;