Generating random type-level naturals

[Eric M. Pashman]

I've been playing around with the idea of writing a genetic programming implementation based on the ideas behind HList. Using type-level programming, it's fairly straighforward to put together a program representation that's strongly typed, that supports polymorphism, and that permits only well-typed programs by construction. This has obvious advantages over vanilla GP implementations. But it's impossible to generate arbitrary programs in such a representation using standard Haskell.

Imagine that you have an HList-style heterogenous list of arbitrarily typed Haskell values. It would be nice to be able to pull values from this collection at random and use them to build up random programs. But that's not possible because one can't write a function that outputs a value of arbitrary type. (Or, more or less equivalently, one can't write dependently typed functions, and trying to fake it at the type-level leads to the original problem.)

One can, however, write a bit of Template Haskell to construct a random HNat. Something like,

    hNat 0 = [| hZero |]
    hNat n = [| hSucc $(hNat (n - 1)) |]

Call that with a random positive integer inside a splice and Template Haskell will give you a random HNat that you can use to index an HList. There's your arbitrary Haskell value.

But this technique is of little practical value since it only works at compile-time. I've fiddled around with the hint library, trying to interpret the Template Haskell to get random HNats at run-time. This works, sort of, but there's no way to "liberate" the generated HNat because hint's `interpret` function requires a type witness. A look-alike string from the `eval` function is as close as you can get.

Is there some dirty trick provided by the GHC API that would allow me to bind the generated HNat to a name and pass it around in a way similar to what GHCi seems to do? I realize that I probably have a grossly optimistic idea of what magic GHCi is performing when it interprets user input in a way that seems to allow this sort of thing.

To summarize, I'm basically trying to wrap up the following process programmatically:

    ghci> n <- randomInt       -- A random Int
    ghci> :load SomeModule.hs  -- Contains `hNat` as above
    ghci> let hn = $(hNat n)   -- Voila, a random HNat
    ghci> ...                  -- Do stuff with `hn`, then repeat

Is something along the lines of what I'm imagining possible? If not, can I get close enough for my purposes?

General insights and commentary are welcome as well.

Regards,

Eric