Haskell中的枢轴Quicksort
是否有可能在Haskell中实现快速排序（使用RANDOM-PIVOT），它仍然有一个简单的Ord a => [a]->[a]签名？
我开始理解Monads，而现在，我有点像单片机那样思考单子，这对于IO来说非常有用。
所以，我明白一个返回一个随机数的函数实际上应该返回一个像IO这样的monadic值，否则它会破坏引用透明性。 我也明白，应该没有办法从返回的monadic值中“提取”随机整数，否则，它会再次破坏参考透明度。
但是，我仍然认为应该可以实现'纯粹' [a]->[a] quicksort函数，即使它使用随机数据透视，因为它是引用透明的。 从我的角度来看，随机数据透视仅仅是一个实现细节，不应该改变函数的签名
OBS：我实际上对特定的quicksort问题没有兴趣（所以，我不想听起来粗鲁，但我不想要“使用mergesort”或“随机数据透视不会增加实践中的性能”类型的答案）我实际上对如何实现一个使用'不纯'函数的'纯'函数感兴趣，例如quicksort，我可以确保函数实际上是纯函数。
Quicksort就是一个很好的例子。
在这种情况下，如果您知道函数是引用透明的，但是您无法向编译器证明它，则可以使用模块Data.Unsafe的函数unsafePerformIO :: IO a -> a 。
例如，你可以使用unsafePerformIO来获得一个初始的随机状态，然后用这个状态做任何事情。
但请注意：如果不是真的需要，请不要使用它。 即使如此，请仔细考虑一下。 unsafePerformIO有点是一切罪恶的根源，因为它的后果可能是非常重要的 - 任何事情都可以通过使用这个函数强制不同类型来使RTS崩溃。
你在做一个错误的假设，即选择枢轴点只是一个实现细节。 考虑一个集合的部分排序。 像卡片上的快速排序
如果面值较小但如果您要评估布尔值，则卡<卡b：
4 spades < 4 hearts (false)
4 hearts < 4 spades (false)
4 hearts = 4 spades (false)
在这种情况下，枢轴的选择将决定卡的最终排序。 完全一样
对于像这样的功能
a = get random integer
b = a + 3
print b
由a决定。 如果你是随机选择一些东西，那么你的计算是或者可能是非确定性的。
好的，看看这个。
选择可散列包中复制的部分，以及voodoo魔术语言杂注
{-# LANGUAGE FlexibleInstances, UndecidableInstances, NoMonomorphismRestriction, OverlappingInstances #-}
import System.Random (mkStdGen, next, split)
import Data.List (foldl')
import Data.Bits (shiftL, xor)
class Hashable a where
hash :: a -> Int
instance (Integral a) => Hashable a where
hash = fromIntegral
instance Hashable Char where
hash = fromEnum
instance (Hashable a) => Hashable [a] where
hash = foldl' combine 0 . map hash
-- ask the authors of the hashable package about this if interested
combine h1 h2 = (h1 + h1 `shiftL` 5) `xor` h2
好的，现在我们可以列出任何Hashable的列表并将它变成一个Int 。 我在这里为Char和Integral a提供Integral a实例，更多更好的实例在可散列的packge中，这也允许salting和东西。
这只是我们可以制作一个数字生成器。
genFromHashable = mkStdGen . hash
所以现在有趣的部分。 我们来写一个函数，它需要一个随机数生成器，一个比较器函数和一个列表。 然后我们将通过查询生成器来选择一个数据透视表，并使用比较器对列表进行分区。
qSortByGen _ _ [] = []
qSortByGen g f xs = qSortByGen g'' f l ++ mid ++ qSortByGen g''' f r
where (l, mid, r) = partition (`f` pivot) xs
pivot = xs !! (pivotLoc `mod` length xs)
(pivotLoc, g') = next g
(g'', g''') = split g'
partition f = foldl' step ([],[],[])
where step (l,mid,r) x = case f x of
LT -> (x:l,mid,r)
EQ -> (l,x:mid,r)
GT -> (l,mid,x:r)
库函数 ： next从生成器中获取一个Int ，并生成一个新的生成器。 split发生器分成两个不同的发生器。
我的功能 ： partition使用f :: a -> Ordering将列表分成三个列表。 如果你知道褶皱，那应该很清楚。 （请注意，它不保留子列表中元素的初始顺序;它将它们逆转，使用foldr可以解决这个问题。） qSortByGen工作方式就像我之前说过的那样：请参阅生成器以获取数据透视表，将列表中，分叉用于两次递归调用的生成器，递归排序左侧和右侧，并将它们连接在一起。
便利功能很容易从这里构成
qSortBy f xs = qSortByGen (genFromHashable xs) f xs
qSort = qSortBy compare
注意最终函数的签名。
ghci> :t qSort
qSort :: (Ord a, Hashable a) => [a] -> [a]
列表中的类型必须实现Hashable和Ord 。 有您要求的“纯”功能，有一个合乎逻辑的附加要求。 更一般的功能在他们的要求中限制性较小。
ghci> :t qSortBy
qSortBy :: (Hashable a) => (a -> a -> Ordering) -> [a] -> [a]
ghci> :t qSortByGen
qSortByGen
:: (System.Random.RandomGen t) =>
t -> (a -> a -> Ordering) -> [a] -> [a]
最后的笔记
qSort对于所有输入的行为将完全相同。 “随机”数据透视选择是。 其实是确定性的。 但是通过对列表进行哈希处理，然后播种一个随机数生成器，使它对我来说“随机”足够了。 ;）
qSort也只适用于长度小于maxBound :: Int ，ghci告诉我的是9,223,372,036,854,775,807。 我认为会有一个负面指标的问题，但在我的临时测试中，我还没有遇到它。
或者，你可以随意使用IO monad以获得“更真实”的随机性。
qSortIO xs = do g <- getStdGen -- add getStdGen to your imports
return $ qSortByGen g compare xs
ghci> :t qSortIO
qSortIO :: (Ord a) => [a] -> IO [a]
ghci> qSortIO "Hello world"
" Hdellloorw"
ghci> qSort "Hello world"
" Hdellloorw"