select.hs (699B)
1 import Control.Arrow 2 import Control.Monad 3 import Control.Monad.Primitive 4 import Control.Parallel.Strategies 5 import System.Random.MWC 6 7 select :: PrimMonad m => Int -> [Int] -> Gen (PrimState m) -> m Int 8 select _ [x] _ = return x 9 select k xs g = do 10 pivot <- liftM (xs !!) (uniformR (0, length xs - 1) g) 11 12 let (lesser, greater) = (filter (< pivot) &&& filter (> pivot)) xs `using` parTuple2 rseq rseq 13 nl = length lesser 14 15 if nl > k 16 then select k (tail lesser) g 17 else select (k - nl) greater g 18 19 main = do 20 g <- create 21 xs <- replicateM 10000 (uniformR (-100 :: Int, 4000) g) 22 23 k <- uniformR (1 :: Int, 10000) g 24 25 z <- select k xs g 26 print z 27