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">&lt;<a href="mailto:johan.tibell@gmail.com">johan.tibell@gmail.com</a>&gt;</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&#39;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&#39;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>