praxis

commit 6fc10e62d21cf2e1cdc860049428b413dea8b225
parent 6adc4e376fee9e49756302ee27695ee43f20b10d
Author: Jared Tobin <jared@jtobin.ca>
Date:   Sat,  1 Dec 2012 01:08:32 +1300

Add select exercise.

Diffstat:
A
20091211_select/select.hs
 | 
27
+++++++++++++++++++++++++++

1 file changed, 27 insertions(+), 0 deletions(-)
diff --git a/20091211_select/select.hs b/20091211_select/select.hs
@@ -0,0 +1,27 @@
+import Control.Arrow
+import Control.Monad
+import Control.Monad.Primitive
+import Control.Parallel.Strategies
+import System.Random.MWC
+
+select :: PrimMonad m => Int -> [Int] -> Gen (PrimState m) -> m Int
+select _ [x] _ = return x
+select k xs  g = do
+    pivot <- liftM (xs !!) (uniformR (0, length xs - 1) g)
+
+    let (lesser, greater) = (filter (< pivot) &&& filter (> pivot)) xs `using` parTuple2 rseq rseq
+        nl                = length lesser
+
+    if   nl > k
+    then select k (tail lesser) g
+    else select (k - nl) greater g
+
+main = do
+    g  <- create
+    xs <- replicateM 10000 (uniformR (-100 :: Int, 4000) g)
+
+    k <- uniformR (1 :: Int, 10000) g
+
+    z <- select k xs g
+    print z
+