type intlist = int list
type partition = intlist * int * intlist

(* printList : intlist -> () 
   printList xs = () 

   Invariant:  
   Prints a xs on the screen *)

fun printList xs  = 
    (print "["; printList' xs; print "]")
and printList' [] = ()
  | printList' [x] = print(Int.toString x)
  | printList' ((x : int) :: (xs : intlist)) =
    (print (Int.toString x); print ","; printList' xs) 
(*    (print x; print ","; printList' xs) *)

(* quicksort : intlist -> intlist 
   quicksort xs = ys
  
   Invariant:
   ys  are a sorted version of the xs
*)
   
fun quicksort [] = []
  | quicksort (pivot :: xs) =
      partition xs ([], pivot, [])  

(* partition : intlist -> partition
   partition xs (lt, pivot, ge)

   Invariant:
   xs, lt, pivot, ge contain the same elements as the 
     list to be sorted
   all elements in "lt" are less then "pivot"
   all elements in "ge" are greater equal "pivot"
*)

and partition [] (lt, pivot, ge) = 
    let
      val _ = print "Unsorted : "
      val _ = printList lt
      val _ = printList [pivot]
      val _ = printList ge
      val _ = print "\n"
      val ltSorted = quicksort lt
      val geSorted = quicksort ge
      val Sorted = ltSorted @ [pivot] @ geSorted
      val _ = print "Sorted   : "
      val _ = printList Sorted
      val _ = print "\n"
    in
      Sorted
    end
      (* quicksort lt @ (pivot :: quicksort ge) *)
  | partition (x :: xs) (lt, pivot, ge) =
      if x < pivot
      then partition xs (x :: lt, pivot, ge)
      else partition xs (lt, pivot, x:: ge)


(*
Error messages:
o Don't forget parenthesis in patterns
o Order of functions is important
o Use mutual recursion to tell ML that one 
    function can call "forward"
*)