[Haskell-cafe] monte carlo trouble

Chaddaï Fouché chaddai.fouche at gmail.com
Wed Aug 15 18:05:14 EDT 2007

2007/8/15, Chad Scherrer <chad.scherrer at gmail.com>:
> If there's a way to lazily sample with replacement from a list without
> even requiring the length of the list to be known in advance, that
> could lead to a solution.

I'm not sure what you mean by "with replacement" but I think it don't
change the fundamental problem. There is in fact a way to get a random
sample from a list without getting it's length first, but it still
require to look at the whole list so it shouldn't change anything
anyway... except if you're dealing with data on disk (which the time
for length() suggests... are you swapping and did you try to push your
data out of RAM ?) where reading is expensive.

Here it is :

getRandomElt :: (RandomGen t) => [a] -> t -> a
getRandomElt (x:xs) g = aux 2 g xs x
      aux _ _ [] y = y
      aux i g (x:xs) y =
          let (r,ng) = randomR (1, i) g in
          if r == 1 then aux (i+1) ng xs x else aux (i+1) ng xs y

There is an equiprobability that each element of the list is chosen.


More information about the Haskell-Cafe mailing list