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 `show`able

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?

**update 2007-08-30: **Various people (in comments and on #haskell) pointed out that I should use mapM rather than map to get the behaviour I want. See also sequence. Thanks!

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)