Quicksort in SML using foldr

Question

I'm working on an extra assignment where the partition function of a quicksort in SML may only be done with foldr, and no library functions may be used. I've gotten the partitioning down just fine, and have the fundamentals of quicksort just fine, but am running into problems where it seems to merge the wrong lists together/merge in the wrong order.

(*comp is a placeholder, I will be given a comparator function and list as input*)
fun comp a b = a > b;

(*Both partition functions are working as intended.*)
fun getGreater (a::b) c = foldr (fn (a, lst) => if (comp a c) then a::lst else lst) [] (a::b);
fun getLesserOrEqual (a::b) c = foldr (fn (a, lst) => if not (comp a c) then a::lst else lst) [] (a::b);

fun merge (a::b) (c::d) = foldr (op::) (c::d) (a::b);

fun tripleMerge (a::b) c (d::e) = merge (a::b) (c::(d::e));

(*Removes head, uses head as pivot. Recursive calls on results on getLesserOrEqual and getGreater*)
fun sort [] = [] | sort (a::b) = if ([a] = (a::b)) then [a] else
    tripleMerge (sort(getLesserOrEqual b a)) a (sort(getGreater b a));

As an example, here are some of the tests I'm running. When I follow my logic on paper, I don't get the same answers as the incorrect items:

sort [2, 6, 3, 6, 4, 100, 0];
val it = [0,2,3,6,4,6,100] : int list (*Incorrect*)

sort [1, 2, 3, 4, 5];
val it = [1,2,3,4,5] : int list

sort [5, 4, 3, 2, 1];
val it = [5,4,3,2,1] : int list (*incorrect*)

sort [1, 100, 10, 1000, 0];
val it = [0,1,10,100,1000] : int list

sort [1, 2, 1, 2, 1, 2, 5, 1];
val it = [1,1,1,1,2,2,2,5] : int list

Is my mistake obvious to anyone?

Answer 1

Here is some feedback:

1. This isn't Quicksort.

2. Instead of writing fun comp a b = a > b, you may refer to op > (a, b) (i.e. turn an operator into a function that takes a pair).

   I understand that your actual comparison function is given as input. A minor point of confusion might be that in the standard library, functions named compare return an order type, i.e. LESS, EQUAL or GREATER, rather than a bool. But never mind.

3. As John says, there is no real reason to use the pattern a :: b when the function is well-defined for empty lists.

4. Prefixing function names with get is somewhat redundant, since all (pure) functions get something as their main purpose.

5. You could combine your two filtering functions by making a higher order variant:

   fun flip f x y = f y x
   fun filter p xs = foldr (fn (x, ys) => if p x then x::ys else ys) [] xs
   fun greaterThan x xs = filter (flip comp x) xs
   fun lessThanOrEqual x xs = filter (comp x) xs
   

6. It seems that sort has two base cases where one is handled with a pattern and the other with an if-then-else. Why?

   fun sort [] = []
     | sort [x] = [x]
     | sort (x::xs) = sort (lessThanOrEqual x xs) @ x :: sort (greaterThan x xs)
   

   Or, if, for some reason, you wanted the base cases listed last:

   fun sort (x::(xs as (_::_))) = sort (lessThanOrEqual x xs) @
                                  x :: sort (greaterThan x xs)
     | sort xs = xs
   

7. Even though this isn't Quicksort, and so isn't nowhere near as efficient, one thing you could do to improve it, is to only pass through xs once, rather than twice. Since we're only allowed to foldr, we have to produce a pair of lists:

   fun partition p xs = foldr (fn (x, (ys, zs)) =>
       if p x then (x::ys, zs) else (ys, x::zs)) ([], []) xs
   
   fun sort [] = []
     | sort [x] = [x]
     | sort (x::xs) =
       let val (lesser, greater) = partition (comp x) xs
       in sort lesser @ x :: sort greater end
   

Answer 2

The only mistake I see is in your merge and tripleMerge functions. By using patterns like a::b you are disallowing empty lists. But -- when the pivot is either the smallest or the greatest element, than one of your partitioning functions will be returning empty lists. If you tweak the code of those two functions like this:

fun merge xs ys = folder (op::) ys xs;

fun tripleMerge xs y ys = merge xs (y::ys);

and leave the rest of the code alone, it will work as expected.