[Haskell-cafe] monte carlo trouble

[Chaddaï Fouché]

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
    where
      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.

-- 
Jedaï