Случайно-сводная быстрая сортировка в Хаскеле
Можно ли реализовать быструю сортировку в Haskell (с помощью RANDOM-PIVOT), которая по-прежнему имеет простой Ord a => [a]->[a] подпись?
Я начинаю понимать монады, и на данный момент я интерпретирую монады как нечто вроде "шаблона команд", который прекрасно работает для ввода-вывода.
Итак, я понимаю, что функция, которая возвращает случайное число, должна на самом деле возвращать монадическое значение, такое как IO, потому что в противном случае она нарушит прозрачность ссылок. Я также понимаю, что не должно быть никакого способа "извлечь" случайное целое число из возвращенного монадического значения, потому что в противном случае это опять-таки нарушило бы прозрачность ссылок.
Но тем не менее, я все еще думаю, что должно быть возможно реализовать "чистый" [a]->[a] Функция быстрой сортировки, даже если она использует случайный шарнир, потому что она прозрачна по ссылкам. С моей точки зрения, случайный стержень - это просто деталь реализации, и он не должен изменять сигнатуру функции.
OBS: Меня на самом деле не интересует конкретная проблема быстрой сортировки (поэтому я не хочу звучать грубо, но я не ищу ответы типа "использовать слияние" или "случайный поворот не повышает производительность на практике") На самом деле меня интересует, как реализовать "чистую" функцию, которая использует "нечистые" функции внутри нее, в таких случаях, как быстрая сортировка, где я могу заверить, что функция на самом деле является чистой.
Быстрая сортировка - просто хороший пример.
4 ответа
В тех случаях, когда вы знаете, что функция прозрачна по ссылкам, но не можете доказать это компилятору, вы можете использовать функцию unsafePerformIO :: IO a -> a из модуля Data.Unsafe,
Например, вы можете использовать unsafePerformIO чтобы получить начальное случайное состояние, а затем сделать что-нибудь, используя только это состояние.
Но, пожалуйста, обратите внимание: не используйте его, если он действительно не нужен. И даже тогда дважды подумай об этом. unsafePerformIO в некоторой степени является корнем всего зла, поскольку его последствия могут быть драматичными - возможно все, от принуждения разных типов до сбоя RTS с помощью этой функции.
Вы делаете ложное предположение, что выбор точки поворота - это просто деталь реализации. Рассмотрим частичное упорядочение на множестве. Как быстрая сортировка на картах, где
card a В этом случае выбор опорных точек будет определять окончательный порядок карт. Точно так же для такой функции, как определяется. Если вы случайно выбираете что-то, то ваши вычисления являются или могут быть недетерминированными. 4 spades < 4 hearts (false)
4 hearts < 4 spades (false)
4 hearts = 4 spades (false)
a = get random integer
b = a + 3
print b
ОК, проверьте это.
Выберите скопированные части из хэш-пакета и прагмы языка магии вуду
{-# 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"
Haskell предоставляет монаду ST для выполнения нереференциально прозрачных действий с референтно прозрачным результатом.
Обратите внимание, что он не обеспечивает ссылочную прозрачность; это просто гарантирует, что потенциально нереферентно-прозрачное временное состояние не может просочиться. Ничто не может помешать вам вернуть обработанные чистые входные данные, которые были преобразованы невоспроизводимым способом. Лучше всего реализовать одну и ту же вещь как ST, так и в чистом виде и использовать QuickCheck для сравнения их на случайных входах.