Proposal for containers: Add 'pop' function to Data.Map

newer
Numeric supports base 8, 10, 16...

older
containers: symmetricDifference...

Martijn Bastiaan

6 Dec 2020 6 Dec '20

11:19 a.m.

Hi all, Proposal: * Add `pop` and `popWithDefault` to `Data.Map` and `Data.IntMap`. * See https://github.com/haskell/containers/pull/757 for exact definition Why: * They're useful functions I expected to be in `Data.Map` and `Data.IntMap`. (This might be influenced by the fact that they're defined on Python's `dict`.) * Their implementations (~ `updateLookupWithKey (\_ _ -> Nothing)`) are harder to parse than a simple `pop`, which should help Haskell codebases become a bit cleaner :). * Their implementations are a bit non-obvious. My first instinct was to write `(Map.lookup ..., Map.delete ...)`, which would have done two traversals. Having "properly" implemented functions in the lib would prevent people from writing their own suboptimal ones. Details and implementation: * https://github.com/haskell/containers/pull/757 Kind regards, Martijn Bastiaan

Show replies by date

David Feuer

6 Dec 6 Dec

11:25 a.m.

The name pop makes me think of a stack. Is this use of the word common? On Sun, Dec 6, 2020, 11:20 AM Martijn Bastiaan via Libraries < libraries@haskell.org> wrote:

...

Hi all,

Proposal:

* Add `pop` and `popWithDefault` to `Data.Map` and `Data.IntMap`. * See https://github.com/haskell/containers/pull/757 for exact definition

Why:

* They're useful functions I expected to be in `Data.Map` and `Data.IntMap`. (This might be influenced by the fact that they're defined on Python's `dict`.)

* Their implementations (~ `updateLookupWithKey (\_ _ -> Nothing)`) are harder to parse than a simple `pop`, which should help Haskell codebases become a bit cleaner :).

* Their implementations are a bit non-obvious. My first instinct was to write `(Map.lookup ..., Map.delete ...)`, which would have done two traversals. Having "properly" implemented functions in the lib would prevent people from writing their own suboptimal ones.

Details and implementation:

* https://github.com/haskell/containers/pull/757

Kind regards, Martijn Bastiaan _______________________________________________ Libraries mailing list Libraries@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

Tom Ellis

11:29 a.m.

On Sun, Dec 06, 2020 at 11:25:33AM -0500, David Feuer wrote:

...

The name pop makes me think of a stack. Is this use of the word common?

Python uses that name, which is why I'm familiar with it:

...

...
...
d = {'a': 1, 'b': 2} d.pop('b') 2 d {'a': 1}

Martijn Bastiaan

11:40 a.m.

Yeah, Python's `pop` made me call it `pop`. I had hoped to find other examples, but Java, Rust, and Ruby don't seem to offer `pop`-like functions for their (hash)maps. On 12/6/20 5:29 PM, Tom Ellis wrote:

...

On Sun, Dec 06, 2020 at 11:25:33AM -0500, David Feuer wrote:

...
The name pop makes me think of a stack. Is this use of the word common? Python uses that name, which is why I'm familiar with it:

...
...
...
d = {'a': 1, 'b': 2} d.pop('b') 2 d {'a': 1}

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

David Feuer

11:43 a.m.

I suggest you add a version for Data.Sequence combining lookup with deleteAt. I wanted that for something fairly recently. On Sun, Dec 6, 2020, 11:41 AM Martijn Bastiaan via Libraries < libraries@haskell.org> wrote:

...

Yeah, Python's `pop` made me call it `pop`. I had hoped to find other examples, but Java, Rust, and Ruby don't seem to offer `pop`-like functions for their (hash)maps.

On 12/6/20 5:29 PM, Tom Ellis wrote:

...
On Sun, Dec 06, 2020 at 11:25:33AM -0500, David Feuer wrote:

...
The name pop makes me think of a stack. Is this use of the word common? Python uses that name, which is why I'm familiar with it:

...
...
...
d = {'a': 1, 'b': 2} d.pop('b') 2 d {'a': 1}

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

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

Carter Schonwald

12:16 p.m.

LookupThenRemove seems like a more descriptive name. Though I guess I can see why pop has appeal. On Sun, Dec 6, 2020 at 11:44 AM David Feuer wrote:

...

I suggest you add a version for Data.Sequence combining lookup with deleteAt. I wanted that for something fairly recently.

On Sun, Dec 6, 2020, 11:41 AM Martijn Bastiaan via Libraries < libraries@haskell.org> wrote:

...
Yeah, Python's `pop` made me call it `pop`. I had hoped to find other examples, but Java, Rust, and Ruby don't seem to offer `pop`-like functions for their (hash)maps.

On 12/6/20 5:29 PM, Tom Ellis wrote:

...
On Sun, Dec 06, 2020 at 11:25:33AM -0500, David Feuer wrote:

...
The name pop makes me think of a stack. Is this use of the word common? Python uses that name, which is why I'm familiar with it:

...
...
...
d = {'a': 1, 'b': 2} d.pop('b') 2 d {'a': 1}

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

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

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

David Feuer

12:25 p.m.

Or lookupRemove? Or possibly lookupAndRemove? The name pop will be confusing in Data.Sequence. On Sun, Dec 6, 2020, 12:17 PM Carter Schonwald wrote:

...

LookupThenRemove seems like a more descriptive name. Though I guess I can see why pop has appeal.

On Sun, Dec 6, 2020 at 11:44 AM David Feuer wrote:

...
I suggest you add a version for Data.Sequence combining lookup with deleteAt. I wanted that for something fairly recently.

On Sun, Dec 6, 2020, 11:41 AM Martijn Bastiaan via Libraries < libraries@haskell.org> wrote:

...
Yeah, Python's `pop` made me call it `pop`. I had hoped to find other examples, but Java, Rust, and Ruby don't seem to offer `pop`-like functions for their (hash)maps.

On 12/6/20 5:29 PM, Tom Ellis wrote:

...
On Sun, Dec 06, 2020 at 11:25:33AM -0500, David Feuer wrote:

...
The name pop makes me think of a stack. Is this use of the word common? Python uses that name, which is why I'm familiar with it:

...
...
> d = {'a': 1, 'b': 2} > d.pop('b') 2 > d {'a': 1}

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

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

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

Alexey Kuleshevich

12:29 p.m.

`extract` is the name that I would suggest. I also agree with David that `pop` is a bit too confusing in a non-stack/queue data structure. If all languages named it pop, then it would be good argument for the name, but we don't need to copy python. The only thing that pyhon has that I wish we had in Haskell is the popularity ;) +1 on the function itself from me, I've needed it multiple occasions. ‐‐‐‐‐‐‐ Original Message ‐‐‐‐‐‐‐ On Sunday, December 6, 2020 8:16 PM, Carter Schonwald wrote:

...

LookupThenRemove seems like a more descriptive name. Though I guess I can see why pop has appeal.

On Sun, Dec 6, 2020 at 11:44 AM David Feuer wrote:

...
I suggest you add a version for Data.Sequence combining lookup with deleteAt. I wanted that for something fairly recently.

On Sun, Dec 6, 2020, 11:41 AM Martijn Bastiaan via Libraries wrote:

...
Yeah, Python's `pop` made me call it `pop`. I had hoped to find other examples, but Java, Rust, and Ruby don't seem to offer `pop`-like functions for their (hash)maps.

On 12/6/20 5:29 PM, Tom Ellis wrote:

...
On Sun, Dec 06, 2020 at 11:25:33AM -0500, David Feuer wrote:

