#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 simonpj): I've taken a look at your straw man. I really don't understand it. What is `TyBox`?? Standing back, I'm sure that the template variables should be deBruijn- ised. And a `VarMap` should look like {{{ data VarMap a = VM { vm_bvar :: BoundVarMap a -- Bound variable , vm_fvar :: VarEnv a -- Free variable , vm_tvar :: TmplVarMap a } -- Template variable type TmplVar = Int -- Like BoundVar but a different namespace type TmplVarMap = IntMap }}} That is, in a key, a variable could be bound by a forall (`vm_bvar`), or free (`bm_fvar`), or a template variable (`vm_tvar`). So a key `(T (forall a. a -> b -> c))`, where b is a template variable and c is free will effectively be treated as {{{ T (forall. bv1 -> tv1 -> c) }}} where I used `bv1` for `BoundVar` 1 and `tv1` for `TmplVar` 1. When doing a `matchT` we must maintain a * `CmEnv`, for deBruijn of the foralls * `TmplVarMap (CmEnv,Type)` for the substitution so far, mapping template variables to types. Well, actually to a kind of lexical closure of `(CmEnv, Type)` (c.f. #9960). When matching, if the key is say (tv1,tv1), then the second time we encounter `tv1` it'll already be bound in the substitution, so we must check for equality with the equality function mentioned in #9960. I don't think an occurs-check can happen when ''matching''. Does that make sense? Happy to talk more, or Skype. Simon -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9805#comment:5 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler