<div dir="ltr">I think maybe you guys (Don and Andrew) are misunderstanding my proposal. The lazy/strict tradeoff is a subtle issue, and I'll be sure to re-read Okasaki's stuff with this in mind, but what I'm talking about here is not a trade off. It's laziness "for free". Move the strictness annotations out of the constructors and into the library functions using 'seq'. Laziness is exposed through _separate_ functions.<br>
<br>I'll copy again my proposed versions of mapWithKey (because I made a typo the first time)<br><br>mapWithKey :: (k -> a -> b) -> Map k a -> Map k b<br>mapWithKey _ Tip = Tip<br>mapWithKey f (Bin sx kx x l r) <br>
= seq l' $ seq r' $ Bin sx kx (f kx x) l' r'<br> where l' = mapWithKey f l <br> r' = mapWithKey f r<br><br>mapWithKeyLazy _ Tip = Tip<br>mapWithKeyLazy f (Bin sx kx x l r) <br> = Bin sx kx (f kx x) (mapWithKey f l) (mapWithKey f r)<br>
<br>So mapWithKey retains all semantics, including guarantees. So would insert, and all other functions. You export a second API (maybe in a nested module) that exposes laziness. Writing another library is kind of silly since a) you want stricness 90% of the time b) it shares 90% of the code. If maintainers are willing to deal with some extra seqs here and there then we can have both libraries in one.<br>
<br>Scott<br><br><br><div class="gmail_quote">On Mon, Aug 4, 2008 at 6:18 PM, Don Stewart <span dir="ltr"><<a href="mailto:dons@galois.com">dons@galois.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
sedillard:<br>
<div class="Ih2E3d">> Hi,<br>
><br>
> I found myself wanting a lazy version of Data.Map today, and by "lazy" I<br>
> mean in the node-subtree pointers. I trust the library writers when they<br>
> put strictness annotations in the fields of the tree nodes, so I'm<br>
> wondering what the various implications of lazy subtrees are, beyond the<br>
> obvious speed hit. Does this cause space leaks beyond what lazy value<br>
> pointers can already cause? Can someone point me to some reading that<br>
> discusses this?<br>
><br>
> Anyway, I'm positing to libraries (rather than haskell-cafe) to gauge<br>
> opinion about a possible rewrite of Data.Map and IntMap to remove<br>
> strictness annotations (bangs) from the node constructors and move them<br>
> into the functions (as seqs). "Rewrite" is maybe too strong of a word.<br>
> "Significant patch" is more like it. It would involve only those functions<br>
> that construct Bin values directly, which is not that many. Less than a<br>
> days work, I think (yes that means I volunteer.) Semantics of everything<br>
> remains unchanged, but it opens up the possibility for lazy versions of<br>
> some functions.<br>
<br>
</div>How about doing it as a separate library, then we can choose either<br>
strict or lazy as the case may be?<br>
<font color="#888888"><br>
-- Don<br>
</font></blockquote></div><br></div>