Proposal and discussion: Deprecate Data.Set.mapMonotonic and Data.Map.mapKeysMonotonic; add correctly named functions

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
7 messages Options
Reply | Threaded
Open this post in threaded view
|

Proposal and discussion: Deprecate Data.Set.mapMonotonic and Data.Map.mapKeysMonotonic; add correctly named functions

David Feuer
We currently have a function mapMonotonic in Data.Set and one called
mapKeysMonotonic in Data.Map. These names are confusing for two
reasons:

1. In some mathematical contexts, a function is considered monotonic
if it's *either* increasing or decreasing.

2. Even where monotonic specifically means *increasing*, it generally
does *not* specifically mean *strictly increasing*.

The functions in question work when, and only when, the given function
is strictly increasing on the elements/keys in the set/map.

I'd like to DEPRECATE these functions, and add new ones:

Data.Set: mapStrictlyIncreasing and mapStrictlyDecreasing
Data.Map: mapKeysStrictlyIncreasing and mapKeysStrictlyDecreasing

Data.Map presents another possibility, however. We could make the
replacements more general, giving them types

Ord k => (k -> v -> (k', v')) -> Map k v -> Map k' v'

and allowing the user to map over both keys and values in one pass.

David Feuer
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Proposal and discussion: Deprecate Data.Set.mapMonotonic and Data.Map.mapKeysMonotonic; add correctly named functions

Ivan Lazar Miljenovic
On 9 July 2016 at 03:49, David Feuer <[hidden email]> wrote:

> We currently have a function mapMonotonic in Data.Set and one called
> mapKeysMonotonic in Data.Map. These names are confusing for two
> reasons:
>
> 1. In some mathematical contexts, a function is considered monotonic
> if it's *either* increasing or decreasing.
>
> 2. Even where monotonic specifically means *increasing*, it generally
> does *not* specifically mean *strictly increasing*.
>
> The functions in question work when, and only when, the given function
> is strictly increasing on the elements/keys in the set/map.
>
> I'd like to DEPRECATE these functions, and add new ones:
>
> Data.Set: mapStrictlyIncreasing and mapStrictlyDecreasing
> Data.Map: mapKeysStrictlyIncreasing and mapKeysStrictlyDecreasing

With the latter function also flipping the underlying tree structure?

> Data.Map presents another possibility, however. We could make the
> replacements more general, giving them types
>
> Ord k => (k -> v -> (k', v')) -> Map k v -> Map k' v'
>
> and allowing the user to map over both keys and values in one pass.

Though IIUC this provides no way of specifying that "I'm sure this
function has a 1-1 monotonic relationship so you can just update the
keys without changing the structure" (in the sense of there's no way
to distinguish between the increasing and decreasing sense).

Overall, I'm about +0.5 from the naming sense of the current
functions, but have used these in the past.


--
Ivan Lazar Miljenovic
[hidden email]
http://IvanMiljenovic.wordpress.com
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Proposal and discussion: Deprecate Data.Set.mapMonotonic and Data.Map.mapKeysMonotonic; add correctly named functions

David Feuer


On Jul 8, 2016 7:18 PM, "Ivan Lazar Miljenovic" <[hidden email]> wrote:
>
> On 9 July 2016 at 03:49, David Feuer <[hidden email]> wrote:

> > Data.Set: mapStrictlyIncreasing and mapStrictlyDecreasing
> > Data.Map: mapKeysStrictlyIncreasing and mapKeysStrictlyDecreasing
>
> With the latter function also flipping the underlying tree structure?

I'm not quite sure what you mean, but I think the answer is yes.

mapKeysStrictlyDecreasing (\x -> -x) (fromList [1..10]) === fromList [(-10) .. (-1)]

>
> > Data.Map presents another possibility, however. We could make the
> > replacements more general, giving them types
> >
> > Ord k => (k -> v -> (k', v')) -> Map k v -> Map k' v'
> >
> > and allowing the user to map over both keys and values in one pass.
>
> Though IIUC this provides no way of specifying that "I'm sure this
> function has a 1-1 monotonic relationship so you can just update the
> keys without changing the structure" (in the sense of there's no way
> to distinguish between the increasing and decreasing sense).

