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.<div><br></div><div> John<br><br><div class="gmail_quote">
On Tue, Nov 23, 2010 at 1:25 AM, Johan Tibell <span dir="ltr"><<a href="mailto:johan.tibell@gmail.com">johan.tibell@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;">
Hi all,<br>
<br>
I'm working on a proposal for adding a Data.HashMap and Data.HashSet<br>
type to containers. These types could share most of their<br>
implementation with Data.IntMap (and Data.IntSet) but can be<br>
(somewhat) more efficiently implemented by specializing IntMap from<br>
<br>
data IntMap a = Nil<br>
| Tip {-# UNPACK #-} !Key a<br>
| Bin {-# UNPACK #-} !Prefix {-# UNPACK #-} !Mask<br>
!(IntMap a) !(IntMap a)<br>
<br>
to<br>
<br>
data FullList k v = FL !k v (List k v)<br>
<br>
data List k v = Nil | Cons !k v (List k v)<br>
<br>
data IntMap a = Nil<br>
| Tip {-# UNPACK #-} !Hash {-# UNPACK #-} !(FullList k v)<br>
| Bin {-# UNPACK #-} !Prefix {-# UNPACK #-} !Mask<br>
!(IntMap a) !(IntMap a)<br>
<br>
Unpacking the FullList into the Tip constructor saves one indirection<br>
and two words of overhead per key/value pair.<br>
<br>
One way to achieve this specialization would be to duplicate the<br>
implementation of Data.IntMap, but it would be nice to avoid the<br>
duplication. Template Haskell would allow most of the implementation<br>
to be shared without sacrificing performance.<br>
<br>
Can containers use Template Haskell? I think the answer is no, but I<br>
thought I'd check anyway.<br>
<br>
Johan<br>
<font color="#888888">--<br>
Libraries mailing list<br>
<a href="mailto:Libraries@haskell.org">Libraries@haskell.org</a><br>
<a href="http://www.haskell.org/mailman/listinfo/libraries" target="_blank">http://www.haskell.org/mailman/listinfo/libraries</a><br>
<br>
</font></blockquote></div><br></div>