[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 ezyang):

 I picked this up again. I looked carefully at where the kind coercion is
 used. Specifically:

 * (TyVar case) When matching in `uVar`, it is used to get the two types to
 the same kind so that `eqType` may succeed.
 * (TyVar case) In `uUnrefined`, it is used to ensure that the `TvSubst` is
 well kinded
 * (CoercionTy case) It is used to extend the `CvSubst`

 So, although you don't say it explicitly, I think that I will need to pass
 `kco` around in the TrieMap implementation so that I can implement these
 methods correctly.  One source of awkwardness here is that the TypeMap
 doesn't currently store `CastTy`, which means any coercions induced by
 them will be lost to the ether (I think what needs to be done is just to
 add back a map for CastTy constructor in TypeMap.)

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