#9805: Use TrieMaps to speed up type class instance lookup -------------------------------------+------------------------------------- Reporter: ezyang | Owner: ezyang Type: task | Status: new Priority: normal | Milestone: Component: Compiler (Type | Version: 7.9 checker) | Keywords: Resolution: | Architecture: Operating System: Unknown/Multiple | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Revisions: -------------------------------------+------------------------------------- Comment (by ezyang): So, here is an irritating problem with trying to deBruijn number template variables on the fly. First, let's establish that it is desirable for template variables to be deBruijn numbered in order of appearance. This is because if you have instanc heads `C a b` and `C b a` (`a` and `b` being template variable), it would be rather silly if we de Bruijinized these as `C 0 1` and `C 1 0`, when really they're the same. We don't know, a priori, what order the "template quantifiers" should be, so it would be great to defer this choice until we've explored the expression deeply enough to tell. The fly in the ointment is this: with template variables, environment extension happens when we ''encounter a template variable'' (as opposed to de Bruijn numbering lambda/foralls, where extension occurs when we ''encounter a lambda/forall''). So, if I am handling `C ????? a` (where `a` is a template variable), I do not know what the index of `a` will be until I have processed `?????` and determined how many template variables show up for the first time there. Accordingly, my lookup function must ''return'' the new template variable environment, in the same way the unifying match function returns the substitution. This is not completely terrible, since we already were going to need to return extra information on lookup for the unifying match, but it does mean we can't use any of the existing lookup/insert functions to manage template variables. C'est la vie? -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9805#comment:7 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler