[containers] Proposal: Add traverseKeys, traverseKeysWith, traverseKeysMonotonic to Data.Map

[John Lato]

On Tue, Mar 11, 2014 at 1:37 AM, Niklas Haas <haskell at nand.wakku.to> wrote:

> > I have to admit I'm not a huge fan of these functions. The major
> objections
> > that come to mind:
> >
> > * They can't be made to pass the Traversable/Traversal laws and can't be
> > implemented much more efficiently than the naive 'dump it out to a list
> and
> > read it back in' approach, so baking them into the library doesn't add
> much
> >
> > * The names are dreadfully confusing next to combinators like
> > traverseWithKey that *do* pass the laws.
> >
> > * If you use fromDistinctAscList you'll get much of the benefit of the
> > monotonic walk you're doing now. Moreover fromList basically gets almost
> > the same performance as fromDistinctAscList these days. Did you benchmark
> > to see how much the custom traversal helps?
> >
> > Between those concerns I'm currently -1 on adding these.
> >
> > -Edward
>
> Good point about fromDistinctAscList, I didn't think about that.
> I haven't gotten round to benchmarking them yet, I'll do that if anybody
> else expresses interest but otherwise I'm also prepared to let this
> proposal die.
>
> Re: traversal laws, I suppose that would be fair argument for
> dropping or at least changing the names of 'traverseKeys' and
> 'traverseKeysWith', though the traversal laws certainly should hold for
> 'traverseKeysMonotonic'. It may be worth only keeping that version
> around, perhaps depending on whether or not it results in a significant
> speed increase over hand-rolling it with fromDistinctAscList.


I would support adding a slight generalization, `traverseWithKeyMonotonic`,
presuming that it is significantly faster than using fromDistinctAscList.

John L.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/libraries/attachments/20140311/bed2b1a3/attachment.html>