https://stackoverflow.com/questions/16214093
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianDarkOtter's comment mentions QuickCheck's Arbitrary and CoArbitrary classes, which are certainly the first thing you should try. QuickCheck has this instance:
instance (CoArbitrary a, Arbitrary b) => Arbitrary (a -> b) where ...
As it happens, I was just yesterday reading the QuickCheck code to understand how this works, so I can just share what I learned while it's fresh in my mind. QuickCheck is built around a type that looks like this (and this won't be exactly the same):
type Size = Int
-- | A generator for random values of type @a@.
newtype Gen a =
MkGen { -- | Generate a random @a@ using the given randomness source and
-- size.
unGen :: StdGen -> Size -> a
}
class Arbitrary a where
arbitrary :: a -> Gen a
The first trick is that QuickCheck has a function that works like this (and I didn't work out exactly how it's implemented):
-- | Use the given 'Int' to \"perturb\" the generator, i.e., to make a new
-- generator that produces different pseudorandom results than the original.
variant :: Int -> Gen a -> Gen a
Then they use this to implement various instances of this CoArbitrary class:
class CoArbitrary a where
-- | Use the given `a` to perturb some generator.
coarbitrary :: a -> Gen b -> Gen b
-- Example instance: we just treat each 'Bool' value as an 'Int' to perturb with.
instance CoArbitrary Bool where
coarbitrary False = variant 0
coarbitrary True = variant 1
Now with these pieces in place, we want this:
instance (Coarbitrary a, Arbitrary b) => Arbitrary (a -> b) where
arbitrary = ...
I won't write out the implementation, but the idea is this:
- Using the
CoArbitraryinstance ofaand theArbitraryinstance ofbwe can make the function\a -> coarbitrary a arbitrary, which has typea -> Gen b. - Remember that
Gen bis a newtype forStdGen -> Size -> b, so the typea -> Gen bis isomorphic toa -> StdGen -> Size -> b. - We can trivially write a function that takes any function of that latter type and switches the argument order around to return a function of type
StdGen -> Size -> a -> b. - This rearranged type is isomorphic to
Gen (a -> b), so voilà, we pack the rearranged function into aGen, and we got our random function generator!
I would recommend that you read the source of QuickCheck to see this for yourself. When you tackle that, you're only going to run into two extra details that might slow you down. First, the Haskell RandomGen class has this method:
-- | The split operation allows one to obtain two distinct random generators.
split :: RandomGen g => g -> (g, g)
This operation is used in the Monad instance for Gen, and is rather important. One of the tricks here is that the StdGen is a pure pseudo random number generator; the way Gen (a -> b) works is that for each possible value of a we perturb a b generator, use that perturbed generator to generate the b result, but then we never advance the perturbed generator's state; basically the generated a -> b function is a closure over a pseudo-random seed, and each time we call it with some a we use that specific a to deterministically create a new seed, and then use that to deterministically generate a b that depends on a and the hidden seed.
The abbreviated type Seed -> a -> b more or less sums up what's going on—a pseudo-random function is a rule for generating a b from a pseudo-random seed and an a. This won't work with imperative-style stateful random number generators.
Second: instead of directly having a (a -> StdGen -> Size -> b) -> StdGen -> Size -> a -> b function as I describe above, the QuickCheck code has promote :: Monad m => m (Gen a) -> Gen (m a), which is the generalization of that to any Monad. When m is the function instance of Monad, promote coincides with (a -> Gen b) -> Gen (a -> b), so it's really the same as I sketch above.
