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