...
The name pop makes me think of a stack. Is this use of the word common? Python uses that name, which is why I'm familiar with it:

...
...
> d = {'a': 1, 'b': 2} > d.pop('b') 2 > d {'a': 1}

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

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

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

Tom Ellis

12:34 p.m.

I really like `extract`! On Sun, Dec 06, 2020 at 05:29:40PM +0000, Alexey Kuleshevich wrote:

...

`extract` is the name that I would suggest. I also agree with David that `pop` is a bit too confusing in a non-stack/queue data structure. If all languages named it pop, then it would be good argument for the name, but we don't need to copy python. The only thing that pyhon has that I wish we had in Haskell is the popularity ;)

‐‐‐‐‐‐‐ Original Message ‐‐‐‐‐‐‐ On Sunday, December 6, 2020 8:16 PM, Carter Schonwald wrote:

...
LookupThenRemove seems like a more descriptive name. Though I guess I can see why pop has appeal.

On Sun, Dec 6, 2020 at 11:44 AM David Feuer wrote:

...
I suggest you add a version for Data.Sequence combining lookup with deleteAt. I wanted that for something fairly recently.

On Sun, Dec 6, 2020, 11:41 AM Martijn Bastiaan via Libraries wrote:

...
Yeah, Python's `pop` made me call it `pop`. I had hoped to find other examples, but Java, Rust, and Ruby don't seem to offer `pop`-like functions for their (hash)maps.

On 12/6/20 5:29 PM, Tom Ellis wrote:

...
On Sun, Dec 06, 2020 at 11:25:33AM -0500, David Feuer wrote:

...
The name pop makes me think of a stack. Is this use of the word common? Python uses that name, which is why I'm familiar with it:

...
>> d = {'a': 1, 'b': 2} >> d.pop('b') 2 >> d {'a': 1}

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

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

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

...

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

Bob Ippolito

12:59 p.m.

`extract` overlaps with the Comonad typeclass (extract, duplicate, extend) On Sun, Dec 6, 2020 at 9:34 AM Tom Ellis < tom-lists-haskell-cafe-2017@jaguarpaw.co.uk> wrote:

...

I really like `extract`!

...
`extract` is the name that I would suggest. I also agree with David that `pop` is a bit too confusing in a non-stack/queue data structure. If all languages named it pop, then it would be good argument for the name, but we don't need to copy python. The only thing that pyhon has that I wish we had in Haskell is the popularity ;)

‐‐‐‐‐‐‐ Original Message ‐‐‐‐‐‐‐ On Sunday, December 6, 2020 8:16 PM, Carter Schonwald < carter.schonwald@gmail.com> wrote:

...
LookupThenRemove seems like a more descriptive name. Though I guess I can see why pop has appeal.

On Sun, Dec 6, 2020 at 11:44 AM David Feuer wrote:

...
I suggest you add a version for Data.Sequence combining lookup with deleteAt. I wanted that for something fairly recently.

On Sun, Dec 6, 2020, 11:41 AM Martijn Bastiaan via Libraries <

On Sun, Dec 06, 2020 at 05:29:40PM +0000, Alexey Kuleshevich wrote: libraries@haskell.org> wrote:

...
...
...
...
Yeah, Python's `pop` made me call it `pop`. I had hoped to find other examples, but Java, Rust, and Ruby don't seem to offer `pop`-like functions for their (hash)maps.

On 12/6/20 5:29 PM, Tom Ellis wrote:

...
On Sun, Dec 06, 2020 at 11:25:33AM -0500, David Feuer wrote: > The name pop makes me think of a stack. Is this use of the word

common?

...
...
...
Python uses that name, which is why I'm familiar with it:

>>> d = {'a': 1, 'b': 2} >>> d.pop('b') 2 >>> d {'a': 1} _______________________________________________ Libraries mailing list Libraries@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

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

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

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

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

David Feuer

1:02 p.m.

None of these types are comonads, so it doesn't seem *that* confusing. On Sun, Dec 6, 2020, 12:59 PM Bob Ippolito wrote:

...

`extract` overlaps with the Comonad typeclass (extract, duplicate, extend)

On Sun, Dec 6, 2020 at 9:34 AM Tom Ellis < tom-lists-haskell-cafe-2017@jaguarpaw.co.uk> wrote:

...
I really like `extract`!

...
`extract` is the name that I would suggest. I also agree with David that `pop` is a bit too confusing in a non-stack/queue data structure. If all languages named it pop, then it would be good argument for the name, but we don't need to copy python. The only thing that pyhon has that I wish we had in Haskell is the popularity ;)

‐‐‐‐‐‐‐ Original Message ‐‐‐‐‐‐‐ On Sunday, December 6, 2020 8:16 PM, Carter Schonwald < carter.schonwald@gmail.com> wrote:

...
LookupThenRemove seems like a more descriptive name. Though I guess I can see why pop has appeal.

On Sun, Dec 6, 2020 at 11:44 AM David Feuer wrote:

...
I suggest you add a version for Data.Sequence combining lookup with deleteAt. I wanted that for something fairly recently.

On Sun, Dec 6, 2020, 11:41 AM Martijn Bastiaan via Libraries <

On Sun, Dec 06, 2020 at 05:29:40PM +0000, Alexey Kuleshevich wrote: libraries@haskell.org> wrote:

...
...
...
...
Yeah, Python's `pop` made me call it `pop`. I had hoped to find

other

...
...
examples, but Java, Rust, and Ruby don't seem to offer `pop`-like functions for their (hash)maps.

On 12/6/20 5:29 PM, Tom Ellis wrote: > On Sun, Dec 06, 2020 at 11:25:33AM -0500, David Feuer wrote: >> The name pop makes me think of a stack. Is this use of the word common? > Python uses that name, which is why I'm familiar with it: > >>>> d = {'a': 1, 'b': 2} >>>> d.pop('b') > 2 >>>> d > {'a': 1} > _______________________________________________ > Libraries mailing list > Libraries@haskell.org > http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries _______________________________________________ Libraries mailing list Libraries@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

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

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

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

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

Oleg Grenrus

1:04 p.m.

NonEmptySeq could be. NonEmptySet almost (it could have extract). - Oleg On 6.12.2020 20.02, David Feuer wrote:

...

None of these types are comonads, so it doesn't seem *that* confusing.

On Sun, Dec 6, 2020, 12:59 PM Bob Ippolito mailto:bob@redivi.com> wrote:

`extract` overlaps with the Comonad typeclass (extract, duplicate, extend)

On Sun, Dec 6, 2020 at 9:34 AM Tom Ellis mailto:tom-lists-haskell-cafe-2017@jaguarpaw.co.uk> wrote:

I really like `extract`!

