Блог

Я пытаюсь реализовать алгоритм быстрой сортировки в OCaml, и я думал, что он у меня есть, но он не компилируется, и я просто не могу понять, что с ним не так. Вот мой код:

 let rec quicksort list =
    match list with
    [] -> []
    |h::t -> append((quicksort (filter (largerthan h)
    t))(quicksort(filter (smallerthan h) t)));;

let largerthan x y =
    x<y;;

let smallerthan x y =
    x>y;;

let rec append x y =
match x with
[] -> y
| h::t -> h:: append t y;;  

let rec filter f list =
   match list with
   [] -> []
   |h::t -> (if f h = true then h:: filter f t else filter f t);; 
  

Теперь, когда я пытаюсь использовать это в OCaml, появляется сообщение «Ошибка: это выражение имеет тип ‘a -> ‘b
но ожидалось выражение типа «a», указывающее на последнюю строку моей функции быстрой сортировки.

Кто-нибудь знает, что происходит не так??

Большое спасибо!

Линус

Редактировать: Хорошо, я избавился от исходной ошибки (спасибо ADEpt :)). Однако теперь функция просто выводит пустой список независимо от входных данных… Кто-нибудь знает, что там происходит??

У вас есть дополнительные скобки в вызове «применить». Вместо:

append((быстрая сортировка (фильтр (больше, чем h) t))(быстрая сортировка (фильтр (меньше, чем h) t))

Напишите это:

добавить (быстрая сортировка (фильтр (больше, чем h) t)) (быстрая сортировка (фильтр (меньший, чем h) t))

Что касается вашего «второго» вопроса: вы забыли добавить h в отсортированный список….

OCaml компилирует вашу программу в том порядке, в котором вы ее передаете. В этом вопросе все очень строго. если вы что-то используете, вам нужно указать это, прежде чем использовать. Если вы замените определение, впоследствии будет использоваться новое определение, но до этого старое.

Если брать ваш код сверху вниз, вот что получается:

 let rec quicksort list =
    match list with
    [] -> []
    |h::t -> append((quicksort (filter (largerthan h)
    t))(quicksort(filter (smallerthan h) t)));;
  

На данный момент нет определения largerthan , smallerthan filter or append , поэтому компилятор не знает, что с этим делать.

Измените порядок вашего кода, и несколько проблем исчезнут.