val natrange = 
    let 
        fun nr l a b = if b < a then l else nr (b :: l) a (b-1) 
    in 
        nr [] 
    end;

fun allcons x ll = map (fn l => x::l) ll;

fun change 0 _ = [[]]
  | change _ [] = []
  | change n [c] = if n mod c = 0 then [[(n div c, c)]] else []
  | change n (c::coins) =
       List.concat (map (fn x => allcons (x,c) (change (n - x * c) coins)) (natrange 0 (n div c)));

val change99 = List.length (change 99 [50,20,10,5,2,1]);

local val a = 16807.0 and m = 2147483647.0
in fun nextrandom seed =
          let val t = a*seed
          in t - m * real(floor(t/m)) end
    and truncto k r = 1 + floor((r / m) * (real k))
end;

fun randlist (n,seed,seeds) =
        if n=0 then (seed,seeds)
        else randlist(n-1, (nextrandom seed), seed::seeds);
val (seed,rs) = randlist(10000, 1.0, []);


datatype 'a tree = Leaf | Branch of 'a * ('a tree) * ('a tree);

fun insert _ (x, Leaf) = Branch (x, Leaf, Leaf)
  | insert b (x, (Branch (a,t1,t2))) = if (b (x, a))
                                       then Branch (a, (insert b (x, t1)), t2)
                                       else Branch (a, t1, (insert b (x, t2)));
fun flatten Leaf = []
  | flatten (Branch (a,t1,t2)) = (flatten t1) @ [a] @ (flatten t2);

val treeSort = fn b => flatten o (foldr (insert b) Leaf);

fun increasing b [] = true
  | increasing b [x] = true
  | increasing b (x::y::l) = if b (x, y) then increasing b (y::l) else false;

val checkTreeSort = let val b = Real.<= in increasing b (treeSort b rs) end;