[GHC] #9805: Use TrieMaps to speed up type class instance lookup

[GHC]

#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