Write an ML function qsort which, given a list of objects t and a comparator fun

Question

Write an ML function qsort which, given a list of objects t and a comparator function f (given curry in curry style, f has type 'a --> 'a --> bool) outputs a sorted version of t in ascending order according to f using the classic quicksort algorithm. Note that we are well aware of the Wikipedia implementation or the other dozen implementations floating on the web. I expect you to write this on your own! Namely, write fun qsort 1 f = ... Revisit the previous question, hut this time, you cannot define the partition from first principles (as a recursive function) nor can you use the List.partition basis function. The only thing you can use is the higher-order function foldr. fun qsHigh 1 f = ...

Explanation / Answer

(* * This is an example showing that array bounds checking * is not needed for doing quicksort on an array. * The code is copied from SML/NJ lib with some modification. *) (* 16 type annotations, which occupy about 40 lines *) type order = LESS | EQUAL | GREATER ;; let min m n = if le_int m n then m else n withtype {m:int} int(m) -> {n:int} int(n) -> int(min(m, n)) ;; let{size:nat} sortRange(arr, start, n, cmp) = let item i = arr..(i) withtype {i:nat | i 'a in let swap (i,j) = let tmp = item i in arr..(i) unit ;; (* sorted checks if a list is well-sorted *) let{size:nat} sorted cmp arr = let len = vect_length arr in let rec s(v,i) = let v' = arr..(i) in match cmp(v,v') with GREATER -> false | _ -> if eq_int (i+1) len then true else s(v',i+1) withtype {i:nat | i bool ;; let vec = [|7;5;3;1;8;6;4;2|] ;;

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.