Can containers depend on Template Haskell?

Johan Tibell johan.tibell at gmail.com
Tue Nov 23 04:25:04 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.

Johan


More information about the Libraries mailing list