In SML is it possible to find the number of occurrences of the min number in a list?

I have code to find the number of occurrences of a number but i am stumped on how to find the min and use it to find how many of the minimum num there is.

fun occurrences(nil, n)=0
|   occurrences(ls, n) =
    if hd(ls)=n then occurrences(tl(ls),n)   1
    else occurrences(tl(ls),n)   0;

Thank you!

CodePudding user response：

You can write a function that keeps track of the min value and its count as you iterate through the list.

We can do this by implementing a tail-recursive function which helper, which maintains the value of the current minimum and a count of the number of times that item has appeared.

We can then wrap this in another function min_count via a let-in-end block.

For example:

fun min_count [] = 0 (* the empty list has zero items in it *)
  | min_count (x :: xs) =
let
  (* when we reach the end of the list, return the accumulated count *)
  fun helper (_, n) [] = n
    | helper (m, n) (y :: ys) =

    (* if we find a new minimum, reset the count *)
    if y < m then helper (y, 1) ys

    (* if the current list item is larger than the min, ignore it *)
    else if y > m then helper (m, n) ys

    (* if we've found another instance of the min, add one to the count *)
    else helper (m, n   1) ys
in
  (* first item appears once *)
  helper (x, 1) xs (* first item appears once *)
end;

CodePudding user response：

We can also readily define this in terms of a fold.

What information do we need to keep track of as we fold over the list?

• The current minimum.
• The current count of minimum values.

Using List.foldl this will be our initial value expressed as a tuple. We'll pick the maximum value an int can be (at least on my machine). Feel free to change this value as is sensible. And we'll start with a count of zero.

let
  fun f(x, (min, count)) =
    if x = min then (min, count   1) 
    else if x < min then (x, 1)
    else (min, count)
in
  List.foldl f (1073741823, 0) [1, 2, 3, 4, 5, 6, 1, 2, 3, 4, 3, 3, 5]
end;

The function we apply each time is very simple. It patterns matches against that initial value tuple to give us min and count. If min equals the current value in the list (x) then x is another occurrence of that minimum value and we increment the count by 1. If it's less than the min then we have a new minimum value, so we pass that along and start over at 1 with the count. Otherwise, nothing changes.

Optionally we can clean this up a bit using Int.compare, case, and aliasing (min, count) as init.

let
  fun f(x, init as (min, count)) =
    case Int.compare(x, min) of
      EQUAL => (x, count   1)
    | LESS  => (x, 1)
    | _     => init

  val init = (1073741823, 0)
  val lst  = [1, 2, 3, 4, 5, 6, 1, 2, 3, 4, 3, 3, 5]
in
  List.foldl f init lst
end;