Generating random type-level naturals

José Pedro Magalhães jpm at
Tue Nov 6 14:17:53 CET 2012

Hi Eric,

I'm not sure I fully understand what you want to do, so let me ask a basic
have you considered just using an Arbitrary instance of HsExpr? How would
compare to what you are trying to achieve?


On Mon, Nov 5, 2012 at 11:23 PM, Eric M. Pashman <eric.pashman at>wrote:

> 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
> _______________________________________________
> Glasgow-haskell-users mailing list
> Glasgow-haskell-users at
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <>

More information about the Glasgow-haskell-users mailing list