containers compiles cleanly with jhc right now, so if you make it depend on
non h2010 features then it would be good to protect them with an #ifdef or
some other mechanism.
John
On Tue, Nov 23, 2010 at 1:25 AM, Johan Tibell
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 -- Libraries mailing list Libraries@haskell.org http://www.haskell.org/mailman/listinfo/libraries