Imagine I have a data structure like so: data E = EAp E E | ELam Int E | ELetRec [(Int,E)] E | EVar Int now, I want to annotate every occurence of E with some pass specific information, such as free variables or levels for lambda lifting. in [PEY91] this technique was used: data EAn a = EaAp (a,EAn a) (a,EAn a) | EaLam Int (a,EAn a) | EaLetRec [(Int,(a,EAn a))] (a,EAn a) | EaVar Int however this suffered from two problems, 1. EAn () is not computationally identical to E, since it has an extra indirection 2. it is anoying to work with EAn () when we don't want to use the extra info, meaning we keep both E and EAn around, despite them being very similar using an idea inspired by [SHEARD01] I came up with the following newtype Id a = Id a type Er f = f (E f) -- E used recursivly data E f = EAp (Er f) (Er f) | ELam Int (Er f) | ELetRec [(Int,Er f)] (Er f) | EVar Int now, this solves problem 1. (E Id) is computationally identical to the original E, however problem 2 persists. If I don't want to be constantly casting to and from Id, I have to use both the seperate annotated and unannotated versions. is this actually the case? is there a better solution I don't see? perhaps something using crazy GHC extensions? if not, are there any proposed extensions which would solve this promlem? if there were some limited way to partially apply a type declaration that would solve the problem, but raise others. perhaps a 'nullary' type constructor, as in type Id = or just type Id so Id is of kind (* -> *) and expands to nothing. then in (E Id) it is fully applied... any other ideas? perhaps some that work :) John [PEY91] http://research.microsoft.com/~simonpj/papers/fully-lazy-lambda-lifter.ps.gz [SHEARD01] http://www.cse.ogi.edu/~sheard/papers/generic.ps -- --------------------------------------------------------------------------- John Meacham - California Institute of Technology, Alum. - john@foo.net ---------------------------------------------------------------------------