Proposal: add laziness to Data.Map / IntMap

Bertram Felgenhauer bertram.felgenhauer at
Mon Aug 4 22:53:20 EDT 2008

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.



More information about the Libraries mailing list