Бесконечный цикл в быстрой сортировке SML?

Итак, я написал эту функцию быстрой сортировки на SML, чтобы использовать свертывание функций высокого порядка, но она зависает в бесконечном цикле, и я не могу определить неисправную логику, которая ее вызывает. Любые предложения о том, где искать?

(* 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;

Спасибо за любые предложения.


sml
person c0nn    schedule 07.02.2014    source источник

Ответы (1)


arrow_upward
1
arrow_downward

Проблема в том, что подсписки, для которых вы вызываете quicksort, могут быть такими же длинными, как и исходный список. Вы должны убедиться, что элемент сводки не может быть в этих списках.

Самый простой способ сделать это — использовать сопоставление, чтобы разделить входящий список на pivot и список оставшихся элементов, а затем передать этот список тестовым функциям.

person gsg    schedule 07.02.2014