[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