Can containers depend on Template Haskell?

Milan Straka fox at
Tue Nov 23 04:37:54 EST 2010


> Hi all,
> 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
>     data IntMap a = Nil
>                   | Tip {-# UNPACK #-} !Key a
>                   | Bin {-# UNPACK #-} !Prefix {-# UNPACK #-} !Mask
> !(IntMap a) !(IntMap a)
> to
>     data FullList k v = FL !k v (List k v)
>     data List k v = Nil | Cons !k v (List k v)
>     data IntMap a = Nil
>                   | Tip {-# UNPACK #-} !Hash {-# UNPACK #-} !(FullList k v)
>                   | Bin {-# UNPACK #-} !Prefix {-# UNPACK #-} !Mask
> !(IntMap a) !(IntMap a)
> Unpacking the FullList into the Tip constructor saves one indirection
> and two words of overhead per key/value pair.
> One way to achieve this specialization would be to duplicate the
> implementation of Data.IntMap, but it would be nice to avoid the
> duplication. Template Haskell would allow most of the implementation
> to be shared without sacrificing performance.
> Can containers use Template Haskell? I think the answer is no, but I
> thought I'd check anyway.

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].

I was considering doing this in some containers-exposed-by-th package, but
if the containers could do it by themselves, that would be awesome.
Of course the package could be still compiled by other compilers, it
would just not export the implementations.


More information about the Libraries mailing list