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 <dons@galois.com> wrote:
sedillard:
>    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 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?

-- Don