是否有可能在haskell中实施一般的就地快速排序？

Question

问题中的一般术语(与专业相反)意味着函数可以对项目进行排序,只要它们是一个类型的实例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需要.
相比之下,经典的快速排序的类型或者签名sort的Data.List,是Ord a => [a] -> [a].约束只是Ord.

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

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

不幸的是,他们主要担心的是就地.这里给出的所有就地快速排序示例都有其他类型限制.
例如,iqsortklapaucius给出 了类型签名

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

有谁知道如何使用类型签名实现就地快速排序haskell功能Ord a => [a] -> [a]？
我知道如何进行就地快速排序,但我不知道如何使它变得通用.

Answer 1

iqsort实际上看起来对我很全面.如果你看一下Data.Vector.Generic黑线鳕,你其实可以使用该接口的任何 a!不同之处在于给定的函数更通用,因为它允许您选择一个未装箱的矢量,这当然只适用于某些 a.

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

因此,如果选择要装箱的V,矢量约束就会消失.