Infinite loop in SML quicksort?

Question

So, I've written this quicksort function in SML to exploit the high order function folding, but it's getting hung up in an infinite loop, and I can't pin down the faulty logic that's causing it. Any suggestions on where to look?

(* takes in a list of numbers and an arbitrary binary relation function f *)
fun quicksort nil f  = []
  | quicksort [x] f  = [x]
  | quicksort list f =
        let
            (* simply choose pivot as first item in the list *)
            val pivot = hd list
            (* lists iterated by folding for numbers pertaining to the relation f 
               or its converse *)
            fun test a  = List.foldr (fn (x,y) => if f (pivot, x) then x::y else y) [] a
            fun testC a = List.foldr (fn (x,y) => if f (pivot, x) then y else x::y) [] a
        in
            (* my notion is the function is looping here, since the functions test 
               and testC work fine on their own *)
            quicksort (test list) op f @ [pivot] @ quicksort (testC list) op f
        end;

Thanks for any suggestions.

Answer 1

The problem is that the sublists on which you invoke quicksort can be as long as the initial list. You must ensure that the pivot element cannot be in those lists.

The easiest way to do that is to use matching to split the incoming list into pivot and a list of remaining elements, and then pass that list to the test functions.