Return larger value of tuple

Question

I'm trying to find the Mode of a list, and return a tuple of the mode, and the number of times it occurs in the list. I have it to a point where I can return a list of each number and the number of times it occurs after that, but it also gives me occurrences past the first,

fun counter(_, nil) = 0
  | counter(a, x::xs) = if a = x then 1+counter(a, xs)
            else counter(a, xs);

fun countList(nil) = []
  | countList(x::xs) =
    (x, counter(x, x::xs))::countList(xs);

val lst = countList([1,2,1,1,3,4,5,2,1,2,1]);

Gives me val lst = [(1,5),(2,3),(1,4),(1,3),(3,1),(4,1),(5,1),(2,2),(1,2),(2,1),(1,1)] : (int * int) list

Which shouldn't be a problem, just loop through each value and see if the first values equal and then only give the first value, then only return the greatest one(s) but I cant seem to be able to figure that part out. I guess I'm just having trouble looping through the list and compare to the current value that I'm checking.

Answer 1

After you computed lst list, you don't need to find matching elements in it. The only thing you need to do is to traverse the list to find the element with maximum tuple second value.

fun findMax l =
  let fun find (nil, acc) = acc
  | find ((value, count)::xs, (acc_value, acc_count)) =
    if count > acc_count then find (xs, (value, count))
    else if value = acc_value then (acc_value, acc_count)
    else find (xs, (acc_value, acc_count))
  in find (l, (0, 0)) end;

findMax lst;
val it = (1, 5): int * int

However, this solution has O(n²) complexity. Alternatively, you can sort elements first in O(n * log n) time, and then return the first element (or several ones) from the list with maximum number of occurrences.