fun max3(a:int,b,c) = (* maximum of three integers *)
	if a>b then
		if a>c then a
		else c
	else
		if b>c then b
		else c;

(* Naive Reverse--Ullman2, p.55 *)
fun reverse(L) =
    if L = nil then nil
	else reverse(tl(L)) @ [hd(L)];

(* Naive Reverse with Difference Lists--Ullman2, Ex.3.15 *)
fun reverse([]) = []
|   reverse(x::xs) = reverse(xs) @ [x];


(* Ullman 2, Fig.3.6 *)
fun comb(n,m) = (* assumes 0 <= m <= n *)
    if m = 0 orelse m = n then 1
	else comb(n-1,m) + comb(n-1,m-1);

(* Ullman2 Fig.3.10 *)
fun
  take(L) =
       if L = [] then []
       else hd(L)::skip(tl(L))
and
  skip(L) =
    if L = nil then nil
    else take(tl(L));

(* Powerset--Ullman notes *)
fun pre(x, nil) = nil
|   pre(x,L::Ls) = (x::L)::pre(x,Ls);

fun pow([]) = [[]]
|   pow(x::xs) =
    let
      val ps = pow(xs)
    in
      ps @ pre(x,ps)
    end;

(* Fast Exponentiation, Paulson2, p.49 *)

fun power(x,k): real =
  if k=1 then x
         else if k mod 2 = 0 then power(x*x, k div 2)
                             else x* power(x*x, k div 2);



(* Ullman2 Fig.3.12 *)
fun merge([],M) = M
|   merge(L,[]) = L
|   merge(L as x::xs, M as y::ys) =
      if x < y then x::merge(xs, M)
      else y::merge(L,ys);

(* Fast reverse with difference lists. Ullman2 p.87; Paulson2 p.80 *)
fun rev1([], M) = M
|   rev1(x::xs, ys) = rev1(xs, x::ys);

fun fastrev(L) = rev1(L,[]);

(* Paulson, p.43.  The function cond is a conditional expression that leads
to unintuitive results, because of ML's use of call-by-value (eager or strict
evaluation) *)

fun cond(test, then_part, else_part) =
  if test then then_part else else_part;

(* Example:
val x = 0;
if x = 0 then [0] else tl []; ---works
cond(x=0, [0], tl []); ---fails
*)

(* Factorial Programs.  Paulson2, pp.40-43 *)

fun fact n: int = if n=0 then 1 else n*fact(n-1);

fun badf n: int = cond(n=0, 1, n*badf(n-1));  (* Uses eager conditional *)

(*Iterative, i.e., Tail-Recursive, Program *)

fun facti(n,p) = if n=0 then p else facti(n-1, n*p);

(* Simulation of goto program with mutual recursion--Paulson2 p.58 *)
(*var x:=0; y:= 0; z:=0;
  F: x := x+1; goto G;
  G: if x<y then goto F else (y := x+y; goto H);
  H: if z>0 then (z := z-x; goto F) else stop;
*)
fun F(x,y,z) = G(x+1,y,z)
and G(x,y,z) = if y<z then F(x,y,z) else H(x,x+y,z)
and H(x,y,z) = if z>0 then F(x,y,z-x) else (x,y,z);

(* Requires 46-bit mantissa--works with Moscow ML version 1.43
   (April 1998) and with sml97 *)
local val a = 16807.0 and m = 2147483647.0
in fun nextrand seed =
  let val t = a* seed
  in t - m * real(floor(t/m)) end
end;

fun randlist (n, seed, tail) =
    if n = 0 then (seed, tail)
    else randlist (n-1, nextrand seed, seed::tail);

(* To generate a list of 10,000 random numbers in rs, call
   val (seed, rs) = randlist(10000, 1.0, []);  *)

(* Simple insertion sort.  Paulson2, pp.109-110. *)
fun ins (x, []): real list = [x]
|   ins (x, y::ys) =
	if x <= y then x::y::ys (* x belongs here *)
			  else y::ins(x,ys);

(* Examples of use: ins(4.0, [6.0]); ins(8.0, it); ins(5.0, it) *)

fun insort [] = []
|   insort (x::xs) = ins(x, insort xs);

(* Example of use: insort([9.0, 7.0, 8.0, 3.0, 4.0, 2.0, 5.0]); *)

(* Paulson2, p.110 *)
fun quick [] = []
|   quick [x] = [x]
|   quick (a::bs) = (* the head "a" is the pivot *)
     let fun partition (left, right, []): real list =
           (quick left) @ (a :: quick right)
	 |   partition (left, right, x::xs) =
               if x <= a then partition(x::left, right, xs)
                         else partition (left, x::right, xs) 
     in
       partition([],[],bs)
     end;