Random pain in Haskell

Random numbers seem to be a bit of a pain in Haskell. Because they are not a “pure” function (they involve hooking up with a system or user-supplied random number generator) there is a little scaffolding involved. Also when the number comes back, it's wrapped in an IO Ref, making the whole of your function impure — causing me at least a fair amount of grief.

I got stuck trying to do something more complicated and then went back to a simpler task: implementing a function pick

 > pick :: [a] -> a

or rather

 > pick :: [a] -> IO a

which will return an element from [a], chosen at random

The first, obvious implementation is

 > pick a = do r <- getStdRandom (randomR (1, length a))
 >             return $ a !! (r-1)

The getStdRandom is the boilerplate I was mentioning (there may be better ways of doing this — I just cargo culted from the Haskell Report) while randomR gives a random integer in the range (min,max) provided.

This is (for once) rather longer than the equivalent Perl

 sub pick { $_[rand( @_ )] }

It's also inefficient, as we have to scan all the elements of a to get the length and then another r elements to do the indexing.

There's a lovely algorithm to choose a random element of a sequence that only involves scanning it once. You start with your first element and select it. You move to the second element, and have a probability of (1/2) of selecting it. You move to the third, with a probability of (1/3)

Here's my code for it:

 > pick :: [a] -> IO a
 > pick []     = undefined
 > pick [x]    = do return x
 > pick (x:xs) = pick' x xs 2
 >
 > pick' :: (Num p, Random p) => t -> [t] -> p -> IO t
 > pick' curr []          _    = do return curr
 > pick' curr (next:rest) prob
 >   = do r <- getStdRandom (randomR (1,prob))
 >        let curr' = if r == 1 then next else curr
 >        pick' curr' rest (prob+1)

Why in the auxhiliary function pick’ does p get typed as Random? As far as I can see, it's just a number, it increases monotonically and only participates in the function randomR as an upper bound.

Now this works in ghci:

 *Main> pick [1,2,3,4,5]
 3

Now if we want a list of random numbers:

 *Main> map (\_ -> pick [1..5]) [1..5]
 <interactive>:1:0:
    No instance for (Show (IO t))
      arising from use of `print' at <interactive>:1:0-32
    Possible fix: add an instance declaration for (Show (IO t))
    In the expression: print it
    In a 'do' expression: print it

This is annoying. OK, maybe an IO value can't be showable because show returns a String, not an IO String, so using Show would allow you to subvert the IO sandbox. Or something. But if ghci can fake it in the case of a single IO value, why can't it do something sensible for a list of IO values?

Some interesting comments also on the algorithm to choose random numbers.  Fair comment that my description of it is a little confusing - by "select", I mean "change the currently selected number for the new number".  But the code is quite clear - evir and Sorear pointed out that Nethack (at least 3.4.3) has a citation of the algorithm and a proof in the comments! (in eat.c Elliott Kleinrock, October 5, 1990)