Proposal: Add strict versions of foldlWithKey and insertLookupWithKey to Data.Map

[tibbe]

This proposal depends on #4277.

The current Data.Map API lacks two important functions:

• A strict left (pre-order) fold -- needed to e.g. sum all the values in a map efficiently.

• A strict insertLookupWithKey' -- needed to e.g. update an integer counter and retrieve the previous value in a single traversal.

The benchmark we ran indicates that foldlWithKey' is 95% faster than its lazy counter part. insertLookupWithKey' is only 6% faster, but the speedup is highly dependent on how many times each element is update. Each element was only updated once in our benchmark so real speedups should be larger.

The consideration period is 3 weeks.

Note that the attached patch includes the dependent patches in the above linked ticket.

[milan]

(In #4311) This patch is no longer blocked by #4278.

[tibbe]

I've attached a patch that adds the foldlWithKey' function. It replaces the earlier patch. Please apply.

N.B. insertLookupWithKey' has already been added in HEAD.

[tibbe]

Discussion thread:  http://www.mail-archive.com/glasgow-haskell-bugs@haskell.org/msg28268.html

Discussion summary:

- Also add a strict right fold (included in the patch) - Force the traversal evaluation order in addition to the accumulator (not done; we don't get the Core we want for the fold so I rather not mess with it until #4267 is resolved). - There are other *WithKey? functions that could need strict versions (not done; out of scope for this proposal).

Patch to apply: strict-fold-with-key.dpatch

[igloo]

Discussion thread is actually here:  http://comments.gmane.org/gmane.comp.lang.haskell.libraries/13544

Reformatting tibbe's summary:

• Also add a strict right fold (included in the patch)
• Force the traversal evaluation order in addition to the accumulator (not done; we don't get the Core we want for the fold so I rather not mess with it until #4267 is resolved).
• There are other *WithKey functions that could need strict versions (not done; out of scope for this proposal).

[igloo]

Re "Force the traversal evaluation order in addition to the accumulator", I thought the conclusion on the thread was that you would make the change? I think without it the semantics are wrong.

[tibbe]

I've attached a new version that forces the traversal as well.

[igloo]

Applied, thanks.