4

是否可以在仍然具有简单Ord a => [a]->[a]签名的 Haskell（使用 RANDOM-PIVOT）中实现快速排序？

我开始理解 Monad，现在，我将 monad 解释为某种“命令模式”，这对 IO 非常有用。

所以，我知道一个返回随机数的函数实际上应该返回一个像 IO 这样的一元值，因为否则它会破坏引用透明度。我也明白应该没有办法从返回的一元值中“提取”随机整数，否则，它会再次破坏引用透明度。

但是，我仍然认为应该可以实现一个“纯”[a]->[a]快速排序功能，即使它使用随机枢轴，因为它是引用透明的。从我的角度来看，随机枢轴只是一个实现细节，不应该改变函数的签名

OBS：我实际上对特定的快速排序问题并不感兴趣（所以，我不想听起来很粗鲁，但我不是在寻找“使用合并排序”或“随机枢轴不会提高实践中的性能”之类的答案）我实际上对如何实现一个在其中使用“不纯”函数的“纯”函数感兴趣，在快速排序等情况下，我可以确保该函数实际上是一个纯函数。

快速排序只是一个很好的例子。

4

4 回答 4

7

您错误地假设选择枢轴点只是一个实现细节。考虑一个集合的偏序。就像对卡片的快速排序

如果面值较小但要评估布尔值，则 card a < card 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 决定。如果您随机选择某些东西，那么您的计算是或可能是不确定的。

于 2011-03-09T03:25:46.640 回答
4

好的，看看这个。

选择从可散列包中复制的部分，以及巫毒魔法语言编译指示。

{-# 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，更多更好的实例在可散列包中，它也允许加盐和其他东西。

这一切只是为了我们可以制作一个数字生成器。

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就像我之前说的：咨询生成器以获取枢轴，对列表进行分区, fork 生成器供两次递归调用使用，递归排序左右两边，然后全部拼接在一起。

方便的功能很容易从这里编写

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 单子以获得“更真实”的随机性。

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"
于 2011-03-09T02:56:58.313 回答
3

在这种情况下，如果您知道该函数是引用透明的，但您无法向编译器证明它，您可以使用unsafePerformIO :: IO a -> a模块中的函数Data.Unsafe。

例如，您可以使用unsafePerformIO获取初始随机状态，然后仅使用此状态执行任何操作。

但请注意：如果不是真的需要，请不要使用它。即便如此，请三思而后行。unsafePerformIO在某种程度上是万恶之源，因为它的后果可能是戏剧性的——从强制不同类型到使用此函数使 RTS 崩溃，任何事情都是可能的。

于 2011-03-08T20:49:46.147 回答
2

Haskell 提供ST monad 来执行具有引用透明结果的非引用透明操作。

请注意，它不强制引用透明度；它只是确保潜在的非参考透明临时状态不会泄漏。没有什么可以阻止您返回以不可重现的方式重新排列的经过处理的纯输入数据。最好的方法是以 ST 和纯方式实现相同的东西，并使用 QuickCheck 在随机输入上比较它们。

于 2011-03-08T20:29:49.703 回答