Can containers depend on Template Haskell?

[wren ng thornton]

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/src/Data-Trie-BitTwiddle.html

-- 
Live well,
~wren