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
On Wed, May 27, 2009 at 4:55 PM, Thomas Friedrich
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
In general, I don't think you'd use QuickCheck to generate random numbers. QuickCheck is, for the most part, solely for testing. I would write sample1 :: [a] -> StdGen -> a sample :: [a] -> StdGen -> [a] -- defined in terms of sample1 and use the take function to trim the list to the number of items you want. (Lazy evaluation guarantees that the rest won't get evaluated.) Use mkStdGen to create a StdGen to pass to it. Alex
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
Hi, thanks for the web-link. The idea of putting the whole thing into a random shuffling framework is in deed a really neat idea. And it perfectly suits my purpose. I don't need it for QuickCheck, it was just an idea. Cheers, Thomas Regis Saint-Paul wrote:
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
participants (3)
-
Alexander Dunlap -
Regis Saint-Paul -
Thomas Friedrich