Proposal: add laziness to Data.Map / IntMap

[Scott Dillard]

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 at 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
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/libraries/attachments/20080804/f5e6e5d3/attachment.htm