Proposal: add laziness to Data.Map / IntMap
dons at galois.com
Mon Aug 4 20:18:56 EDT 2008
> I found myself wanting a lazy version of Data.Map today, and by "lazy" I
> mean in the node-subtree pointers. I trust the library writers when they
> put strictness annotations in the fields of the tree nodes, so I'm
> wondering what the various implications of lazy subtrees are, beyond the
> obvious speed hit. Does this cause space leaks beyond what lazy value
> pointers can already cause? Can someone point me to some reading that
> discusses this?
> Anyway, I'm positing to libraries (rather than haskell-cafe) to gauge
> opinion about a possible rewrite of Data.Map and IntMap to remove
> strictness annotations (bangs) from the node constructors and move them
> into the functions (as seqs). "Rewrite" is maybe too strong of a word.
> "Significant patch" is more like it. It would involve only those functions
> that construct Bin values directly, which is not that many. Less than a
> days work, I think (yes that means I volunteer.) Semantics of everything
> remains unchanged, but it opens up the possibility for lazy versions of
> some functions.
How about doing it as a separate library, then we can choose either
strict or lazy as the case may be?
More information about the Libraries