The next obvious functions after â€œPickâ€ are â€œUnpickâ€ to eject a value randomly from the list, and â€œPick Nâ€ values from the list.
unpick is fairly straight-forward. To do in a single pass,
you have to thread through the list of values, but otherwise it's more
or less the same as the previous code for pick
> unpick :: [a] -> IO [a] > unpick  = undefined > unpick [x] = do return  > unpick (x:xs) = do zs <- unpick'  [x] xs 2 > return (reverse zs) > > unpick' :: (Num p, Random p) => [t] -> [t] -> [t] -> p -> IO [t] > unpick' curr orig  _ > = do return curr > unpick' curr orig (next:rest) prob > = do r <- getStdRandom (randomR (1,prob)) > let curr' = if r == 1 then orig else (next:curr) > unpick' curr' (next:orig) rest (prob+1)
To do pickN I'd originally thought of picking the required number, and then following an algorithm similar to that of pick
but dropping one (with unpick) every time I selected a new entry. That
would be quadratic, and also insane. I discussed with dakkar, and we
agreed that it might just be simpler to call something like pick N
times (maybe with a function that returned the picked and the rejected
But, if we know the length of the array things are much easier. We
can just scan the array, selecting elements with a probability of (r/e)
where r is the number of required elements left to be selected, and e
the number of elements left in the array.
> pickN :: Int -> [a] -> IO [a] > pickN n xs = let len = length xs > in pickN' n len xs
And we just need
> pickN' :: Int -> Int -> [a] -> IO [a] > pickN' n l  = do return  > pickN' n l (x:xs) > = do b <- roll n l > if b > then x: (pickN' (n-1) (l-1) xs) > else pickN' n (l-1) xs
and to define the auxhiliary function roll, because I got tired of writing it out all over the place:
> roll p q = do r <- getStdRandom (randomR (1,q)) > return $ r <= p
Which is all great apart from not working. The problem is that
pickNâ€™ returns a monadic value, while x is a pure one. I asked on
#haskell and got help from oerjan, scook0, and DRMacIver.
First of all they suggested:
> if b > then (x:) `liftM` (pickN' (n-1) (l-1) xs) > else pickN' n (l-1) xs
Now I intuitively sort-of-understood what this was doing but not
why. (Bear in mind that I'm still confused about things like â€œwhy do I return this but not that?â€ and â€œHow does it know which Monad it's in?â€)
It turns out that liftM lifts a function with one
pure argument into a function with one monadic argument. But I'm
concatenating x (pure) with picked xs (monadic)! So the section (x:) is actually a pure function specialised to concatenate â€œxâ€ with a pure list (which is the single argument).
My first reaction was a mix of wonder and â€œgood god that's
horribleâ€. As they pointed out though, I could just use another do
> if b > then do xs <- pickN' (n-1) (l-1) xs > return (x:xs) > else pickN' n (l-1) xs
Hurrah! Now I should go and check out a random monad like MonadRandom…