Proposal: add laziness to Data.Map / IntMap
sedillard at ucdavis.edu
Mon Aug 4 21:17:57 EDT 2008
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.
I'll copy again my proposed versions of mapWithKey (because I made a typo
the first time)
mapWithKey :: (k -> a -> b) -> Map k a -> Map k b
mapWithKey _ Tip = Tip
mapWithKey f (Bin sx kx x l r)
= seq l' $ seq r' $ Bin sx kx (f kx x) l' r'
where l' = mapWithKey f l
r' = mapWithKey f r
mapWithKeyLazy _ Tip = Tip
mapWithKeyLazy f (Bin sx kx x l r)
= Bin sx kx (f kx x) (mapWithKey f l) (mapWithKey f r)
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.
On Mon, Aug 4, 2008 at 6:18 PM, Don Stewart <dons at galois.com> wrote:
> > Hi,
> > I found myself wanting a lazy version of Data.Map today, and by "lazy"
> > mean in the node-subtree pointers. I trust the library writers when
> > put strictness annotations in the fields of the tree nodes, so I'm
> > wondering what the various implications of lazy subtrees are, beyond
> > 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
> > into the functions (as seqs). "Rewrite" is maybe too strong of a
> > "Significant patch" is more like it. It would involve only those
> > that construct Bin values directly, which is not that many. Less than
> > days work, I think (yes that means I volunteer.) Semantics of
> > remains unchanged, but it opens up the possibility for lazy versions
> > some functions.
> How about doing it as a separate library, then we can choose either
> strict or lazy as the case may be?
> -- Don
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the Libraries