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

Niklas Haas haskell at nand.wakku.to
Tue Mar 11 08:37:01 UTC 2014

> 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.

More information about the Libraries mailing list