Proposal for containers: Add 'lookup' function to Data.Set
David Feuer
david.feuer at gmail.com
Wed Jun 29 17:39:47 UTC 2016
+1 for lookupEntry. I think that's very intuitive.
On Wed, Jun 29, 2016 at 8:36 AM, Andreas Abel <andreas.abel at ifi.lmu.de> wrote:
> On 29.06.2016 11:17, Edward Kmett wrote:
>>
>> As another color for the bikeshed: lookupWithKey would match the
>> existing vocabulary of insertWithKey, etc.
>
>
> Even though they have a different ethymology, coming from insertWith (with a
> function) etc.!?
>
> Another bikeshed
>
> lookupEntry :: Ord a => a -> Set a -> Maybe a
> lookupEntry :: Ord a => k -> Map k v -> Maybe (k, v)
>
> since it retrieves the whole set/map entry and not just the value.
>
>> 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 at joachim-breitner.de <mailto:mail at 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
>> > <dct25-561bs at mythic-beasts.com
>> <mailto:dct25-561bs at mythic-beasts.com>> 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 at haskell.org <mailto:Libraries at haskell.org>
>> > > http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
>> > >
>> > > _______________________________________________
>> > > Libraries mailing list
>> > > Libraries at haskell.org <mailto:Libraries at haskell.org>
>> > > http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
>> > >
>> > _______________________________________________
>> > Libraries mailing list
>> > Libraries at haskell.org <mailto:Libraries at haskell.org>
>> > http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
>> --
>>
>> Joachim “nomeata” Breitner
>> mail at joachim-breitner.de <mailto:mail at joachim-breitner.de> •
>> https://www.joachim-breitner.de/
>> XMPP: nomeata at joachim-breitner.de
>> <mailto:nomeata at joachim-breitner.de> • OpenPGP-Key: 0xF0FBF51F
>> Debian Developer: nomeata at debian.org <mailto:nomeata at debian.org>
>>
>> _______________________________________________
>> Libraries mailing list
>> Libraries at haskell.org <mailto: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
>>
>
>
> --
> Andreas Abel <>< Du bist der geliebte Mensch.
>
> Department of Computer Science and Engineering
> Chalmers and Gothenburg University, Sweden
>
> andreas.abel at gu.se
> http://www2.tcs.ifi.lmu.de/~abel/
> _______________________________________________
> Libraries mailing list
> Libraries at haskell.org
> http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
More information about the Libraries
mailing list