Haskell中的Random-Pivot Quicksort

是否可以在Haskell中实现快速排序（使用RANDOM-PIVOT）仍然具有简单的Ord a => [a]->[a]签名？我开始理解Monads了，而且，就像现在一样，我将monad解释为像'命令模式'这样的东西，这对于IO非常有用。所以，我理解一个返回随机数的函数实际上应该返回一个像IO一样的monadic值，因为否则会破坏引用透明性。我也明白，应该没有办法从返回的monadic值中“提取”随机整数，否则，它会再次破坏参照透明度。但是，我仍然认为应该可以实现'纯'[a]->[a]快速排序功能，即使它使用随机数据透视，因为它是参考透明的。从我的角度来看，随机数据透视只是一个实现细节，不应该改变函数的签名 OBS：我对具体的快速排序问题并不感兴趣（所以，我不想听起来很粗鲁，但我不是在寻找“使用mergesort”或“随机支点不会提高实践中的表现”这种答案）我实际上对如何实现一个在其中使用'impure'函数的'纯'函数感兴趣，例如quicksort，我可以确保函数实际上是纯函数。 Quicksort就是一个很好的例子。

已邀请:

4 个回复

辅奈

在这种情况下，如果您知道该函数是引用透明的，但您无法向编译器证明它，则可以使用模块Data.Unsafe中的函数unsafePerformIO :: IO a -> a。例如，您可以使用unsafePerformIO获得初始随机状态，然后使用此状态执行任何操作。但请注意：如果不是真的需要，请不要使用它。即便如此，请三思而后行。 unsafePerformIO在某种程度上是所有邪恶的根源，因为它的后果可能是戏剧性的 - 任何东西都可以通过强制使用此函数来强制使用不同的类型来破坏RTS。

莽缓逢

你假设选择枢轴点只是一个实现细节。考虑对集合进行部分排序。像卡片上的快速排序一样卡a＆lt;卡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决定的。如果你是随机选择某些东西，那么你的计算是或者可能是非确定性的。

凸晴

好的，看看这个。选择从hashable包中复制的部分，以及voodoo magic language pragma

{-# 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将列表分成三个列表。如果你知道褶皱，那应该很清楚。（请注意，它不会保留子列表中元素的初始顺序;它会反转它们。使用折叠器可以解决这个问题。）qSortByGen就像我之前说过的那样：咨询生成器的枢轴，分区list，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 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"

嘘伪

Haskell使ST monad能够以引用透明的结果执行非引用透明的操作。请注意，它不强制引用透明度;它只是确保潜在的非引用透明的临时状态不会泄漏。没有什么可以阻止您返回以不可重现的方式重新排列的被操纵的纯输入数据。最好是以ST和纯方式实现相同的功能，并使用QuickCheck在随机输入上进行比较。

要回复问题请先登录或注册

Haskell中的Random-Pivot Quicksort

4 个回复

发起人

referential_transparency

quicksort

问题状态

Haskell中的Random-Pivot Quicksort

与内容相关的链接

4 个回复

发起人

referential_transparency

quicksort

问题状态