Re: Proposal for containers: Add 'lookup' function to Data.Set

I don't think all the other xxxWith functions currently make this guarantee! I think they should, though. On Jun 29, 2016 5:17 AM, "Edward Kmett" wrote:

As another color for the bikeshed: lookupWithKey would match the existing vocabulary of insertWithKey, etc.

We could further document the rest of them to include the assertion that the copy of the key they give back to the combinator is the one found in the Map/Set and not the one given. Then this is just the continuation of an existing pattern in the library.

-Edward

On Wed, Jun 29, 2016 at 4:18 AM, Joachim Breitner < mail@joachim-breitner.de> wrote:

...

Hi,

good point. How about

lookupKey :: Ord a => a -> Set a -> Maybe a

and

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

It might be a bit strange to talk about key in the context of Sets, but less so to someone who knows about sharing and pointers etc, and the naming convention works well for maps. There, looking up the key is likely the main purpose of the function; that we return the value along with it is a nice bonus.

Greetings, Joachim

Am Mittwoch, den 29.06.2016, 02:12 -0400 schrieb David Feuer:

...

Would we also want something similar for `Data.Map`, looking up a key and returning the copy of the key found in the map along with the associated value?

lookupWithInternedKeyOrWhatever :: Ord k => k -> Map k v -> (k, v)

If so, it might pay to think about a naming scheme that will make sense for both Data.Map and Data.Set.

On Tue, Jun 28, 2016 at 12:38 PM, David Turner wrote:

...

+1

When I previously searched for (and failed to find) this function in order to implement an intern table, I remember trying 'lookup', 'lookupEQ' and 'find' in approximately that order, so that's my order if preference for its name.

'lookupInterned' or similar could work for me too if you want to scare off beginners although I don't see a strong need myself. Certainly a mention of interning in the haddocks would help.

WHAT

It is proposed to add a ‘lookup' function on 'Set' in the "containers" package. Feedback during the next two weeks is welcome.

The function

...

lookup :: Ord a => a -> Set a -> Maybe a

is almost indentical to the 'member' function but, in addition, returns the value stored in the set.

WHY

The point of this proposal is to facilitate program-wide data sharing. The 'lookup' function gives access to a pointer to an object already stored in a Set and equal to a given argument. The 'lookup' function is a natural extension to the current 'lookupLT', 'lookupGT', 'lookupLE' and 'lookupGE' functions, with obvious semantics.

Example use case: In a parser, the memory footprint can be reduced by collapsing all equal strings to a single instance of each string. To achieve this, one needs a way to get a previously seen string (internally, a pointer) equal to a newly parsed string. Amazingly, this is very difficult with the current "containers" library interface. One current option is to use a Map instead, e.g., 'Map String String' which stores twice as many pointers as necessary.

HOW

The git pull request at https://github.com/haskell/containers/pull/291 contains the straight-forward implementation of the 'lookup’ function on 'Set', with test cases, as a patch against the current containers master branch.

Salutations, Nicolas.

_______________________________________________ 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 --

Joachim “nomeata” Breitner mail@joachim-breitner.de • https://www.joachim-breitner.de/ XMPP: nomeata@joachim-breitner.de • OpenPGP-Key: 0xF0FBF51F Debian Developer: nomeata@debian.org

_______________________________________________ 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