(* split xs into two even parts: ys and zs *) let rec split (xs:'a list) (ys:'a list) (zs: 'a list) : 'a list * 'a list = match xs with [] -> (ys, zs) | hd :: tail -> split tail zs (hd :: ys) (* merge lists xs and ys *) (* two empty lists merge into an empty list *) (* an empty list merges with a non-empty list yielding the latter, unchanged *) (* two non-empty lists compare first elements, and prepend the smaller * of the two to the result of the recursive merge *) let rec merge (cmp: 'a->'a->bool) (xs:'a list) (ys:'a list) : 'a list = [] (* TODO: FIX ME *) (* Sort original list os using function cmp *) (* an empty list is already sorted *) (* a one-element list is already sorted *) (* a multi-element list should be split * and recursively sorted, then merged *) let rec mergesort (cmp: 'a->'a->bool) (os:'a list) : 'a list = [] (* TODO: FIX ME *) let int_sort : int list -> int list = mergesort (<=) let int_data : int list = [5; 7; 4; 3; 2; 1; 6] (* returns true if x <= y, where false < true *) let bool_cmp (x:bool) (y:bool) : bool = if not x then true else y let bool_sort : bool list -> bool list = mergesort bool_cmp let bool_data : bool list = [true; true; false; false; true; false] let test1 () = bool_sort bool_data = [false; false; false; true; true; true] let test2 () = int_sort int_data = [1; 2; 3; 4; 5; 6; 7] let tests = [test1; test2] let rec runtests (tests : (unit -> bool) list) = match tests with [] -> () | hd::tail -> if hd () then print_endline "success!" else print_endline "failure :-("; runtests tail let main = print_string "\n\nBeginning Tests\n\n"; runtests tests; print_string "\nCompleted Tests\n\n";