(* 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";