On Sun, Dec 06, 2020 at 05:29:40PM +0000, Alexey Kuleshevich wrote: > `extract` is the name that I would suggest. I also agree with David > that `pop` is a bit too confusing in a non-stack/queue data > structure. If all languages named it pop, then it would be good > argument for the name, but we don't need to copy python. The only > thing that pyhon has that I wish we had in Haskell is the popularity > ;) > > ‐‐‐‐‐‐‐ Original Message ‐‐‐‐‐‐‐ > On Sunday, December 6, 2020 8:16 PM, Carter Schonwald mailto:carter.schonwald@gmail.com> wrote: > > > LookupThenRemove seems like a more descriptive name. Though I guess I can see why pop has appeal. > > > > On Sun, Dec 6, 2020 at 11:44 AM David Feuer mailto:david.feuer@gmail.com> wrote: > > > >> I suggest you add a version for Data.Sequence combining lookup with deleteAt. I wanted that for something fairly recently. > >> > >> On Sun, Dec 6, 2020, 11:41 AM Martijn Bastiaan via Libraries mailto:libraries@haskell.org> wrote: > >> > >>> Yeah, Python's `pop` made me call it `pop`. I had hoped to find other > >>> examples, but Java, Rust, and Ruby don't seem to offer `pop`-like > >>> functions for their (hash)maps. > >>> > >>> On 12/6/20 5:29 PM, Tom Ellis wrote: > >>>> On Sun, Dec 06, 2020 at 11:25:33AM -0500, David Feuer wrote: > >>>>> The name pop makes me think of a stack. Is this use of the word common? > >>>> Python uses that name, which is why I'm familiar with it: > >>>> > >>>>>>> d = {'a': 1, 'b': 2} > >>>>>>> d.pop('b') > >>>> 2 > >>>>>>> d > >>>> {'a': 1} > >>>> _______________________________________________ > >>>> Libraries mailing list > >>>> Libraries@haskell.org mailto:Libraries@haskell.org > >>>> http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries > >>> _______________________________________________ > >>> Libraries mailing list > >>> Libraries@haskell.org mailto:Libraries@haskell.org > >>> http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries > >> > >> _______________________________________________ > >> Libraries mailing list > >> Libraries@haskell.org mailto:Libraries@haskell.org > >> http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

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

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

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

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

David Feuer

1:26 p.m.

I guess the real point is that I don't think most people will expect an `extract` function in `containers` to be a comonadic one. On Sun, Dec 6, 2020, 1:05 PM Oleg Grenrus wrote:

...

NonEmptySeq could be. NonEmptySet almost (it could have extract).

- Oleg On 6.12.2020 20.02, David Feuer wrote:

None of these types are comonads, so it doesn't seem *that* confusing.

On Sun, Dec 6, 2020, 12:59 PM Bob Ippolito wrote:

...
`extract` overlaps with the Comonad typeclass (extract, duplicate, extend)

On Sun, Dec 6, 2020 at 9:34 AM Tom Ellis < tom-lists-haskell-cafe-2017@jaguarpaw.co.uk> wrote:

...
I really like `extract`!

...
`extract` is the name that I would suggest. I also agree with David that `pop` is a bit too confusing in a non-stack/queue data structure. If all languages named it pop, then it would be good argument for the name, but we don't need to copy python. The only thing that pyhon has that I wish we had in Haskell is the popularity ;)

‐‐‐‐‐‐‐ Original Message ‐‐‐‐‐‐‐ On Sunday, December 6, 2020 8:16 PM, Carter Schonwald < carter.schonwald@gmail.com> wrote:

...
LookupThenRemove seems like a more descriptive name. Though I guess I can see why pop has appeal.

On Sun, Dec 6, 2020 at 11:44 AM David Feuer wrote:

...
I suggest you add a version for Data.Sequence combining lookup with deleteAt. I wanted that for something fairly recently.

On Sun, Dec 6, 2020, 11:41 AM Martijn Bastiaan via Libraries <

On Sun, Dec 06, 2020 at 05:29:40PM +0000, Alexey Kuleshevich wrote: libraries@haskell.org> wrote:

...
...
...
> Yeah, Python's `pop` made me call it `pop`. I had hoped to find

other

...
> examples, but Java, Rust, and Ruby don't seem to offer `pop`-like > functions for their (hash)maps. > > On 12/6/20 5:29 PM, Tom Ellis wrote: >> On Sun, Dec 06, 2020 at 11:25:33AM -0500, David Feuer wrote: >>> The name pop makes me think of a stack. Is this use of the word common? >> Python uses that name, which is why I'm familiar with it: >> >>>>> d = {'a': 1, 'b': 2} >>>>> d.pop('b') >> 2 >>>>> d >> {'a': 1} >> _______________________________________________ >> Libraries mailing list >> Libraries@haskell.org >> http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries > _______________________________________________ > Libraries mailing list > Libraries@haskell.org > http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

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

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

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

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

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

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

Andreas Abel

1:38 p.m.

I have reservations against this proposal: 1. `pop` seems to be below the Fairbairn threshold.

...

pop :: Int -> IntMap a -> (Maybe a, IntMap a) pop = updateLookupWithKey (\_ _ -> Nothing)

It specializes the Swiss knife `updateLookupWithKey` without involving any other map-specific function. 2. Addition of `pop` would require a similar function in all other standard collections, to keep their interfaces in sync. 3. Is there sufficient evidence that `pop` is a strongly user-demanded feature? One way to quantify this is to look on hackage for the pattern `updateLookupWithKey (\_ _ -> Nothing)` (and variants) and maybe even on how often this pattern has been given a name. (The latter would be a more scientific way to develop our libraries in general. Instead of randomly adding functionality based on non-representative discussions on this list, we could scan hackage for common patterns---especially, mine popular utility libraries. Harvest the intelligence of the masses...) While I would not recommend to add `pop`, I would recommend to enhance the documentation of `updateLookupWithKey` to include `pop` as a use case. This would also ensure the discoverability of the present solution. I seem to recall that we have given this recommendation to similar proposals in the past ("similar" in terms of the Fairbairn threshold). Cheers, Andreas On 2020-12-06 19:04, Oleg Grenrus wrote:

...

NonEmptySeq could be. NonEmptySet almost (it could have extract).

- Oleg

On 6.12.2020 20.02, David Feuer wrote:

...
None of these types are comonads, so it doesn't seem *that* confusing.

On Sun, Dec 6, 2020, 12:59 PM Bob Ippolito mailto:bob@redivi.com> wrote:

`extract` overlaps with the Comonad typeclass (extract, duplicate, extend)

On Sun, Dec 6, 2020 at 9:34 AM Tom Ellis mailto:tom-lists-haskell-cafe-2017@jaguarpaw.co.uk> wrote:

I really like `extract`!

On Sun, Dec 06, 2020 at 05:29:40PM +0000, Alexey Kuleshevich wrote: > `extract` is the name that I would suggest. I also agree with David > that `pop` is a bit too confusing in a non-stack/queue data > structure. If all languages named it pop, then it would be good > argument for the name, but we don't need to copy python. The only > thing that pyhon has that I wish we had in Haskell is the popularity > ;) > > ‐‐‐‐‐‐‐ Original Message ‐‐‐‐‐‐‐ > On Sunday, December 6, 2020 8:16 PM, Carter Schonwald mailto:carter.schonwald@gmail.com> wrote: > > > LookupThenRemove seems like a more descriptive name. Though I guess I can see why pop has appeal. > > > > On Sun, Dec 6, 2020 at 11:44 AM David Feuer mailto:david.feuer@gmail.com> wrote: > > > >> I suggest you add a version for Data.Sequence combining lookup with deleteAt. I wanted that for something fairly recently. > >> > >> On Sun, Dec 6, 2020, 11:41 AM Martijn Bastiaan via Libraries mailto:libraries@haskell.org> wrote: > >> > >>> Yeah, Python's `pop` made me call it `pop`. I had hoped to find other > >>> examples, but Java, Rust, and Ruby don't seem to offer `pop`-like > >>> functions for their (hash)maps. > >>> > >>> On 12/6/20 5:29 PM, Tom Ellis wrote: > >>>> On Sun, Dec 06, 2020 at 11:25:33AM -0500, David Feuer wrote: > >>>>> The name pop makes me think of a stack. Is this use of the word common? > >>>> Python uses that name, which is why I'm familiar with it: > >>>> > >>>>>>> d = {'a': 1, 'b': 2} > >>>>>>> d.pop('b') > >>>> 2 > >>>>>>> d > >>>> {'a': 1} > >>>> _______________________________________________ > >>>> Libraries mailing list > >>>> Libraries@haskell.org mailto:Libraries@haskell.org > >>>> http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries > >>> _______________________________________________ > >>> Libraries mailing list > >>> Libraries@haskell.org mailto:Libraries@haskell.org > >>> http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries > >> > >> _______________________________________________ > >> Libraries mailing list > >> Libraries@haskell.org mailto:Libraries@haskell.org > >> http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

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

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

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

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

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

