わかりました、これをチェックしてください。
ハッシュ可能なパッケージからコピーされた部分とブードゥー魔法の言語プラグマを選択します
{-# 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
OK、これで何かのリストを取り、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ジェネレーターを 2 つの異なるジェネレーターにフォークします。
My functions :リストを 3 つのリストに分割するためにpartition使用します。f :: a -> Ordering折り目を知っていれば、それは非常に明確なはずです。（サブリスト内の要素の最初の順序を保持しないことに注意してください。逆にします。foldr を使用すると、問題が解決する可能性があります。）qSortByGen前に述べたように機能します。ピボットのジェネレーターを参照し、リストを分割します。 、2 つの再帰呼び出しで使用するジェネレーターをフォークし、左辺と右辺を再帰的に並べ替え、すべてを連結します。
便利な関数はここから簡単に作成できます
qSortBy f xs = qSortByGen (genFromHashable xs) f xs
qSort = qSortBy compare
最終関数のシグネチャに注意してください。
ghci> :t qSort
qSort :: (Ord a, Hashable a) => [a] -> [a]
Hashableリスト内の型は、 と の両方を実装する必要がありOrdます。あなたが求めていた「純粋な」機能があり、論理的な要件が1つ追加されています。より一般的な機能は、要件の制限が少なくなります。
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。負のインデックスに問題があると思っていましたが、アドホック テストではまだ問題に遭遇していません。
または、「真の」ランダム性のために 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"