[GHC] #9960: Performance problem with TrieMap

[GHC]

#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