Use TrieMaps to speed up type class instance lookup
Currently, type class instance resolution is performed by doing a map lookup by type class, and then linearly matching against every instance. This is not great, and for a while, simonpj has been keen on using the TrieMap data structure in GHC, which has been previously used to implement a map from CoreExprs to various things (e.g. for CSE). What makes this a little tricky is that instance lookup isn't intended to be an exact match: we should unify so-called template variables and provide a substitution; furthermore, there may be multiple matches.
After some prototyping, I think we should be able to make this work. The primary refactoring we have to do is *maintain the key associated with an entry in a TrieMap*. Unlike the current uses of TrieMaps, where it's acceptable to lose the underlying key associated with an entry in the TrieMap, we need to know the key when doing unification, because it may be reported in the substitution. There are a few knock-on effects of this:
- We should add a method
foldWithKeyTM :: (Key m -> a -> b -> b) -> m a -> b -> bto the
- We need a variant of
UniqFMwhich tracks the original key that was used. I propose we name it
UniqKM(unique key map). A number of implementations of
TrieMapneed to be adjusted to use this instead of
- Why can't we just represent keyed TrieMaps as
TypeMap (Type, a)? It might be possible. An insurmountable difficulty would be if we need to know the partial key PRIOR to having finished traversing the TrieMap; however, for the parts of the unification algorithm I've implemented, this does not seem to be the case. The primary actual difficulty is that
Typeuses a named representation, whereas
TypeMapkeys are on-the-fly deBruijn numbered. There would at least be some annoying fiddliness.
- Reversing the deBruijn numbered key into a
Typeis a bit goofy. Essentially, you need the reverse of the current
CmEnv: a mapping from de Bruijn levels to the
Varyou've decided to allocate. (I've called this
CfEnvin my prototype)
- When we represent a TrieMap binder, we have to put the binder map on the OUTSIDE, as opposed to the inside as it is currently. Otherwise, we can't update the
CfEnvwith the new mapping before making the recursive call to fold-with-key.
I'll attach the standalone Haskell file I used to prototype this, wherein I copy-pasted a lot of Haskell from GHC's source and implemented fuzzy map on a simplified version of
|Component||Compiler (Type checker)|