(* Some basic list functions *)

(* printing an integer-list *)

fun prIntList (L) =
    let
        fun prIL ([]) = print ("")
        |   prIL ((a:int)::M) =
                 if null (M) then print(a)
                 else (print (a); print (", "); prIL (M))
    in
        (print ("["); prIL (L); print ("]\n"))
    end
;

(* Reversing a list *)

fun reverse (L) =
    let fun rev ([], M) = M
        |   rev (x::xs, M) = rev (xs, x::M)
        ;
    in
        rev (L, [])
    end
;

(* Sequential search on a list *)

fun lookup (x, []) = false
|   lookup (x, h::L) =
           if (x = h) then true
           else lookup (x, L)
;


(* MERGE SORT (parametrized on the ordering relation R) *)

(* ALGORITHM:
   Let L split into 2 parts M and N.
   Then the sorted version of L is the merge of MM and NN, where
        MM and NN are the sorted versions of M and N.
*)

(* Step 1: Split the list into two equal length lists *)

fun split ([]) = ([], [])
|   split ([a]) = ([a], [])
|   split (a::b::L) =
          let
              val (M, N) = split (L)
          in
              (a::M, b::N)
          end
;

(* Step 2: Merge sorted lists (parametrized on the ordering relation R)  *)

fun merge ([], M, _) = M
|   merge (L, [], _) = L
|   merge (L as a::LL, M as b::MM, R) =
          if R (a, b) then a::merge(LL, M, R)
          else b::merge(L, MM, R)
;

(* Main body of merge sort *)

fun mergesort ([], _) = []
|   mergesort ([a], _) = [a]
|   mergesort (L, R) =
         let val (M, N) = split (L);
             val (MM, NN) = (mergesort (M, R), mergesort(N, R))
         in
             merge (MM, NN, R)
         end
;

(* Sort a list while deleting duplicates *)

(* Merging 2 sorted lists while removing duplicates *)

fun uniq ([]) = []
|   uniq ([a]) = [a]
|   uniq (a::b::L) =
         if (a=b) then uniq (a::L)
         else a::uniq (b::L)
;

fun uniqMerge ([], M, _) = uniq (M)
|   uniqMerge (L, [], _) = uniq (L)
|   uniqMerge (L as a::LL, M as b::MM, R) =
          if (a=b) then uniqMerge (L, MM, R)
          else if R (a, b) then a::uniqMerge (LL, M, R)
          else b::uniqMerge(L, MM, R)
;

fun uniqMergesort ([], _) = []
|   uniqMergesort ([a], _) = [a]
|   uniqMergesort (L, R) =
         let val (M, N) = split (L);
             val (MM, NN) = (uniqMergesort (M, R), uniqMergesort(N, R))
         in
             uniqMerge (MM, NN, R)
         end
;