Some recent papers from Ross Paterson and Richard Bird [1] examine nested
types and programming techniques associated with them. They use the
extended typing discipline of Hugs with rank-2 polymorphism.
My first question is where I can find documentation on implementing rank-2
polymorphism. How is it done in Hugs and GHC?
My understanding is that with nested datatypes an unbound number of
distinct datatypes can be present even in a single value as opposed to
regular datatypes where one value can be composed only of a limited number
of types.
I am asking because I have an experimental translation scheme in place that
transforms regular polynomial datatypes into C++ (templated) types. This
breaks down when nested datatypes arise, because an unbounded number of
template instantiations have to be created. Since I intend to explore this
translation too, I have to modify my target model.
One way to pursue is to put (a reference to) the run-time representation of
the nested type into (memory layout of) the value, and let the rank-2
functions operate on the run-time representation of the type. Since this is
not needed with values of regular type, this technique would put additional
overhead on them, even if the generality of nested datatypes is not used in
the function.
Are there any other implementation techniques?
Thanks very much,
Gabor
[1] http://www.soi.city.ac.uk/~ross/papers/gfold.html
