ОК, проверьте это.
Выберите части, скопированные из хэшируемой упаковки , и прагмы Voodoo Magic Language
{-# 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 работает так же, как я говорил ранее: обратитесь к генератору за сводной информацией, разбить список, разбить генератор для использования в двух рекурсивных вызовах, рекурсивно отсортировать левую и правую стороны и объединить все вместе.
Удобные функции легко составить здесь
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"