That is the pre-condition. There still needs to be one for strictly increasing functions and another for strictly decreasing ones, since they lead to reversed tree structures.

>
> Overall, I'm about +0.5 from the naming sense of the current
> functions, but have used these in the past.

I don't understand this statement.


_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Proposal and discussion: Deprecate Data.Set.mapMonotonic and Data.Map.mapKeysMonotonic; add correctly named functions

Andreas Abel-2
I thought the current functions are quite clear with a bit of common
sense.  They assume the renaming of keys does not change their relative
order, so the underlying tree structure of the map/set can remain as-is.

Of course, as you point out, the names are not precise, but cannot the
documentation add what is not reflected in the names?

The question is, as always, if the breakage caused by the renaming
compensates for having the optimal name.  I am slightly biased against
the renaming.

--Andreas


On 09.07.2016 02:28, David Feuer wrote:

>
> On Jul 8, 2016 7:18 PM, "Ivan Lazar Miljenovic"
> <[hidden email] <mailto:[hidden email]>> wrote:
>  >
>  > On 9 July 2016 at 03:49, David Feuer <[hidden email]
> <mailto:[hidden email]>> wrote:
>
>  > > Data.Set: mapStrictlyIncreasing and mapStrictlyDecreasing
>  > > Data.Map: mapKeysStrictlyIncreasing and mapKeysStrictlyDecreasing
>  >
>  > With the latter function also flipping the underlying tree structure?
>
> I'm not quite sure what you mean, but I think the answer is yes.
>
> mapKeysStrictlyDecreasing (\x -> -x) (fromList [1..10]) === fromList
> [(-10) .. (-1)]
>
>  >
>  > > Data.Map presents another possibility, however. We could make the
>  > > replacements more general, giving them types
>  > >
>  > > Ord k => (k -> v -> (k', v')) -> Map k v -> Map k' v'
>  > >
>  > > and allowing the user to map over both keys and values in one pass.
>  >
>  > Though IIUC this provides no way of specifying that "I'm sure this
>  > function has a 1-1 monotonic relationship so you can just update the
>  > keys without changing the structure" (in the sense of there's no way
>  > to distinguish between the increasing and decreasing sense).
>
> That is the pre-condition. There still needs to be one for strictly
> increasing functions and another for strictly decreasing ones, since
> they lead to reversed tree structures.
>
>  >
>  > Overall, I'm about +0.5 from the naming sense of the current
>  > functions, but have used these in the past.
>
> I don't understand this statement.
>
>
>
> _______________________________________________
> Libraries mailing list
> [hidden email]
> http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
>


--
Andreas Abel  <><      Du bist der geliebte Mensch.

Department of Computer Science and Engineering
Chalmers and Gothenburg University, Sweden

[hidden email]
http://www2.tcs.ifi.lmu.de/~abel/
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Proposal and discussion: Deprecate Data.Set.mapMonotonic and Data.Map.mapKeysMonotonic; add correctly named functions

Edward Kmett-2
I'm also slightly biased against renaming, as the intent is signaled pretty clearly.

-Edward

On Mon, Jul 11, 2016 at 6:12 AM, Andreas Abel <[hidden email]> wrote:
I thought the current functions are quite clear with a bit of common sense.  They assume the renaming of keys does not change their relative order, so the underlying tree structure of the map/set can remain as-is.

Of course, as you point out, the names are not precise, but cannot the documentation add what is not reflected in the names?

The question is, as always, if the breakage caused by the renaming compensates for having the optimal name.  I am slightly biased against the renaming.

--Andreas


On 09.07.2016 02:28, David Feuer wrote:

On Jul 8, 2016 7:18 PM, "Ivan Lazar Miljenovic"
<[hidden email] <mailto:[hidden email]>> wrote:
 >
 > On 9 July 2016 at 03:49, David Feuer <[hidden email]
