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

David Feuer david.feuer at gmail.com
Mon Dec 7 02:06:57 UTC 2020


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 <keith.wygant at gmail.com> 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 <david.feuer at gmail.com>
> wrote:
>>
>> It feels very awkward to me.
>>
>> On Sun, Dec 6, 2020, 5:59 PM Philip Hazelden <philip.hazelden at gmail.com>
>> 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 at 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 <libraries at haskell.org>:
>>>> >
>>>> > 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 at haskell.org
>>>> > http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
>>>> _______________________________________________
>>>> Libraries mailing list
>>>> Libraries at haskell.org
>>>> http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
>>>>
>>> _______________________________________________
>>> Libraries mailing list
>>> Libraries at haskell.org
>>> http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
>>>
>> _______________________________________________
> Libraries mailing list
> Libraries at haskell.org
> http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.haskell.org/pipermail/libraries/attachments/20201206/503cef4a/attachment.html>


More information about the Libraries mailing list