Реализация быстрой сортировки в OCaml: не понимаете, что происходит?

Question

Я пытаюсь реализовать алгоритм быстрой сортировки в 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 но ожидалось выражение типа «а» при указании на последнюю строку моей функции быстрой сортировки.

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

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

Linus

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

Answer 1

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

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

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

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

Answer 2

По вашему "второму" вопросу: вы забыли добавить h в отсортированный список ....

Answer 3

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

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

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

В настоящее время нет определения largerthan, smallerthan, filter или append, поэтому компилятор не знает, что с этим делать.

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