More Random fun

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