(* factorization.sml *)

(* val divides : int -> int -> bool

   divides m n tests whether m divides n *)

fun divides m n = n mod m = 0;

(* val leastFactor : int * int -> int

   if m <= n, then leastFactor(m, n) returns the least positive factor
   of n that is >= m *)

fun leastFactor(m, n) =
      if divides m n
      then m
      else leastFactor(m + 1, n);

exception TooSmall

(* val factors : int -> int list

   if n >= 2, then factors n returns the list of all prime factors of
   n, listed in non-decreasing order; otherwise, it raises TooSmall *)

local
  (* val facts : int -> int list

     if n >= 2, then facts n returns the list of all prime factors of
     n, listed in non-descreasing order *)

  fun facts n =
        let val m = leastFactor(2, n)
        in if m = n
           then [m]
           else m :: facts(n div m)
        end
in
  fun factors n = if n < 2 then raise TooSmall else facts n
end;

(* val group : ('a * 'a -> order) -> 'a list -> (int * 'a)list

   if cmp is a linear ordering, and xs is in non-decreasing order,
   then group cmp xs returns the list [(n1, x1), ..., (nm, xm)], where
   the xi's are all the distinct elements of xs, listed in ascending
   order, and each corresponding ni is the number of times that xi
   appears in xs *)

fun group cmp =
      let (* val grp : 'a list * (int * 'a)list -> (int * 'a)list

             if xs is in non-decreasing order, then grp(xs, zs)
             returns zs @ [(n1, x1), ..., (nm, xm)], where the xi's
             are all the distinct elements of xs, listed in ascending
             order, and each corresponding ni is the number of times
             that xi appears in xs *)

          fun grp(nil,     zs) = zs
            | grp(x :: xs, zs) = grp'(xs, 1, x, zs)

          (* val grp' : 'a list * int * 'a * (int * 'a)list -> (int * 'a)list

             if xs is in non-decreasing order, and y is <= all
             elements of xs, according to cmp, then grp'(xs, y, n, zs)
             returns zs @ [(n0, y), (n1, x1), ..., (nm, xm)], where n0
             is n + the number of occurrence of y in xs, the xi's are
             all the distinct elments of xs - {y}, listed in ascending
             order, and each corresponding ni is the number of times
             that xi appears in xs - {y} *)

          and grp'(nil,     n, y, zs) = zs @ [(n, y)]
            | grp'(x :: xs, n, y, zs) =
                case cmp(y, x) of
                     LESS    => grp(x :: xs, zs @ [(n, y)])
                   | EQUAL   => grp'(xs, n + 1, y, zs)
                   | GREATER => raise Fail "cannot happen"
      in fn xs => grp(xs, nil) end;

(* val display : ('a -> string) * (int * 'a)list -> unit

   display toStr [(n1, x1), ..., (nm, xm)] prints each pair on its
   own line, using toStr to print the xi's *)

fun display toStr =
      List.app(fn (n, y) =>
                    (print "("; print(Int.toString n); print ", ";
                     print(toStr y); print ")\n"));

(* val factorizeAndDisplay : int -> unit

   if n >= 2, then factorizeAndDisplay n prints a list of pairs (n1,
   x1), ..., (nm, xm), where the xi's are the distinct prime factors
   of n, listed in ascending order, and each ni is the number of times
   that the corresponding xi appears as a factor of n; otherwise, it
   prints an error message *)

fun factorizeAndDisplay n =
      (display Int.toString o group Int.compare o factors)n
        handle TooSmall => print "too small\n";