#9960: Performance problem with TrieMap -------------------------------------+------------------------------------- Reporter: simonpj | Owner: Type: bug | Status: new Priority: normal | Milestone: Component: Compiler | Version: 7.8.4 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: Type of failure: None/Unknown | Unknown/Multiple Blocked By: | Test Case: Related Tickets: | Blocking: | Differential Revisions: Phab:D606 -------------------------------------+------------------------------------- Comment (by ezyang): I had a maybe too clever idea. We need equality over Types, etc; and this equality has to be modulo de Bruijn numbering. In the current proposed design, we bake `CmEnv` into the generic "empty, singleton, many" structure. This isn't great, because what about keys we don't need CmEnv? This got me thinking: maybe we're looking at it wrong: the key in question should be `data ClosedType = ClosedType CmEnv Type`, and we define a TrieMap over *this*. Now, when we define TrieMap instances, we don't have to synthesize an `emptyCME` to pass to the helper functions: we have all the information we need. To make a recursive call, we construct a new `ClosedType` with the updated CME and then call lookup on that. We can even define a plain old `Eq` instance on `ClosedType` respecting de Bruijn indices. `Singleton k v` now automatically stores the `CmEnv`; and we can make some helper functions which default to an `emptyCME`. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9960#comment:6 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler