On 11/23/10 4:37 AM, Milan Straka wrote:
I'm working on a proposal for adding a Data.HashMap and Data.HashSet type to containers. These types could share most of their implementation with Data.IntMap (and Data.IntSet) but can be (somewhat) more efficiently implemented by specializing IntMap from [...]
Well, there would be another benefit -- if the containers exports the implementation of also Map and Set as a Q [Dec] (that is what you would need for IntMap, right?), then the clients could easily create specialised datatypes for Set and Map, ie. SetWord working as Set Word, containing unboxed Words. Generally it would just need some tweaking in the Q [Dec].
It sounds like TH is a no-go, but it would be nice to try to make the situation a bit better for this sort of thing. For example, the bytestring-trie package[1] has to duplicate all the bit-twiddling logic of IntMap for (essentially) defining a Word8Map, because Data.IntMap doesn't make that logic public. By and large the logic[2] is independent of the actual size of the thing being tried on, and it features some non-trivial optimizations like using shiftRL# and the benchmarking behind the highestBitMask implementation (which is one of the size-dependent parts). Though perhaps updating containers to make the bit-twiddling functions public should be a different proposal. One thing I'd like to see in the proposed Data.HashMap/HashSet implementations is something sufficiently general that the underlying Data.Map/Set can be abstracted out. For instance, Data.Trie is more performant than Map ByteString; and while HashMap ByteString is more performant still, it ends up failing over to Map ByteString which is suboptimal. It'd be nice to have the hooks set up so that it's trivial to implement HashTrie which is a HashMap ByteString that fails over to Trie instead. HashTrie couldn't take advantage of any of the trie structure for manipulating the map, but it could still share the equality/ordering testing to make lookup/insertion faster. [1] Which needs some loving in order to incorporate the latest optimizations from containers. Hopefully this will happen soon :) [2] http://hackage.haskell.org/packages/archive/bytestring-trie/0.2.2/doc/html/s... -- Live well, ~wren