Random Pivot Quicksort at Haskell

Question

Is it possible to implement quicksort in Haskell (with RANDOM-PIVOT) that still has a simple signature Ord a => [a]->[a] ?

I’m starting to understand Monads, and for now I’m kind of interpreting Monads as something like a “command template” that is great for IO.

So, I understand that a function returning a random number should actually return a monadic value, such as IO, because otherwise it will break referential transparency. I also understand that there should be no way to “extract” a random integer from the returned monadic value, because otherwise it will again break referential transparency.

But, nevertheless, I still think that it should be possible to implement the “pure” [a]->[a] quicksort function, even if it uses a random code because it is transparent in reference. From my point of view, a random bar is just a detail of the implementation and should not change the signature of the function

OBS: I'm really not interested in the specific issue of quicksort (so I don't want to sound rude, but I'm not looking for "use mergesort" or "random core doesn't improve performance in practice" answers). I'm really curious how to implement a “pure” function that uses “unclean” functions in it, in cases like quicksort, where I can assure that the function is actually pure.

Quicksort is a good example.

Answer 1

In such cases, when you know that the function is referentially transparent, but you cannot prove it to the compiler, you can use the unsafePerformIO :: IO a -> a function from the Data.Unsafe module.

For example, you can use unsafePerformIO to get the initial random state, and then do something using only that state.

But note: do not use it if it is not really needed. And even then think twice about it. unsafePerformIO is, in some ways, the root of all evil, because the consequences can be dramatic - everything can be connected with forcing different types to crash RTS using this function.

Answer 2

You make the false assumption that the choice of a fulcrum is just a detail of implementation. Consider a partial order on a set. Like quicksort on maps where

card a <card b if the nominal value is less, but if you had to calculate the logical values:

  4 spades < 4 hearts (false) 4 hearts < 4 spades (false) 4 hearts = 4 spades (false) 

In this case, the choice of control points will determine the final order of the cards. Similar

for a function like

 a = get random integer b = a + 3 print b 

determined by a. If you arbitrarily choose something, then your calculation is or may be non-deterministic.

Answer 3

OK check this out.

Select fragments copied from the hashed package and pragmas of the voodoo 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 

OK, so now we can take a list of something Hashable and turn it into Int . I have provided instances of Char and Integral a ; larger and better instances are in hashed packaging, which also allows salt and more.

That’s all we can do with a number generator.

 genFromHashable = mkStdGen . hash 

So now the fun part. Let a function be written that takes a random number generator, a comparator function, and a list. Then we sort the list by contacting the generator to select the reference element, and the comparator to split the list.

 qSortByGen _ _ [] = [] qSortByGen gf xs = qSortByGen g'' fl ++ mid ++ qSortByGen g''' fr 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 fx of LT -> (x:l,mid,r) EQ -> (l,x:mid,r) GT -> (l,mid,x:r) 

Library Functions : next captures Int from the generator and creates a new generator. split deploys the generator to two different generators.

My functions : partition uses f :: a -> Ordering to split the list into three lists. If you know the folds, this should be perfectly clear. (Note that it does not preserve the initial order of elements in the sublists; it changes them. Using foldr can fix this if this is a problem). qSortByGen works the same way as I said: consult the generator for the fulcrum, split the list, expand the generator for use in two recursive calls, recursively sort the left and right sides and combine it all together.

Convenient features are easy to compose here.

 qSortBy f xs = qSortByGen (genFromHashable xs) f xs qSort = qSortBy compare 

Pay attention to the final signature of the function.

 ghci> :t qSort qSort :: (Ord a, Hashable a) => [a] -> [a] 

The type inside the list must implement both Hashable and Ord . There is a "pure" function that you requested, with one logical additional requirement. More general functions are less stringent in their requirements.

 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] 

Final notes

qSort will behave exactly the same for all inputs. "Random" rotation selection. actually deterministic. But it is obscured by hashing the list, and then by sowing the random number generator, which makes it “random” enough for me.;)

qSort also works only for lists shorter than maxBound :: Int , which, according to ghci, are 9,223,372,036,854,775,807. I thought there would be a problem with negative indices, but in my ad-hoc testing I have not come across this yet.

---

Or you can just live with the IO monad for a "true" coincidence.

 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" 

Answer 4

Haskell provides the ST monad for performing non-core-transparent actions using a referentially transparent result.

Please note that it does not provide referential transparency; it simply ensures that a potentially opaque temporary state cannot leak out. Nothing prevents you from returning managed, clean input that has been rearranged in a non-reproducible manner. It is best to implement the same thing in ST and clean paths, and use QuickCheck to compare them on random inputs.