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.
Scott
On Mon, Aug 4, 2008 at 6:18 PM, Don Stewart
Hi,
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
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
sedillard: they the 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?
-- Don