quicksort in ML

Question

Без использования выражений case (которые входят в следующий раздел класса), я не понимаю, почему следующее не выполняет quicksort. Он попадает в петлю где-то и никогда не заканчивается.

splitAt и append уже прошли проверку, но вот коды для них.

fun append(xs, ys) = 
if null xs 
then ys 
else (hd xs) :: append(tl xs, ys) 

fun splitAt(xs : int list, x : int) = 
let 
    fun sp(ys : int list, more : int list, less : int list) = 
     if null ys 
     then (more, less) 
     else 
      if hd ys < x 
      then sp(tl ys, more, append(less, [hd ys])) 
      else sp(tl ys, append(more, [hd ys]), less) 
in 
    sp(xs, [], []) 
end 

fun qsort(xs : int list) = 
    if length xs <= 1 
    then xs 
    else 
    let 
     val s = splitAt(xs, hd xs) 
    in 
     qsort(append(#2 s, #1 s)) 
    end 

И я получаю ту же проблему, используя присоединять (QSort (# 2 с), QSort (# 1 с)), но я, хотя прежний был лучше стиль, поскольку она требует только одного рекурсию с каждым раундом. Я думаю, я должен сказать, что «splitAt» делит список на большее или равное второму аргументу и меньше, и создает кортеж). Добавить объединяет 2 списка.

PS: Это только проблема практики, а не тест или домашнее задание.

Answer 1

Он попадает в петлю где-то и никогда не кончается.

Ваша проблема, скорее всего, вызывается в списке, который не уменьшается по размеру при рекурсивном вызове qsort. Возможно, пойдите с append(qsort (#2 s), qsort (#1 s)). Но даже тогда вы можете быть уверены, что каждый из #1 s и #2 s всегда будет уменьшать размер?

В идеале вы должны поставить splitAt и append, так как они не являются библиотечными функциями. Вы можете рассмотреть возможность использования встроенного добавления под названием @ и встроенного List.partition для формирования splitAt.

Сравнить против этого найденного где-то на межсетях:

fun quicksort [] = [] 
    | quicksort (x::xs) = 
    let 
     val (left, right) = List.partition (fn y => y < x) xs 
    in 
     quicksort left @ [x] @ quicksort right 
    end 

Answer 2

Поскольку это не домашнее задание ...

Обратите внимание, что если xs = [1,2] затем splitAt(xs hd xs) возвращается ([1,2],[]) поэтому попытка разобраться [1,2] этим версия qsort сводится к ... сортировке [1,2] снова. Это никогда не закончится.

Вместо этого я буду защищать splitAt от хвост xs. Минимальная твик в код, чтобы оставить append и splitAt в одиночку, но переписать qsort как:

fun qsort(xs : int list) = 
    if length xs <= 1 
    then xs 
    else 
    let 
     val s = splitAt(tl xs, hd xs) 
    in 
     append(qsort(#2 s), (hd xs) :: qsort(#1 s)) 
    end; 

Тогда, например,

- qsort [4,2,1,2,3,6,4,7]; 
val it = [1,2,2,3,4,4,6,7] : int list 

Очень важно, что вы применяете qsort дважды затем добавить результаты , Попробуйте применить qsort один раз к добавленному split будет пытаться уменьшить qsort до применения qsort к списку, который имеет тот же размер, что и исходный список.

SML действительно становится забавным, когда вы получаете соответствие шаблону. Вы должны наслаждаться следующей главой.