<mailto:[hidden email]>> wrote:

 > > Data.Set: mapStrictlyIncreasing and mapStrictlyDecreasing
 > > Data.Map: mapKeysStrictlyIncreasing and mapKeysStrictlyDecreasing
 >
 > With the latter function also flipping the underlying tree structure?

I'm not quite sure what you mean, but I think the answer is yes.

mapKeysStrictlyDecreasing (\x -> -x) (fromList [1..10]) === fromList
[(-10) .. (-1)]

 >
 > > Data.Map presents another possibility, however. We could make the
 > > replacements more general, giving them types
 > >
 > > Ord k => (k -> v -> (k', v')) -> Map k v -> Map k' v'
 > >
 > > and allowing the user to map over both keys and values in one pass.
 >
 > Though IIUC this provides no way of specifying that "I'm sure this
 > function has a 1-1 monotonic relationship so you can just update the
 > keys without changing the structure" (in the sense of there's no way
 > to distinguish between the increasing and decreasing sense).

That is the pre-condition. There still needs to be one for strictly
increasing functions and another for strictly decreasing ones, since
they lead to reversed tree structures.

 >
 > Overall, I'm about +0.5 from the naming sense of the current
 > functions, but have used these in the past.

I don't understand this statement.



_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries



--
Andreas Abel  <><      Du bist der geliebte Mensch.

Department of Computer Science and Engineering
Chalmers and Gothenburg University, Sweden

[hidden email]
http://www2.tcs.ifi.lmu.de/~abel/

_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries


_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Proposal and discussion: Deprecate Data.Set.mapMonotonic and Data.Map.mapKeysMonotonic; add correctly named functions

David Feuer

Fine. Sounds like I lose this one. Should the duals be mapAntitone and mapKeysAntitone?

On Jul 12, 2016 1:44 AM, "Edward Kmett" <[hidden email]> wrote:
I'm also slightly biased against renaming, as the intent is signaled pretty clearly.

-Edward

On Mon, Jul 11, 2016 at 6:12 AM, Andreas Abel <[hidden email]> wrote:
I thought the current functions are quite clear with a bit of common sense.  They assume the renaming of keys does not change their relative order, so the underlying tree structure of the map/set can remain as-is.

Of course, as you point out, the names are not precise, but cannot the documentation add what is not reflected in the names?

The question is, as always, if the breakage caused by the renaming compensates for having the optimal name.  I am slightly biased against the renaming.

--Andreas


On 09.07.2016 02:28, David Feuer wrote:

On Jul 8, 2016 7:18 PM, "Ivan Lazar Miljenovic"
<[hidden email] <mailto:[hidden email]>> wrote:
 >
 > On 9 July 2016 at 03:49, David Feuer <[hidden email]
<mailto:[hidden email]>> wrote:

 > > Data.Set: mapStrictlyIncreasing and mapStrictlyDecreasing
 > > Data.Map: mapKeysStrictlyIncreasing and mapKeysStrictlyDecreasing
 >
 > With the latter function also flipping the underlying tree structure?

I'm not quite sure what you mean, but I think the answer is yes.

mapKeysStrictlyDecreasing (\x -> -x) (fromList [1..10]) === fromList
[(-10) .. (-1)]

 >
 > > Data.Map presents another possibility, however. We could make the
 > > replacements more general, giving them types
 > >
 > > Ord k => (k -> v -> (k', v')) -> Map k v -> Map k' v'
 > >
 > > and allowing the user to map over both keys and values in one pass.
 >
 > Though IIUC this provides no way of specifying that "I'm sure this
 > function has a 1-1 monotonic relationship so you can just update the
 > keys without changing the structure" (in the sense of there's no way
 > to distinguish between the increasing and decreasing sense).

That is the pre-condition. There still needs to be one for strictly
increasing functions and another for strictly decreasing ones, since
they lead to reversed tree structures.

 >
 > Overall, I'm about +0.5 from the naming sense of the current
 > functions, but have used these in the past.

I don't understand this statement.



_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries



--
Andreas Abel  <><      Du bist der geliebte Mensch.

Department of Computer Science and Engineering
Chalmers and Gothenburg University, Sweden

[hidden email]
http://www2.tcs.ifi.lmu.de/~abel/

