On Sun, Aug 31, 2008 at 11:19 AM, Patrick Perry
"variant" takes a generator and an integer, and produces a generator. Here is how it works in the new version:
First, n gets written in binary:
e.g.
n = 10011
Then, we replace "1" with "fst . split". and we replace "0" with "snd . split".
n' = l . r . r . l . l where l = fst . split r = snd . split
Then, we apply the resulting function to the generator
g' = n' g0
The run time is O (log n).
In the old version, "split" gets called n times, so the run time is O(n). For certain double values, variant gets called with n on the order of 2^30, hence the hang in QuickCheck. The new version of variant employs the same algorithm as in QuickCheck2.
Thanks for the explanation! Cheers, Johan