haskell - 使用haskel实现快速排序

Question

我想知道为什么下面的快速排序代码显示“未解决的顶级重载错误”

sort = \xs -> case xs of
                [] -> []
                y:ys -> sort[p | p <- ys, p < y]
                        ++ y:sort[p| p <- ys, p > y] 

你能告诉我为什么吗？

标签： haskell

Answer 1

无法推断此函数的类型，因为使用 和 的约束可能有多种<类型>。您可以通过添加如下签名（尽可能通用）来解决此问题。顺便说一句，您的实现会删除重复出现的元素。使用<=而不是<修复此问题：

sort :: Ord a => [a] -> [a]
sort = \xs -> case xs of
                [] -> []
                y:ys -> sort[p | p <- ys, p <= y]
                        ++ y:sort[p| p <- ys, p > y] 

示例调用（双 7）：

> sort [12,34,2,4,7,6,34,7,3]
[2,3,4,6,7,7,12,34,34]