[Haskell-beginners] System.Random

[Regis Saint-Paul]

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 at haskell.org [mailto:beginners-bounces at 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 at haskell.org
> http://www.haskell.org/mailman/listinfo/beginners