[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)                           |
      Resolution:                    |             Keywords:
Operating System:  Unknown/Multiple  |         Architecture:
                                     |  Unknown/Multiple
 Type of failure:  None/Unknown      |            Test Case:
      Blocked By:                    |             Blocking:
 Related Tickets:                    |  Differential Rev(s):
       Wiki Page:                    |
-------------------------------------+-------------------------------------

Comment (by goldfire):

 The new algorithm should be just as amenable to this new implementation as
 the old one. Yes, it's all tied in with unification (and there are kind
 equalities) but don't let that scare you. In particular, the kind coercion
 passed down through the algorithm is only important in the `TyVar` case
 (and, perhaps, in the `ForAllTy` case, where it's propagated. Does this
 ever actually trigger? Who knows). So I believe this shouldn't cause any
 undue difficulty in realizing your idea (which I think is great).

--
Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/9805#comment:14>
GHC <http://www.haskell.org/ghc/>
The Glasgow Haskell Compiler