And HList paper left me with two questions. The first one is how much such an encoding costs both in terms of speed and space. And the second one is can I conveniently define a Storable instance for hlists. As I said before, I need all this machinery to parse a great number of serialized nested C structs from a file.
I'm afraid I've overlooked the part about the great serialized C structs. Serializing HList is easy -- it's de-serialization that is difficult. Essentially, we need to write a mini-type-checker. Sometimes, Template Haskell can help, and we can use GHC's own type-checker. Since the approach you outlined relies on Haskell type-classes to express hierarchies, you'll have the same type-checking problem. You'll have to somehow deduce those type-class constraints during the de-serialization, and convince GHC of them. If you assume a fixed number of classes (C struct types), things become simpler. The HList-based solution becomes just as simple if you assume a fixed number of record types.