在OCaml中实现快速排序：不明白发生了什么问题？

我想在OCaml中实现快速排序算法，我以为我有它，但它不会编译，我只是不能看到它有什么问题。这里是我的代码：在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 一个，但预计类型”的表达”同时指出到我的快速排序功能的最后一行。

有谁知道发生了什么事？

非常感谢！

莱纳斯

编辑：好吧，我已经摆脱了原来的错误（感谢ADEPT :)）。然而，现在这个函数只是输出一个空列表而不管输入...有人知道那里发生了什么吗？

来源

2011-11-09 Linus

你不需要为largerthan，只需使用（<）（带有括号）。 smallerthan（使用（>））也是如此。 –

还要注意的是这不会真的是一个快速快速排序，因为追加慢（列表中的第一部分将建立两次... ...） –

还要注意的是'append'和'filter'已经在基础库中的可用，分别为'（@）'（infix operator，'xs @ yx'）和'List.filter'。 – gasche

在“应用”调用中您有额外的零食。相反的：

append((quicksort (filter (largerthan h) t))(quicksort(filter (smallerthan h) t))

这样写：

append (quicksort (filter (largerthan h) t)) (quicksort (filter (smallerthan h) t))

来源

2011-11-09 11:46:36 ADEpt

或甚至更好： 'let left = quicksort（filter（largerthan h）t）in let right = quicksort（filter（smallerthan h）t）in append left right'（with proper line endings that I'm not当然我可以发表评论;这看起来更可读） – akoprowski

谢谢！这照顾到了错误。但是，我现在只是得到一个空列表作为输出...有人知道哪里出了问题吗？ :) – Linus

您需要打开“largetthan”和“smallerthan”到“largerthan”和“smallerorequalthen” :)否则没有子列表包含“H” – ADEpt

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定义，所以编译器不知道该怎么办这个。

重新排列你的代码和几个问题就会迎刃而解。

来源

2011-11-09 11:55:29 LiKao

另外要注意：尽量使用方法从标准库或一些很好的替代在可能的情况下使用标准库（例如电池）。 'filter'和'append'已经存在了。 – LiKao

嘿，谢谢你的解释。但是，我只是把这个顺序放在这里，在我的源文件中顺序是正确的:)。 – Linus

好的。总是给出展示问题的代码，以避免在您提供的代码存在其他问题时混淆其他代码。 – LiKao

为了您的“第二”的问题：你忘了到h添加到排序列表....

来源

2011-11-09 13:44:55

是的！非常感谢！ – Linus

在OCaml中实现快速排序：不明白发生了什么问题？

回答

相关问题