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

[Edward Kmett]

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


On Mon, Mar 10, 2014 at 9:24 PM, Niklas Haas <haskell at nand.wakku.to> wrote:

> Hello all,
>
> While programming a specific type of map update I came across a great
> need for a 'traverseKeys' function. I ended up making it myself but it
> was still less efficient than it needed to be because my traversal
> function was actually monotonic.
>
> I went ahead and added this along with some variants to Data.Map.
>
> > traverseKeys :: (Applicative f, Ord k2) => (k1 -> f k2) -> Map k1 a -> f
> (Map k2 a)
> > traverseKeysWith :: (Applicative f, Ord k2) => (a -> a -> a) -> (k1 -> f
> k2) -> Map k1 a -> f (Map k2 a)
> > traverseKeysMonotonic :: (Applicative f, Ord k2) => (k1 -> f k2) -> Map
> k1 a -> f (Map k2 a)
>
> A full patch can be found here:
>
> https://github.com/nandykins/containers/commit/a8b0ebd57653bc0a309af69d732356e3572c455c
>
> Let me know what you think,
>
> Discussion period: 2 weeks
> _______________________________________________
> Libraries mailing list
> Libraries at haskell.org
> http://www.haskell.org/mailman/listinfo/libraries
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/libraries/attachments/20140311/0cc6998a/attachment.html>