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

[Edward Kmett]

What does it mean to talk about a monotonic function with Applicative
side-effects (a -> f b) in this setting?

I'm not able to determine how laws for such a beast work.

You can reason about just the pure case easily. That is a strict
generalization, but the whole point of using it is to string together
effects, no?

For *some* instances it is positional. e.g. using a ZipList means that for
each position in the ZipList generated the function must be monotone.

For others it is a global statement. e.g. the list monad to properly be
monotone you'd need to consider the maximal element in each result list
against the minimal element of the next result list

Yes, you can reason it through casewise, by knowing which of the b's in the
f's get merged by the particular Applicative, but the fact that you
*have*to reason it through casewise without being able to express
uniform laws
about the operation indicates to me that it may be a less well defined
notion than you might at first think.

-Edward


On Tue, Mar 11, 2014 at 4:45 AM, John Lato <jwlato at gmail.com> wrote:

> 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.
>
> _______________________________________________
> 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/1df172e4/attachment.html>