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

older
Re: Proposal for containers: Add...

David Feuer

8 Jul 2016 8 Jul '16

1:49 p.m.

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

Show replies by date

Ivan Lazar Miljenovic

8 Jul 8 Jul

7:18 p.m.

On 9 July 2016 at 03:49, David Feuer 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 Ivan.Miljenovic@gmail.com http://IvanMiljenovic.wordpress.com

David Feuer

8:28 p.m.

On Jul 8, 2016 7:18 PM, "Ivan Lazar Miljenovic" wrote:

...

On 9 July 2016 at 03:49, David Feuer 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.

Andreas Abel

11 Jul 11 Jul

6:12 a.m.

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" mailto:ivan.miljenovic@gmail.com> wrote:

...
On 9 July 2016 at 03:49, David Feuer
mailto:david.feuer@gmail.com> 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 Libraries@haskell.org 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 andreas.abel@gu.se http://www2.tcs.ifi.lmu.de/~abel/

Edward Kmett

12 Jul 12 Jul

1:44 a.m.

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 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" mailto:ivan.miljenovic@gmail.com> wrote:

...
On 9 July 2016 at 03:49, David Feuer
mailto:david.feuer@gmail.com> 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 Libraries@haskell.org 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

andreas.abel@gu.se http://www2.tcs.ifi.lmu.de/~abel/

_______________________________________________ Libraries mailing list Libraries@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

David Feuer

1:49 a.m.

Fine. Sounds like I lose this one. Should the duals be mapAntitone and mapKeysAntitone? On Jul 12, 2016 1:44 AM, "Edward Kmett" 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 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" mailto:ivan.miljenovic@gmail.com> wrote:

...
On 9 July 2016 at 03:49, David Feuer
mailto:david.feuer@gmail.com> 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 Libraries@haskell.org 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

andreas.abel@gu.se http://www2.tcs.ifi.lmu.de/~abel/

_______________________________________________ Libraries mailing list Libraries@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

Andreas Abel

10:32 a.m.

+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" mailto:ekmett@gmail.com> 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 mailto:abela@chalmers.se> 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" mailto:ivan.miljenovic@gmail.com mailto:ivan.miljenovic@gmail.com>> wrote: > > On 9 July 2016 at 03:49, David Feuer mailto:david.feuer@gmail.com mailto:david.feuer@gmail.com>> 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 Libraries@haskell.org mailto:Libraries@haskell.org 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

andreas.abel@gu.se mailto:andreas.abel@gu.se http://www2.tcs.ifi.lmu.de/~abel/

_______________________________________________ Libraries mailing list Libraries@haskell.org mailto:Libraries@haskell.org 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 andreas.abel@gu.se http://www2.tcs.ifi.lmu.de/~abel/

3234

Age (days ago)

3238

Last active (days ago)

List overview

Download

6 comments

4 participants

participants (4)

Andreas Abel
David Feuer
Edward Kmett
Ivan Lazar Miljenovic