Proposal: add laziness to Data.Map / IntMap

[Bertram Felgenhauer]

Scott Dillard wrote:
> 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.

It's not for free. When the compiler does a pattern match on the Bin
constructor, Bin sz kx x l r, it can no longer assume that l and r are
fully evaluated, so it has to add code to evaluate them in case they are
not. And in fact, this code will be needed if any of your proposed lazy
functions are added later. I have not checked whether this has a
measurable performance or code size impact.

> So mapWithKey retains all semantics, including guarantees.

Semantically the change is safe, agreed.

regards,

Bertram