1

问题中的术语general（与 special 相反）意味着该函数可以对项目进行排序，只要它们属于 的实例类型Ord。

考虑一下最著名的 haskell 广告之一

quicksort :: Ord a => [a] -> [a]
quicksort []     = []
quicksort (p:xs) = (quicksort lesser) ++ [p] ++ (quicksort greater)
    where
        lesser  = filter (< p) xs
        greater = filter (>= p) xs

上面的实现不是就地的。
我试图写一个就地版本。就地进行快速排序很容易。通常，我们只需要一个可变数组，我选择了Foreign.Marshal.Array.
我的实现是就地的并且运行得很好，但我对它的类型签名不满意

(Ord a, Storable a) => [a] -> IO [a]

更准确地说，类型约束Storable a让我很恼火。

显然，如果我们要对项目进行排序，Ord则需要约束，而Storable没有必要。
相比之下，经典快速排序或sortin的类型签名Data.List是Ord a => [a] -> [a]. 约束是Ord.

我没有找到摆脱额外约束的方法。

我搜索了 Stackoverflow，发现了一些关于在 Haskell 中就地快速排序的问题，例如
，你如何在 Haskell 中进行就地快速排序
为什么极简主义，例如 Haskell 快速排序不是“真正的”快速排序？

不幸的是，他们的主要关注点就位。那里给出的所有就地快速排序示例也有额外的类型约束。
例如，iqsortklapaucius 给出的 具有类型签名

iqsort :: (Vector v a, Ord a) => v a -> v a

有谁知道如何使用类型签名实现就地快速排序 haskell 函数Ord a => [a] -> [a]？
我知道如何进行就地快速排序，但我不知道如何使其通用。

4

2 回答 2

5

iqsort实际上对我来说看起来很一般。如果您查看 Data.Vector.Generic 黑线鳕，您实际上可以将该接口用于任何 a！不同之处在于给定的函数更通用，因为它允许您选择一个未装箱的向量，这当然只适用于一些 a.

这是链接：http ://hackage.haskell.org/packages/archive/vector/0.10.0.1/doc/html/Data-Vector-Generic.html

因此，如果您选择要装箱的 V，矢量约束就会消失。

于 2013-02-03T19:18:36.077 回答
3

是的，有可能。（尽管在 Haskell 中，您只想在真正需要最佳性能的情况下使用这种命令式算法。）

我知道两种这样的算法：

（Introsort基本上是精炼的快速排序，具有 O(n log n)最坏情况复杂度。）

我不确定MVector，但对于MArrays，你不必担心额外的约束MArray a e m。他们在那里使类型更通用，而不是更少。像这样的签名

qsort :: (MArray a e m, Ord e) => a Int e -> m ()

允许对不同的数组表示使用相同的算法。对于某些数据类型，您可以拥有该类型的专用数组，它们比通用数组更快、更紧凑。例如，如果要对 8 位整数进行排序，则有一个专门MArray IOUArray Int8 IO用于未装箱数组的实例。qsort仅使用多态性的这种数组的专门化是

qsort :: IOUArray Int Int8 -> IO ()

但是您也有MArray IOArray e IO可以任意工作的实例e。通过使用qsortwith IOArray，您可以获得没有限制的专业化e：

qsort :: (Ord e) => IOArray Int e -> IO ()

此外，如果您使用STArrays 和STmonad，您可以使用相同的函数对数组进行就地排序，稍后将结果作为纯值获取，而无需IO.

于 2013-02-03T20:04:18.057 回答