Carter Schonwald

4:37 p.m.

Well said Andreas, I emphatically agree with your latter point: We need to ground proposal need / utility with statistical information about actual code out in the world. On Sun, Dec 6, 2020 at 1:38 PM Andreas Abel wrote:

...

I have reservations against this proposal:

1. `pop` seems to be below the Fairbairn threshold.

...
pop :: Int -> IntMap a -> (Maybe a, IntMap a) pop = updateLookupWithKey (\_ _ -> Nothing)

It specializes the Swiss knife `updateLookupWithKey` without involving any other map-specific function.

2. Addition of `pop` would require a similar function in all other standard collections, to keep their interfaces in sync.

3. Is there sufficient evidence that `pop` is a strongly user-demanded feature? One way to quantify this is to look on hackage for the pattern `updateLookupWithKey (\_ _ -> Nothing)` (and variants) and maybe even on how often this pattern has been given a name.

(The latter would be a more scientific way to develop our libraries in general. Instead of randomly adding functionality based on non-representative discussions on this list, we could scan hackage for common patterns---especially, mine popular utility libraries. Harvest the intelligence of the masses...)

While I would not recommend to add `pop`, I would recommend to enhance the documentation of `updateLookupWithKey` to include `pop` as a use case. This would also ensure the discoverability of the present solution.

I seem to recall that we have given this recommendation to similar proposals in the past ("similar" in terms of the Fairbairn threshold).

Cheers, Andreas

On 2020-12-06 19:04, Oleg Grenrus wrote:

...
NonEmptySeq could be. NonEmptySet almost (it could have extract).

- Oleg

On 6.12.2020 20.02, David Feuer wrote:

...
None of these types are comonads, so it doesn't seem *that* confusing.

On Sun, Dec 6, 2020, 12:59 PM Bob Ippolito mailto:bob@redivi.com> wrote:

`extract` overlaps with the Comonad typeclass (extract, duplicate, extend)

On Sun, Dec 6, 2020 at 9:34 AM Tom Ellis mailto:tom-lists-haskell-cafe-2017@jaguarpaw.co.uk> wrote:

I really like `extract`!

On Sun, Dec 06, 2020 at 05:29:40PM +0000, Alexey Kuleshevich wrote: > `extract` is the name that I would suggest. I also agree with David > that `pop` is a bit too confusing in a non-stack/queue data > structure. If all languages named it pop, then it would be good > argument for the name, but we don't need to copy python. The only > thing that pyhon has that I wish we had in Haskell is the popularity > ;) > > ‐‐‐‐‐‐‐ Original Message ‐‐‐‐‐‐‐ > On Sunday, December 6, 2020 8:16 PM, Carter Schonwald mailto:carter.schonwald@gmail.com> wrote: > > > LookupThenRemove seems like a more descriptive name. Though I guess I can see why pop has appeal. > > > > On Sun, Dec 6, 2020 at 11:44 AM David Feuer mailto:david.feuer@gmail.com> wrote: > > > >> I suggest you add a version for Data.Sequence combining lookup with deleteAt. I wanted that for something fairly recently. > >> > >> On Sun, Dec 6, 2020, 11:41 AM Martijn Bastiaan via Libraries mailto:libraries@haskell.org> wrote: > >> > >>> Yeah, Python's `pop` made me call it `pop`. I had hoped to find other > >>> examples, but Java, Rust, and Ruby don't seem to offer `pop`-like > >>> functions for their (hash)maps. > >>> > >>> On 12/6/20 5:29 PM, Tom Ellis wrote: > >>>> On Sun, Dec 06, 2020 at 11:25:33AM -0500, David Feuer wrote: > >>>>> The name pop makes me think of a stack. Is this use of the word common? > >>>> Python uses that name, which is why I'm familiar with it: > >>>> > >>>>>>> d = {'a': 1, 'b': 2} > >>>>>>> d.pop('b') > >>>> 2 > >>>>>>> d > >>>> {'a': 1} > >>>> _______________________________________________ > >>>> Libraries mailing list > >>>> Libraries@haskell.org mailto:Libraries@haskell.org > >>>> http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries > >>> _______________________________________________ > >>> Libraries mailing list > >>> Libraries@haskell.org mailto:Libraries@haskell.org > >>> http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries > >> > >> _______________________________________________ > >> Libraries mailing list > >> Libraries@haskell.org mailto:Libraries@haskell.org > >> http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

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

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

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

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

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

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

Philip Hazelden

2:05 p.m.

