Proposal for containers: Add 'lookup' function to Data.Set
Andreas Abel
andreas.abel at ifi.lmu.de
Wed Jun 29 12:36:23 UTC 2016
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/
More information about the Libraries
mailing list