Niklas Haas | 11 Mar 02:24 2014
Picon

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

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
Edward Kmett | 11 Mar 09:30 2014
Picon

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

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

_______________________________________________
Libraries mailing list
Libraries <at> haskell.org
http://www.haskell.org/mailman/listinfo/libraries
Niklas Haas | 11 Mar 09:37 2014
Picon

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

> 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.
John Lato | 11 Mar 09:45 2014
Picon

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

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
Edward Kmett | 11 Mar 13:38 2014
Picon

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

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


_______________________________________________
Libraries mailing list
Libraries <at> haskell.org
http://www.haskell.org/mailman/listinfo/libraries
Akio Takano | 12 Mar 01:02 2014
Picon

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

Hi,

On Tue, Mar 11, 2014 at 9:38 PM, Edward Kmett <ekmett <at> gmail.com> wrote:
> 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.

Would a definition like the below help?

A function (m :: a -> f b) is monotonic iff for all finite (xs ::
[a]), the following two expressions are equivalent:

isMonotonic <$> traverse (\x -> (x,) <$> m x) xs
True <$ traverse (\x -> (x,) <$> m x) xs

where

isMonotonic :: (Ord a, Ord b) => [(a, b)] -> Bool
isMonotonic xs = and $ zipWith (<=) sorted (drop 1 sorted)
  where sorted = sortBy (compare `on` fst) xs

-- Takano Akio

Gmane