I don't love `extract`, myself. I can see the motivation - extracting something generally means removing it without destroying it. But I worry that that's not salient enough to make the meaning clear. I dunno, maybe it's just that Data.Map already has "update", "alter" and "adjust", and I have no idea which is which - I don't think extract would be as bad as those, but it feels like in the same direction. For the Maybe version, I'd suggest `deleteLookup`. Or at least something with both those words, but this combination seems to be what I'd expect given the existing `splitLookup`, `deleteFindMin` and `deleteFindMax`. "delete" seems to be the standard "remove something from the map" - the word "remove" isn't yet used, so I don't see any reason to introduce it. And "lookup" seems to be the standard name for "look something up using Maybe in case it's not there". (By contrast, "find" seems to be the standard name for "look something up and error if it's not there".) For the default version, the only existing function I can see that takes a default is `findWithDefault`. (And this is the only use of "find" in the name of a function that doesn't error.) `deleteFindWithDefault` is a handful, but it would still be my suggestion. On Sun, Dec 6, 2020 at 5:30 PM Alexey Kuleshevich wrote:

...

`extract` is the name that I would suggest. I also agree with David that `pop` is a bit too confusing in a non-stack/queue data structure. If all languages named it pop, then it would be good argument for the name, but we don't need to copy python. The only thing that pyhon has that I wish we had in Haskell is the popularity ;) +1 on the function itself from me, I've needed it multiple occasions.

‐‐‐‐‐‐‐ Original Message ‐‐‐‐‐‐‐ On Sunday, December 6, 2020 8:16 PM, Carter Schonwald < carter.schonwald@gmail.com> wrote:

LookupThenRemove seems like a more descriptive name. Though I guess I can see why pop has appeal.

On Sun, Dec 6, 2020 at 11:44 AM David Feuer wrote:

...
I suggest you add a version for Data.Sequence combining lookup with deleteAt. I wanted that for something fairly recently.

On Sun, Dec 6, 2020, 11:41 AM Martijn Bastiaan via Libraries < libraries@haskell.org> wrote:

...
Yeah, Python's `pop` made me call it `pop`. I had hoped to find other examples, but Java, Rust, and Ruby don't seem to offer `pop`-like functions for their (hash)maps.

On 12/6/20 5:29 PM, Tom Ellis wrote:

...
On Sun, Dec 06, 2020 at 11:25:33AM -0500, David Feuer wrote:

...
The name pop makes me think of a stack. Is this use of the word common? Python uses that name, which is why I'm familiar with it:

...
...
> d = {'a': 1, 'b': 2} > d.pop('b') 2 > d {'a': 1}

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

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

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

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

Martijn Bastiaan

3:25 p.m.

I've taken a look, and it seems like a non-trivial change. For now I've added a version that simply traverses two times for Seq, to have API parity with Map/IntMap. If people are happy to accept pop/popWithDefault (be it with different names) I'll put in the work to make it do a single traversal for Seq too. On 12/6/20 5:43 PM, David Feuer wrote:

...

I suggest you add a version for Data.Sequence combining lookup with deleteAt. I wanted that for something fairly recently.

On Sun, Dec 6, 2020, 11:41 AM Martijn Bastiaan via Libraries mailto:libraries@haskell.org> wrote:

Yeah, Python's `pop` made me call it `pop`. I had hoped to find other examples, but Java, Rust, and Ruby don't seem to offer `pop`-like functions for their (hash)maps.

On 12/6/20 5:29 PM, Tom Ellis wrote: > On Sun, Dec 06, 2020 at 11:25:33AM -0500, David Feuer wrote: >> The name pop makes me think of a stack. Is this use of the word common? > Python uses that name, which is why I'm familiar with it: > >>>> d = {'a': 1, 'b': 2} >>>> d.pop('b') > 2 >>>> d > {'a': 1} > _______________________________________________ > Libraries mailing list > Libraries@haskell.org mailto:Libraries@haskell.org > http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries _______________________________________________ Libraries mailing list Libraries@haskell.org mailto:Libraries@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

David Feuer

3:32 p.m.

I wrote deleteAt, so I could probably write this function somewhat more easily than anyone else, once it has a name. On Sun, Dec 6, 2020, 3:25 PM Martijn Bastiaan wrote:

...

I've taken a look, and it seems like a non-trivial change. For now I've added a version that simply traverses two times for Seq, to have API parity with Map/IntMap. If people are happy to accept pop/popWithDefault (be it with different names) I'll put in the work to make it do a single traversal for Seq too. On 12/6/20 5:43 PM, David Feuer wrote:

I suggest you add a version for Data.Sequence combining lookup with deleteAt. I wanted that for something fairly recently.

On Sun, Dec 6, 2020, 11:41 AM Martijn Bastiaan via Libraries < libraries@haskell.org> wrote:

...
Yeah, Python's `pop` made me call it `pop`. I had hoped to find other examples, but Java, Rust, and Ruby don't seem to offer `pop`-like functions for their (hash)maps.

On 12/6/20 5:29 PM, Tom Ellis wrote:

...
On Sun, Dec 06, 2020 at 11:25:33AM -0500, David Feuer wrote:

...
The name pop makes me think of a stack. Is this use of the word common? Python uses that name, which is why I'm familiar with it:

...
...
...
d = {'a': 1, 'b': 2} d.pop('b') 2 d {'a': 1}

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

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

Tom Ellis

11:25 a.m.

On Sun, Dec 06, 2020 at 05:19:23PM +0100, Martijn Bastiaan via Libraries wrote:

...

Proposal:

* Add `pop` and `popWithDefault` to `Data.Map` and `Data.IntMap`. * See https://github.com/haskell/containers/pull/757 for exact definition

Thanks. I wanted this recently! I contented myself with a lookup/delete pair but your efficient implementation would be better.

Simon Jakobi

2:41 p.m.

Regarding the type signature: pop :: Ord k => k -> Map k a -> (Maybe a, Map k a) I think it might be better to be consistent with similar functions like minView :: Map k a -> Maybe (a, Map k a) and uncons :: [a] -> Maybe (a, [a]) Therefore the type should be pop :: Ord k => k -> Map k a -> Maybe (a, Map k a) --- I like the "pop" name though – I think the analogy to stacks is pretty obvious. --- Like Andreas Abel I believe, that if there is a good, simple implementation, it might be a good first step to simply document the implementation as an example. If there's much demand for exporting the function or if a fast implementation is more complex, we can still enhance the API later on. Am So., 6. Dez. 2020 um 17:20 Uhr schrieb Martijn Bastiaan via Libraries :

...

Hi all,

Proposal:

* Add `pop` and `popWithDefault` to `Data.Map` and `Data.IntMap`. * See https://github.com/haskell/containers/pull/757 for exact definition

Why:

* They're useful functions I expected to be in `Data.Map` and `Data.IntMap`. (This might be influenced by the fact that they're defined on Python's `dict`.)

* Their implementations (~ `updateLookupWithKey (\_ _ -> Nothing)`) are harder to parse than a simple `pop`, which should help Haskell codebases become a bit cleaner :).

* Their implementations are a bit non-obvious. My first instinct was to write `(Map.lookup ..., Map.delete ...)`, which would have done two traversals. Having "properly" implemented functions in the lib would prevent people from writing their own suboptimal ones.

Details and implementation:

* https://github.com/haskell/containers/pull/757

Kind regards, Martijn Bastiaan _______________________________________________ Libraries mailing list Libraries@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

Oleg Grenrus

5:33 p.m.

so it's uninsert (re uncons). - Oleg On 6.12.2020 21.41, Simon Jakobi via Libraries wrote:

...

Regarding the type signature:

pop :: Ord k => k -> Map k a -> (Maybe a, Map k a)

I think it might be better to be consistent with similar functions like

minView :: Map k a -> Maybe (a, Map k a)

and

uncons :: [a] -> Maybe (a, [a])

Therefore the type should be

pop :: Ord k => k -> Map k a -> Maybe (a, Map k a)

---

I like the "pop" name though – I think the analogy to stacks is pretty obvious.

---

Like Andreas Abel I believe, that if there is a good, simple implementation, it might be a good first step to simply document the implementation as an example.

If there's much demand for exporting the function or if a fast implementation is more complex, we can still enhance the API later on.

Am So., 6. Dez. 2020 um 17:20 Uhr schrieb Martijn Bastiaan via Libraries :

...
Hi all,

Proposal:

* Add `pop` and `popWithDefault` to `Data.Map` and `Data.IntMap`. * See https://github.com/haskell/containers/pull/757 for exact definition

Why:

* They're useful functions I expected to be in `Data.Map` and `Data.IntMap`. (This might be influenced by the fact that they're defined on Python's `dict`.)

* Their implementations (~ `updateLookupWithKey (\_ _ -> Nothing)`) are harder to parse than a simple `pop`, which should help Haskell codebases become a bit cleaner :).

* Their implementations are a bit non-obvious. My first instinct was to write `(Map.lookup ..., Map.delete ...)`, which would have done two traversals. Having "properly" implemented functions in the lib would prevent people from writing their own suboptimal ones.

Details and implementation:

* https://github.com/haskell/containers/pull/757

Kind regards, Martijn Bastiaan _______________________________________________ Libraries mailing list Libraries@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

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

Philip Hazelden

5:58 p.m.

Hm. I note that with `minView` and `uncons`, moving the Maybe to the inside doesn't increase the space of return values. That is, any input that gives `Nothing` now would give `(Nothing, empty)` if Maybe was on the inside. That's not true of this function; if the key isn't found, that doesn't tell us what is in the map. Of course it tells us that the second part of the return value is the same as the input map, but that feels not super-close to "the second part of the return value is this one specific value". And, my sense is that having Maybe on the inside would be more often what people would want to use. Like... if you don't care what the map-without-this-element looks like, you'd just use lookup. So clearly the caller of this function is going to use it in some cases. Maybe-on-the-outside is fine if you'll use it "only if the element was already there", but seems likely awkward otherwise. So I'd argue for keeping the Maybe on the inside. On Sun, Dec 6, 2020 at 7:42 PM Simon Jakobi via Libraries < libraries@haskell.org> wrote:

...

Regarding the type signature:

pop :: Ord k => k -> Map k a -> (Maybe a, Map k a)

I think it might be better to be consistent with similar functions like

minView :: Map k a -> Maybe (a, Map k a)

and

uncons :: [a] -> Maybe (a, [a])

Therefore the type should be

pop :: Ord k => k -> Map k a -> Maybe (a, Map k a)

---

I like the "pop" name though – I think the analogy to stacks is pretty obvious.

---

Like Andreas Abel I believe, that if there is a good, simple implementation, it might be a good first step to simply document the implementation as an example.

If there's much demand for exporting the function or if a fast implementation is more complex, we can still enhance the API later on.

Am So., 6. Dez. 2020 um 17:20 Uhr schrieb Martijn Bastiaan via Libraries :

...
Hi all,

Proposal:

* Add `pop` and `popWithDefault` to `Data.Map` and `Data.IntMap`. * See https://github.com/haskell/containers/pull/757 for exact

definition

...
Why:

* They're useful functions I expected to be in `Data.Map` and `Data.IntMap`. (This might be influenced by the fact that they're defined on Python's `dict`.)

* Their implementations (~ `updateLookupWithKey (\_ _ -> Nothing)`) are harder to parse than a simple `pop`, which should help Haskell codebases become a bit cleaner :).

* Their implementations are a bit non-obvious. My first instinct was to write `(Map.lookup ..., Map.delete ...)`, which would have done two traversals. Having "properly" implemented functions in the lib would prevent people from writing their own suboptimal ones.

Details and implementation:

* https://github.com/haskell/containers/pull/757

Kind regards, Martijn Bastiaan _______________________________________________ Libraries mailing list Libraries@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

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

David Feuer

6:30 p.m.

It feels very awkward to me. On Sun, Dec 6, 2020, 5:59 PM Philip Hazelden wrote:

...

Hm. I note that with `minView` and `uncons`, moving the Maybe to the inside doesn't increase the space of return values. That is, any input that gives `Nothing` now would give `(Nothing, empty)` if Maybe was on the inside. That's not true of this function; if the key isn't found, that doesn't tell us what is in the map. Of course it tells us that the second part of the return value is the same as the input map, but that feels not super-close to "the second part of the return value is this one specific value".

And, my sense is that having Maybe on the inside would be more often what people would want to use. Like... if you don't care what the map-without-this-element looks like, you'd just use lookup. So clearly the caller of this function is going to use it in some cases. Maybe-on-the-outside is fine if you'll use it "only if the element was already there", but seems likely awkward otherwise.

So I'd argue for keeping the Maybe on the inside.

On Sun, Dec 6, 2020 at 7:42 PM Simon Jakobi via Libraries < libraries@haskell.org> wrote:

...
Regarding the type signature:

pop :: Ord k => k -> Map k a -> (Maybe a, Map k a)

I think it might be better to be consistent with similar functions like

minView :: Map k a -> Maybe (a, Map k a)

and

uncons :: [a] -> Maybe (a, [a])

Therefore the type should be

pop :: Ord k => k -> Map k a -> Maybe (a, Map k a)

---

I like the "pop" name though – I think the analogy to stacks is pretty obvious.

---

Like Andreas Abel I believe, that if there is a good, simple implementation, it might be a good first step to simply document the implementation as an example.

If there's much demand for exporting the function or if a fast implementation is more complex, we can still enhance the API later on.

Am So., 6. Dez. 2020 um 17:20 Uhr schrieb Martijn Bastiaan via Libraries :

...
Hi all,

Proposal:

* Add `pop` and `popWithDefault` to `Data.Map` and `Data.IntMap`. * See https://github.com/haskell/containers/pull/757 for exact

definition

...
Why:

* They're useful functions I expected to be in `Data.Map` and `Data.IntMap`. (This might be influenced by the fact that they're defined on Python's `dict`.)

* Their implementations (~ `updateLookupWithKey (\_ _ -> Nothing)`) are harder to parse than a simple `pop`, which should help Haskell codebases become a bit cleaner :).

* Their implementations are a bit non-obvious. My first instinct was to write `(Map.lookup ..., Map.delete ...)`, which would have done two traversals. Having "properly" implemented functions in the lib would prevent people from writing their own suboptimal ones.

Details and implementation:

* https://github.com/haskell/containers/pull/757

Kind regards, Martijn Bastiaan _______________________________________________ Libraries mailing list Libraries@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

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

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

Keith

7:24 p.m.

Think of it as 'pop' again. Your state is the Map. You return Maybe the deleted value and a new state of the Map with the value (maybe) deleted. It makes no sense for your new state to be an empty Map (Nothing) when the key wasn't in the map. — Sent from my phone with K-9 Mail. On December 6, 2020 11:30:15 PM UTC, David Feuer wrote:

...

It feels very awkward to me.

On Sun, Dec 6, 2020, 5:59 PM Philip Hazelden wrote:

...
Hm. I note that with `minView` and `uncons`, moving the Maybe to the inside doesn't increase the space of return values. That is, any input that gives `Nothing` now would give `(Nothing, empty)` if Maybe was on the inside. That's not true of this function; if the key isn't found, that doesn't tell us what is in the map. Of course it tells us that the second part of the return value is the same as the input map, but that feels not super-close to "the second part of the return value is this one specific value".

And, my sense is that having Maybe on the inside would be more often what people would want to use. Like... if you don't care what the map-without-this-element looks like, you'd just use lookup. So clearly the caller of this function is going to use it in some cases. Maybe-on-the-outside is fine if you'll use it "only if the element was already there", but seems likely awkward otherwise.

So I'd argue for keeping the Maybe on the inside.

On Sun, Dec 6, 2020 at 7:42 PM Simon Jakobi via Libraries < libraries@haskell.org> wrote:

...
Regarding the type signature:

pop :: Ord k => k -> Map k a -> (Maybe a, Map k a)

I think it might be better to be consistent with similar functions like

minView :: Map k a -> Maybe (a, Map k a)

and

uncons :: [a] -> Maybe (a, [a])

Therefore the type should be

pop :: Ord k => k -> Map k a -> Maybe (a, Map k a)

---

I like the "pop" name though – I think the analogy to stacks is pretty obvious.

---

Like Andreas Abel I believe, that if there is a good, simple implementation, it might be a good first step to simply document the implementation as an example.

If there's much demand for exporting the function or if a fast implementation is more complex, we can still enhance the API later on.

Am So., 6. Dez. 2020 um 17:20 Uhr schrieb Martijn Bastiaan via Libraries :

...
Hi all,

Proposal:

* Add `pop` and `popWithDefault` to `Data.Map` and `Data.IntMap`. * See https://github.com/haskell/containers/pull/757 for exact

definition

...
Why:

* They're useful functions I expected to be in `Data.Map` and `Data.IntMap`. (This might be influenced by the fact that they're defined on Python's `dict`.)

* Their implementations (~ `updateLookupWithKey (\_ _ -> Nothing)`) are harder to parse than a simple `pop`, which should help Haskell codebases become a bit cleaner :).

* Their implementations are a bit non-obvious. My first instinct was to write `(Map.lookup ..., Map.delete ...)`, which would have done two traversals. Having "properly" implemented functions in the lib would prevent people from writing their own suboptimal ones.

Details and implementation:

* https://github.com/haskell/containers/pull/757

Kind regards, Martijn Bastiaan _______________________________________________ Libraries mailing list Libraries@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

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

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

David Feuer

9:06 p.m.

That depends on whether you want State (Map k v) (Maybe v) or StateT (Map k v) Maybe v Both ideas are useful, but for a data structure library I believe the latter is more often what you want, and what more users will expect. The approach you suggest is redundant, and makes the type less informative. You have to read the documentation to know what map gets returned if the key isn't present. On Sun, Dec 6, 2020, 7:25 PM Keith wrote:

...

Think of it as 'pop' again. Your state is the Map. You return Maybe the deleted value and a new state of the Map with the value (maybe) deleted. It makes no sense for your new state to be an empty Map (Nothing) when the key wasn't in the map. — Sent from my phone with K-9 Mail.

On December 6, 2020 11:30:15 PM UTC, David Feuer wrote:

...
It feels very awkward to me.

On Sun, Dec 6, 2020, 5:59 PM Philip Hazelden wrote:

...
Hm. I note that with `minView` and `uncons`, moving the Maybe to the inside doesn't increase the space of return values. That is, any input that gives `Nothing` now would give `(Nothing, empty)` if Maybe was on the inside. That's not true of this function; if the key isn't found, that doesn't tell us what is in the map. Of course it tells us that the second part of the return value is the same as the input map, but that feels not super-close to "the second part of the return value is this one specific value".

And, my sense is that having Maybe on the inside would be more often what people would want to use. Like... if you don't care what the map-without-this-element looks like, you'd just use lookup. So clearly the caller of this function is going to use it in some cases. Maybe-on-the-outside is fine if you'll use it "only if the element was already there", but seems likely awkward otherwise.

So I'd argue for keeping the Maybe on the inside.

On Sun, Dec 6, 2020 at 7:42 PM Simon Jakobi via Libraries < libraries@haskell.org> wrote:

...
Regarding the type signature:

pop :: Ord k => k -> Map k a -> (Maybe a, Map k a)

I think it might be better to be consistent with similar functions like

minView :: Map k a -> Maybe (a, Map k a)

and

uncons :: [a] -> Maybe (a, [a])

Therefore the type should be

pop :: Ord k => k -> Map k a -> Maybe (a, Map k a)

---

I like the "pop" name though – I think the analogy to stacks is pretty obvious.

---

Like Andreas Abel I believe, that if there is a good, simple implementation, it might be a good first step to simply document the implementation as an example.

If there's much demand for exporting the function or if a fast implementation is more complex, we can still enhance the API later on.

Am So., 6. Dez. 2020 um 17:20 Uhr schrieb Martijn Bastiaan via Libraries :

...
Hi all,

Proposal:

* Add `pop` and `popWithDefault` to `Data.Map` and `Data.IntMap`. * See https://github.com/haskell/containers/pull/757 for exact

definition

...
Why:

* They're useful functions I expected to be in `Data.Map` and `Data.IntMap`. (This might be influenced by the fact that they're defined on Python's `dict`.)

* Their implementations (~ `updateLookupWithKey (\_ _ -> Nothing)`) are harder to parse than a simple `pop`, which should help

Haskell

...
codebases become a bit cleaner :).

* Their implementations are a bit non-obvious. My first instinct

was

...
to write `(Map.lookup ..., Map.delete ...)`, which would have

done

...
two traversals. Having "properly" implemented functions in the

lib

...
would prevent people from writing their own suboptimal ones.

Details and implementation:

* https://github.com/haskell/containers/pull/757

Kind regards, Martijn Bastiaan _______________________________________________ Libraries mailing list Libraries@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

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

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

_______________________________________________

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

Simon Jakobi

7 Dec 7 Dec

5:18 p.m.

It would be enlightening to see some examples of how pop is intended to be used. After reading Philip's response I suspect that users might rather want

...

State (Map k v) (Maybe v)

and that the Maybe should therefore be inside the tuple. Am Mo., 7. Dez. 2020 um 03:07 Uhr schrieb David Feuer :

...

That depends on whether you want

State (Map k v) (Maybe v)

or

StateT (Map k v) Maybe v

Both ideas are useful, but for a data structure library I believe the latter is more often what you want, and what more users will expect. The approach you suggest is redundant, and makes the type less informative. You have to read the documentation to know what map gets returned if the key isn't present.

On Sun, Dec 6, 2020, 7:25 PM Keith wrote:

...
Think of it as 'pop' again. Your state is the Map. You return Maybe the deleted value and a new state of the Map with the value (maybe) deleted. It makes no sense for your new state to be an empty Map (Nothing) when the key wasn't in the map. — Sent from my phone with K-9 Mail.

On December 6, 2020 11:30:15 PM UTC, David Feuer wrote:

...
It feels very awkward to me.

On Sun, Dec 6, 2020, 5:59 PM Philip Hazelden wrote:

...
Hm. I note that with `minView` and `uncons`, moving the Maybe to the inside doesn't increase the space of return values. That is, any input that gives `Nothing` now would give `(Nothing, empty)` if Maybe was on the inside. That's not true of this function; if the key isn't found, that doesn't tell us what is in the map. Of course it tells us that the second part of the return value is the same as the input map, but that feels not super-close to "the second part of the return value is this one specific value".

And, my sense is that having Maybe on the inside would be more often what people would want to use. Like... if you don't care what the map-without-this-element looks like, you'd just use lookup. So clearly the caller of this function is going to use it in some cases. Maybe-on-the-outside is fine if you'll use it "only if the element was already there", but seems likely awkward otherwise.

So I'd argue for keeping the Maybe on the inside.

On Sun, Dec 6, 2020 at 7:42 PM Simon Jakobi via Libraries wrote:

...
Regarding the type signature:

pop :: Ord k => k -> Map k a -> (Maybe a, Map k a)

I think it might be better to be consistent with similar functions like

minView :: Map k a -> Maybe (a, Map k a)

and

uncons :: [a] -> Maybe (a, [a])

Therefore the type should be

pop :: Ord k => k -> Map k a -> Maybe (a, Map k a)

---

I like the "pop" name though – I think the analogy to stacks is pretty obvious.

---

Like Andreas Abel I believe, that if there is a good, simple implementation, it might be a good first step to simply document the implementation as an example.

If there's much demand for exporting the function or if a fast implementation is more complex, we can still enhance the API later on.

Am So., 6. Dez. 2020 um 17:20 Uhr schrieb Martijn Bastiaan via Libraries :

...
Hi all,

Proposal:

* Add `pop` and `popWithDefault` to `Data.Map` and `Data.IntMap`. * See https://github.com/haskell/containers/pull/757 for exact definition

Why:

* They're useful functions I expected to be in `Data.Map` and `Data.IntMap`. (This might be influenced by the fact that they're defined on Python's `dict`.)

* Their implementations (~ `updateLookupWithKey (\_ _ -> Nothing)`) are harder to parse than a simple `pop`, which should help Haskell codebases become a bit cleaner :).

* Their implementations are a bit non-obvious. My first instinct was to write `(Map.lookup ..., Map.delete ...)`, which would have done two traversals. Having "properly" implemented functions in the lib would prevent people from writing their own suboptimal ones.

Details and implementation:

* https://github.com/haskell/containers/pull/757

Kind regards, Martijn Bastiaan _______________________________________________ Libraries mailing list Libraries@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

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

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

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

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

Keith

6 Dec 6 Dec

7:30 p.m.

Also, I'm not sure if this is a real concern, but holding a reference to the original Map seems more likely to leak memory that always using the 'new' map returned by 'popWithKey'. — Sent from my phone with K-9 Mail. On December 6, 2020 11:30:15 PM UTC, David Feuer wrote:

...

It feels very awkward to me.

On Sun, Dec 6, 2020, 5:59 PM Philip Hazelden wrote:

...
Hm. I note that with `minView` and `uncons`, moving the Maybe to the inside doesn't increase the space of return values. That is, any input that gives `Nothing` now would give `(Nothing, empty)` if Maybe was on the inside. That's not true of this function; if the key isn't found, that doesn't tell us what is in the map. Of course it tells us that the second part of the return value is the same as the input map, but that feels not super-close to "the second part of the return value is this one specific value".

And, my sense is that having Maybe on the inside would be more often what people would want to use. Like... if you don't care what the map-without-this-element looks like, you'd just use lookup. So clearly the caller of this function is going to use it in some cases. Maybe-on-the-outside is fine if you'll use it "only if the element was already there", but seems likely awkward otherwise.

So I'd argue for keeping the Maybe on the inside.

On Sun, Dec 6, 2020 at 7:42 PM Simon Jakobi via Libraries < libraries@haskell.org> wrote:

...
Regarding the type signature:

pop :: Ord k => k -> Map k a -> (Maybe a, Map k a)

I think it might be better to be consistent with similar functions like

minView :: Map k a -> Maybe (a, Map k a)

and

uncons :: [a] -> Maybe (a, [a])

Therefore the type should be

pop :: Ord k => k -> Map k a -> Maybe (a, Map k a)

---

I like the "pop" name though – I think the analogy to stacks is pretty obvious.

---

Like Andreas Abel I believe, that if there is a good, simple implementation, it might be a good first step to simply document the implementation as an example.

If there's much demand for exporting the function or if a fast implementation is more complex, we can still enhance the API later on.

Am So., 6. Dez. 2020 um 17:20 Uhr schrieb Martijn Bastiaan via Libraries :

...
Hi all,

Proposal:

* Add `pop` and `popWithDefault` to `Data.Map` and `Data.IntMap`. * See https://github.com/haskell/containers/pull/757 for exact

definition

...
Why:

* They're useful functions I expected to be in `Data.Map` and `Data.IntMap`. (This might be influenced by the fact that they're defined on Python's `dict`.)

* Their implementations (~ `updateLookupWithKey (\_ _ -> Nothing)`) are harder to parse than a simple `pop`, which should help Haskell codebases become a bit cleaner :).

* Their implementations are a bit non-obvious. My first instinct was to write `(Map.lookup ..., Map.delete ...)`, which would have done two traversals. Having "properly" implemented functions in the lib would prevent people from writing their own suboptimal ones.

Details and implementation:

* https://github.com/haskell/containers/pull/757

Kind regards, Martijn Bastiaan _______________________________________________ Libraries mailing list Libraries@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

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

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

David Feuer

9:02 p.m.

That's not a concern. On Sun, Dec 6, 2020, 7:31 PM Keith wrote:

...

Also, I'm not sure if this is a real concern, but holding a reference to the original Map seems more likely to leak memory that always using the 'new' map returned by 'popWithKey'. — Sent from my phone with K-9 Mail.

On December 6, 2020 11:30:15 PM UTC, David Feuer wrote:

...
It feels very awkward to me.

On Sun, Dec 6, 2020, 5:59 PM Philip Hazelden wrote:

...
Hm. I note that with `minView` and `uncons`, moving the Maybe to the inside doesn't increase the space of return values. That is, any input that gives `Nothing` now would give `(Nothing, empty)` if Maybe was on the inside. That's not true of this function; if the key isn't found, that doesn't tell us what is in the map. Of course it tells us that the second part of the return value is the same as the input map, but that feels not super-close to "the second part of the return value is this one specific value".

And, my sense is that having Maybe on the inside would be more often what people would want to use. Like... if you don't care what the map-without-this-element looks like, you'd just use lookup. So clearly the caller of this function is going to use it in some cases. Maybe-on-the-outside is fine if you'll use it "only if the element was already there", but seems likely awkward otherwise.

So I'd argue for keeping the Maybe on the inside.

On Sun, Dec 6, 2020 at 7:42 PM Simon Jakobi via Libraries < libraries@haskell.org> wrote:

...
Regarding the type signature:

pop :: Ord k => k -> Map k a -> (Maybe a, Map k a)

I think it might be better to be consistent with similar functions like

minView :: Map k a -> Maybe (a, Map k a)

and

uncons :: [a] -> Maybe (a, [a])

Therefore the type should be

pop :: Ord k => k -> Map k a -> Maybe (a, Map k a)

---

I like the "pop" name though – I think the analogy to stacks is pretty obvious.

---

Like Andreas Abel I believe, that if there is a good, simple implementation, it might be a good first step to simply document the implementation as an example.

If there's much demand for exporting the function or if a fast implementation is more complex, we can still enhance the API later on.

Am So., 6. Dez. 2020 um 17:20 Uhr schrieb Martijn Bastiaan via Libraries :

...
Hi all,

Proposal:

* Add `pop` and `popWithDefault` to `Data.Map` and `Data.IntMap`. * See https://github.com/haskell/containers/pull/757 for exact

definition

...
Why:

* They're useful functions I expected to be in `Data.Map` and `Data.IntMap`. (This might be influenced by the fact that they're defined on Python's `dict`.)

* Their implementations (~ `updateLookupWithKey (\_ _ -> Nothing)`) are harder to parse than a simple `pop`, which should help

Haskell

...
codebases become a bit cleaner :).

* Their implementations are a bit non-obvious. My first instinct

was

...
to write `(Map.lookup ..., Map.delete ...)`, which would have

done

...
two traversals. Having "properly" implemented functions in the

lib

...
would prevent people from writing their own suboptimal ones.

Details and implementation:

* https://github.com/haskell/containers/pull/757

Kind regards, Martijn Bastiaan _______________________________________________ Libraries mailing list Libraries@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

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

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

_______________________________________________

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

David Feuer

4:25 p.m.

I want the Maybe on the outside if we do this at all. On Sun, Dec 6, 2020, 11:20 AM Martijn Bastiaan via Libraries < libraries@haskell.org> wrote:

...

Hi all,

Proposal:

* Add `pop` and `popWithDefault` to `Data.Map` and `Data.IntMap`. * See https://github.com/haskell/containers/pull/757 for exact definition

Why:

* They're useful functions I expected to be in `Data.Map` and `Data.IntMap`. (This might be influenced by the fact that they're defined on Python's `dict`.)

* Their implementations (~ `updateLookupWithKey (\_ _ -> Nothing)`) are harder to parse than a simple `pop`, which should help Haskell codebases become a bit cleaner :).

* Their implementations are a bit non-obvious. My first instinct was to write `(Map.lookup ..., Map.delete ...)`, which would have done two traversals. Having "properly" implemented functions in the lib would prevent people from writing their own suboptimal ones.

Details and implementation:

* https://github.com/haskell/containers/pull/757

Kind regards, Martijn Bastiaan _______________________________________________ Libraries mailing list Libraries@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

1626

Age (days ago)

1627

Last active (days ago)

List overview

Download

28 comments

11 participants

participants (11)

Alexey Kuleshevich
Andreas Abel
Bob Ippolito
Carter Schonwald
David Feuer
Keith
Martijn Bastiaan
Oleg Grenrus
Philip Hazelden
Simon Jakobi
Tom Ellis