haskell - How to generate random, typed functions -

i programmatically generate random haskell functions , evaluate them. seems me way generate haskell code programatically , run using ghc api or external process, returning string, , parsing haskell data type. true?

my reasoning follows. functions polymorphic can't use typeable. more importantly, if write own type checker , annotate each function type, can't prove haskell compiler type checker correct. example, when pull 2 functions out of heterogenous collection of functions , apply 1 other, need provide compiler guarantee function i'm using choose these functions chooses functions corresponding types. there no way this, right?

darkotter's comment mentions quickcheck's arbitrary , coarbitrary classes, first thing should try. quickcheck has instance:

instance (coarbitrary a, arbitrary b) => arbitrary (a -> b) ... 

as happens, yesterday reading quickcheck code understand how works, can share learned while it's fresh in mind. quickcheck built around type looks (and won't same):

type size = int  -- | generator random values of type @a@. newtype gen =      mkgen { -- | generate random @a@ using given randomness source ,             -- size.              ungen :: stdgen -> size ->            }  class arbitrary     arbitrary :: -> gen 

the first trick quickcheck has function works (and didn't work out how it's implemented):

-- | use given 'int' \"perturb\" generator, i.e., make new -- generator produces different pseudorandom results original. variant :: int -> gen -> gen 

then use implement various instances of coarbitrary class:

class coarbitrary     -- | use given `a` perturb generator.     coarbitrary :: -> gen b -> gen b  -- example instance: treat each 'bool' value 'int' perturb with. instance coarbitrary bool     coarbitrary false = variant 0     coarbitrary true = variant 1 

now these pieces in place, want this:

instance (coarbitrary a, arbitrary b) => arbitrary (a -> b)     arbitrary = ... 

i won't write out implementation, idea this:

1. using coarbitrary instance of a , arbitrary instance of b can make function \a -> coarbitrary arbitrary, has type a -> gen b.
2. remember gen b newtype stdgen -> size -> b, type a -> gen b isomorphic a -> stdgen -> size -> b.
3. we can trivially write function takes function of latter type , switches argument order around return function of type stdgen -> size -> -> b.
4. this rearranged type isomorphic gen (a -> b), voilà, pack rearranged function gen, , got our random function generator!

i recommend read source of quickcheck see yourself. when tackle that, you're going run 2 details might slow down. first, haskell randomgen class has method:

-- | split operation allows 1 obtain 2 distinct random generators. split :: randomgen g => g -> (g, g) 

this operation used in monad instance gen, , rather important. 1 of tricks here stdgen pure pseudo random number generator; way gen (a -> b) works each possible value of a perturb b generator, use perturbed generator generate b result, never advance perturbed generator's state; generated a -> b function closure on pseudo-random seed, , each time call a use specific a deterministically create new seed, , use deterministically generate b depends on a , hidden seed.

the abbreviated type seed -> -> b more or less sums what's going on—a pseudo-random function rule generating b pseudo-random seed , a. won't work imperative-style stateful random number generators.

second: instead of directly having (a -> stdgen -> size -> b) -> stdgen -> size -> -> b function describe above, quickcheck code has promote :: monad m => m (gen a) -> gen (m a), generalization of monad. when m function instance of monad, promote coincides (a -> gen b) -> gen (a -> b), it's same sketch above.