_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries


_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Proposal and discussion: Deprecate Data.Set.mapMonotonic and Data.Map.mapKeysMonotonic; add correctly named functions

Andreas Abel-2
+1  That would be consistent ;)  (in some sense at least).

On 12.07.2016 07:49, David Feuer wrote:

> Fine. Sounds like I lose this one. Should the duals be mapAntitone and
> mapKeysAntitone?
>
> On Jul 12, 2016 1:44 AM, "Edward Kmett" <[hidden email]
> <mailto:[hidden email]>> wrote:
>
>     I'm also slightly biased against renaming, as the intent is signaled
>     pretty clearly.
>
>     -Edward
>
>     On Mon, Jul 11, 2016 at 6:12 AM, Andreas Abel <[hidden email]
>     <mailto:[hidden email]>> wrote:
>
>         I thought the current functions are quite clear with a bit of
>         common sense.  They assume the renaming of keys does not change
>         their relative order, so the underlying tree structure of the
>         map/set can remain as-is.
>
>         Of course, as you point out, the names are not precise, but
>         cannot the documentation add what is not reflected in the names?
>
>         The question is, as always, if the breakage caused by the
>         renaming compensates for having the optimal name.  I am slightly
>         biased against the renaming.
>
>         --Andreas
>
>
>         On 09.07.2016 02:28, David Feuer wrote:
>
>
>             On Jul 8, 2016 7:18 PM, "Ivan Lazar Miljenovic"
>             <[hidden email]
>             <mailto:[hidden email]>
>             <mailto:[hidden email]
>             <mailto:[hidden email]>>> wrote:
>               >
>               > On 9 July 2016 at 03:49, David Feuer
>             <[hidden email] <mailto:[hidden email]>
>             <mailto:[hidden email]
>             <mailto:[hidden email]>>> wrote:
>
>               > > Data.Set: mapStrictlyIncreasing and mapStrictlyDecreasing
>               > > Data.Map: mapKeysStrictlyIncreasing and
>             mapKeysStrictlyDecreasing
>               >
>               > With the latter function also flipping the underlying
>             tree structure?
>
>             I'm not quite sure what you mean, but I think the answer is yes.
>
>             mapKeysStrictlyDecreasing (\x -> -x) (fromList [1..10]) ===
>             fromList
>             [(-10) .. (-1)]
>
>               >
>               > > Data.Map presents another possibility, however. We
>             could make the
>               > > replacements more general, giving them types
>               > >
>               > > Ord k => (k -> v -> (k', v')) -> Map k v -> Map k' v'
>               > >
>               > > and allowing the user to map over both keys and values
>             in one pass.
>               >
>               > Though IIUC this provides no way of specifying that "I'm
>             sure this
>               > function has a 1-1 monotonic relationship so you can
>             just update the
>               > keys without changing the structure" (in the sense of
>             there's no way
>               > to distinguish between the increasing and decreasing sense).
>
>             That is the pre-condition. There still needs to be one for
>             strictly
>             increasing functions and another for strictly decreasing
>             ones, since
>             they lead to reversed tree structures.
>
>               >
>               > Overall, I'm about +0.5 from the naming sense of the current
>               > functions, but have used these in the past.
>
>             I don't understand this statement.
>
>
>
>             _______________________________________________
>             Libraries mailing list
>             [hidden email] <mailto:[hidden email]>
>             http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
>
>
>
>         --
>         Andreas Abel  <><      Du bist der geliebte Mensch.
>
>         Department of Computer Science and Engineering
>         Chalmers and Gothenburg University, Sweden
>
>         [hidden email] <mailto:[hidden email]>
>         http://www2.tcs.ifi.lmu.de/~abel/
>
>         _______________________________________________
>         Libraries mailing list
>         [hidden email] <mailto:[hidden email]>
>         http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
>
>

--
Andreas Abel  <><      Du bist der geliebte Mensch.

Department of Computer Science and Engineering
Chalmers and Gothenburg University, Sweden

[hidden email]
http://www2.tcs.ifi.lmu.de/~abel/
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries