Hi, Maybe you'd like to check this page: http://apfelmus.nfshost.com/random-permutations.html which gives also interesting pointers to other references. Your sampling from a list can be seen as taking the first n elements of a permutation of the list. Of course, computing the full permutation of a long list to just take the first two or three elements would not be very wise. So there are other solutions depending on your setting (sampling from a finite list with or without replacement, sampling from an infinite list (a stream) as data comes in, etc... I just give some rough idea: - for fixed size lists, a random number can be used to skip some elements of the list, if you start from the beginning of the list after reaching its end, then you sample with replacement. - for infinite list, a list of the n sampled element is maintained. This list is first filled with the first n elements of the source list and then, for each new incoming element, you decide randomly if you want to keep it or not. If you decide to keep it, you decide, also randomly, which element of the sample list it replaces. You can find all the details in [1]. Do you need that for performing tests with QuickCheck or was using QuickCheck just an idea on how to go about the problem? Best, Regis [1] Vitter, Jeffrey S. 1985. "Random sampling with a reservoir." ACM Trans. Math. Softw. 11(1):37-57.
-----Original Message----- From: beginners-bounces@haskell.org [mailto:beginners-bounces@haskell.org] On Behalf Of Thomas Friedrich Sent: Thursday, 28 May 2009 1:55 AM To: beginners Subject: [Haskell-beginners] System.Random
Hi everyone,
Using random numbers in Haskell is not entirely trivial (at least, still not for me) and again I am bagging my head against the Gen-Monad. I'd like to write a kind of bootstrap function
sample :: Int -> [a] -> [a] sample n xs = ...
that samples uniformly n elements from the list xs. I am not sure how to go about this. Would you try something like
sample1 :: StdGen -> Int -> [a] -> [a]
and later use this in an IO Monad, something along the lines of: do {g <- mkStdGen; return $ sample g n xs}, or would you write it like
sample2 :: Int -> [a] -> Gen [a]
and then use a function from QuickCheck like `generate` to get your samples?
You see, I don't even know how to start thinking about the problem.
If anyone got an idea, I'd be pleased if you could help me.
Cheers, Thomas
_______________________________________________ Beginners mailing list Beginners@haskell.org http://www.haskell.org/mailman/listinfo/beginners