DarkOtter'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
CoArbitrary
instance ofa
and theArbitrary
instance ofb
we can make the function\a -> coarbitrary a arbitrary
, which has typea -> Gen b
. - Remember that
Gen b
is a newtype forStdGen -> Size -> b
, so the typea -> Gen b
is 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.