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

newer
Proposal: add liftA4 and liftA5 to...

older
Proposal and discussion: Deprecate...

Nicolas Godbout

27 Jun 2016 27 Jun '16

5:45 p.m.

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.

Show replies by date

David Feuer

27 Jun 27 Jun

5:47 p.m.

+1 on the function. -1/2 on the name. On Jun 27, 2016 5:45 PM, "Nicolas Godbout" wrote:

...

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

Nicolas Godbout

5:52 p.m.

David Feuer wrote:

...

+1 on the function. -1/2 on the name.

To be honest, I briefly considered the name `lookupEQ`. The name would fit nicely with `lookupGT` and company. Nicolas.

David Feuer

5:56 p.m.

As much as I dislike the names lookupGT, et al, I think that's probably your best bet now that they exist. On Jun 27, 2016 5:52 PM, "Nicolas Godbout" wrote:

...

David Feuer wrote:

+1 on the function. -1/2 on the name.

To be honest, I briefly considered the name `lookupEQ`. The name would fit nicely with `lookupGT` and company.

Nicolas.

David Feuer

6:17 p.m.

Another option might be "find". On Jun 27, 2016 5:56 PM, "David Feuer" wrote:

...

As much as I dislike the names lookupGT, et al, I think that's probably your best bet now that they exist. On Jun 27, 2016 5:52 PM, "Nicolas Godbout" wrote:

...
David Feuer wrote:

+1 on the function. -1/2 on the name.

To be honest, I briefly considered the name `lookupEQ`. The name would fit nicely with `lookupGT` and company.

Nicolas.

Malcolm Wallace

28 Jun 28 Jun

1:14 a.m.

Or "lookupSharedPointer", if that is the important part of the operational semantics. Regards, Malcolm (iPhone) On 27 Jun 2016, at 23:17, David Feuer wrote: Another option might be "find".

...

On Jun 27, 2016 5:56 PM, "David Feuer" wrote: As much as I dislike the names lookupGT, et al, I think that's probably your best bet now that they exist.

...
On Jun 27, 2016 5:52 PM, "Nicolas Godbout" wrote: David Feuer wrote:

...
+1 on the function. -1/2 on the name.

To be honest, I briefly considered the name `lookupEQ`. The name would fit nicely with `lookupGT` and company.

Nicolas.

_______________________________________________ Libraries mailing list Libraries@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

Joachim Breitner

4:46 a.m.

Hi, given that for naive uses and users, the existence of lookup is more confusing than helpful, I’m in favor of a name that indicates “this is advanced foo”, a suitable documentation, and moving it to the very end of the module documentation, as it is not a function you’d expect for a set implementation. The name "Pointer", though, might be a bit too low-level. Maybe "lookupWithSharing"? Greetings, Joachim Am Dienstag, den 28.06.2016, 06:14 +0100 schrieb Malcolm Wallace:

...

Or "lookupSharedPointer", if that is the important part of the operational semantics.

Regards, Malcolm (iPhone)

On 27 Jun 2016, at 23:17, David Feuer wrote:

Another option might be "find". On Jun 27, 2016 5:56 PM, "David Feuer" wrote:

...
As much as I dislike the names lookupGT, et al, I think that's probably your best bet now that they exist. On Jun 27, 2016 5:52 PM, "Nicolas Godbout" wrote:

...
David Feuer wrote:

...
+1 on the function. -1/2 on the name.

To be honest, I briefly considered the name `lookupEQ`. The name would fit nicely with `lookupGT` and company.

Nicolas.

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

Chris Wong

5:22 a.m.

Python uses "intern", so perhaps that can serve as the name. (See https://docs.python.org/2/library/functions.html#intern) On Tue, Jun 28, 2016 at 9:47 AM, David Feuer wrote:

...

+1 on the function. -1/2 on the name.

On Jun 27, 2016 5:45 PM, "Nicolas Godbout" wrote:

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

-- Chris Wong (https://lambda.xyz) "I had not the vaguest idea what this meant and when I could not remember the words, my tutor threw the book at my head, which did not stimulate my intellect in any way." -- Bertrand Russell

Oliver Charles

5:44 a.m.

I don't really see the problem with lookup. To me, that function always takes a container, an index into that container, and returns the value under than index or fails. It just so happens that sets are indexed by the very values the contain, but I don't find the signature confusing. Sure, I might not use it very often, but it's still clear enough to me what it's doing. Ollie On Tue, 28 Jun 2016, 10:23 a.m. Chris Wong, wrote:

...

Python uses "intern", so perhaps that can serve as the name.

(See https://docs.python.org/2/library/functions.html#intern)

On Tue, Jun 28, 2016 at 9:47 AM, David Feuer wrote:

...
+1 on the function. -1/2 on the name.

On Jun 27, 2016 5:45 PM, "Nicolas Godbout" wrote:

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

-- Chris Wong (https://lambda.xyz)

"I had not the vaguest idea what this meant and when I could not remember the words, my tutor threw the book at my head, which did not stimulate my intellect in any way." -- Bertrand Russell _______________________________________________ Libraries mailing list Libraries@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

Andreas Abel

5:53 a.m.

+1 for "lookup". On 28.06.2016 11:44, Oliver Charles wrote:

...

I don't really see the problem with lookup. To me, that function always takes a container, an index into that container, and returns the value under than index or fails. It just so happens that sets are indexed by the very values the contain, but I don't find the signature confusing. Sure, I might not use it very often, but it's still clear enough to me what it's doing.

Ollie

On Tue, 28 Jun 2016, 10:23 a.m. Chris Wong, mailto:lambda.fairy@gmail.com> wrote:

Python uses "intern", so perhaps that can serve as the name.

(See https://docs.python.org/2/library/functions.html#intern)

On Tue, Jun 28, 2016 at 9:47 AM, David Feuer mailto:david.feuer@gmail.com> wrote: > +1 on the function. -1/2 on the name. > > On Jun 27, 2016 5:45 PM, "Nicolas Godbout" mailto:nicolas.godbout@gmail.com> > wrote: >> >> >> 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 mailto:Libraries@haskell.org >> http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries > > > _______________________________________________ > Libraries mailing list > Libraries@haskell.org mailto:Libraries@haskell.org > http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries >

-- Chris Wong (https://lambda.xyz)

"I had not the vaguest idea what this meant and when I could not remember the words, my tutor threw the book at my head, which did not stimulate my intellect in any way." -- Bertrand Russell _______________________________________________ Libraries mailing list Libraries@haskell.org mailto: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

-- Andreas Abel <>< Du bist der geliebte Mensch. Department of Computer Science and Engineering Chalmers and Gothenburg University, Sweden andreas.abel@gu.se http://www2.tcs.ifi.lmu.de/~abel/

Michael Snoyman

5:58 a.m.

Likewise, I'm not in favor of name proliferation. To avoid confusion, I think it's sufficient to give a clear comments in the Haddocks explaining why one would wish to use this function. On Tue, Jun 28, 2016 at 12:53 PM, Andreas Abel wrote:

...

+1 for "lookup".

On 28.06.2016 11:44, Oliver Charles wrote:

...
I don't really see the problem with lookup. To me, that function always takes a container, an index into that container, and returns the value under than index or fails. It just so happens that sets are indexed by the very values the contain, but I don't find the signature confusing. Sure, I might not use it very often, but it's still clear enough to me what it's doing.

Ollie

On Tue, 28 Jun 2016, 10:23 a.m. Chris Wong, mailto:lambda.fairy@gmail.com> wrote:

Python uses "intern", so perhaps that can serve as the name.

(See https://docs.python.org/2/library/functions.html#intern)

On Tue, Jun 28, 2016 at 9:47 AM, David Feuer mailto:david.feuer@gmail.com> wrote: > +1 on the function. -1/2 on the name. > > On Jun 27, 2016 5:45 PM, "Nicolas Godbout" mailto:nicolas.godbout@gmail.com>

> wrote: >> >> >> 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 mailto:Libraries@haskell.org >> http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries > > > _______________________________________________ > Libraries mailing list > Libraries@haskell.org mailto:Libraries@haskell.org > http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries >

-- Chris Wong (https://lambda.xyz)

"I had not the vaguest idea what this meant and when I could not remember the words, my tutor threw the book at my head, which did not stimulate my intellect in any way." -- Bertrand Russell _______________________________________________ Libraries mailing list Libraries@haskell.org mailto: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

-- Andreas Abel <>< Du bist der geliebte Mensch.

Department of Computer Science and Engineering Chalmers and Gothenburg University, Sweden

andreas.abel@gu.se http://www2.tcs.ifi.lmu.de/~abel/

_______________________________________________ Libraries mailing list Libraries@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

Bardur Arantsson

6:20 a.m.

On 06/28/2016 11:44 AM, Oliver Charles wrote:

...

I don't really see the problem with lookup. To me, that function always takes a container, an index into that container, and returns the value under than index or fails. It just so happens that sets are indexed by the very values the contain, but I don't find the signature confusing. Sure, I might not use it very often, but it's still clear enough to me what it's doing.

David Thomas

29 Jun 29 Jun

4:57 p.m.

Well, "intern" includes a "and if it is not there, add it". Calling this "intern" without that behavior would be highly misleading. That said, maybe we just want an "intern" function? It would save us a dip into the set, for new strings and leave (marginally) less room to make a mistake. Are there many cases where we want `lookup` where we don't actually want `intern`? On Tue, Jun 28, 2016 at 2:22 AM, Chris Wong wrote:

...

Python uses "intern", so perhaps that can serve as the name.

(See https://docs.python.org/2/library/functions.html#intern)

On Tue, Jun 28, 2016 at 9:47 AM, David Feuer wrote:

...
+1 on the function. -1/2 on the name.

On Jun 27, 2016 5:45 PM, "Nicolas Godbout" wrote:

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

-- Chris Wong (https://lambda.xyz)

"I had not the vaguest idea what this meant and when I could not remember the words, my tutor threw the book at my head, which did not stimulate my intellect in any way." -- Bertrand Russell _______________________________________________ Libraries mailing list Libraries@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

David Feuer

5:02 p.m.

I suspect we may want both functions. On Wed, Jun 29, 2016 at 4:57 PM, David Thomas wrote:

...

Well, "intern" includes a "and if it is not there, add it". Calling this "intern" without that behavior would be highly misleading. That said, maybe we just want an "intern" function? It would save us a dip into the set, for new strings and leave (marginally) less room to make a mistake. Are there many cases where we want `lookup` where we don't actually want `intern`?

On Tue, Jun 28, 2016 at 2:22 AM, Chris Wong wrote:

...
Python uses "intern", so perhaps that can serve as the name.

(See https://docs.python.org/2/library/functions.html#intern)

On Tue, Jun 28, 2016 at 9:47 AM, David Feuer wrote:

...
+1 on the function. -1/2 on the name.

On Jun 27, 2016 5:45 PM, "Nicolas Godbout" wrote:

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

-- Chris Wong (https://lambda.xyz)

"I had not the vaguest idea what this meant and when I could not remember the words, my tutor threw the book at my head, which did not stimulate my intellect in any way." -- Bertrand Russell _______________________________________________ Libraries mailing list Libraries@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

Alec

5:12 p.m.

...

Are there many cases where we want `lookup` where we don't actually want `intern`?

Anecdotally, the majority of the times I've wanted `intern` functionality, I've been implementing something full-text-search-like. This meant having a "load the lexicon" phase, where a set of blessed words get `intern`ed, and then a query phase where I want is `lookup` because my lexicon is doing double duty as a stoplist. I have no sense of whether this would be a common case. Also, +1 for `intern`, +1 for `lookup`. I'm fine with both names. On Wed, Jun 29, 2016 at 4:57 PM David Thomas wrote:

...

Well, "intern" includes a "and if it is not there, add it". Calling this "intern" without that behavior would be highly misleading. That said, maybe we just want an "intern" function? It would save us a dip into the set, for new strings and leave (marginally) less room to make a mistake. Are there many cases where we want `lookup` where we don't actually want `intern`?

...
Python uses "intern", so perhaps that can serve as the name.

(See https://docs.python.org/2/library/functions.html#intern)

On Tue, Jun 28, 2016 at 9:47 AM, David Feuer wrote:

...
+1 on the function. -1/2 on the name.

On Jun 27, 2016 5:45 PM, "Nicolas Godbout" wrote:

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

On Tue, Jun 28, 2016 at 2:22 AM, Chris Wong wrote: 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

-- Chris Wong (https://lambda.xyz)

"I had not the vaguest idea what this meant and when I could not remember the words, my tutor threw the book at my head, which did not stimulate my intellect in any way." -- Bertrand Russell _______________________________________________ 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

David Feuer

5:18 p.m.

Let me be firm (co-maintainer's prerogative): the function will not be named `lookup`. The current leader in my eyes is Andreas Abel's `lookupEntry`, but I could be convinced to use something else if others prefer On Jun 29, 2016 5:12 PM, "Alec" wrote:

...

...
Are there many cases where we want `lookup` where we don't actually want `intern`?

Anecdotally, the majority of the times I've wanted `intern` functionality, I've been implementing something full-text-search-like. This meant having a "load the lexicon" phase, where a set of blessed words get `intern`ed, and then a query phase where I want is `lookup` because my lexicon is doing double duty as a stoplist. I have no sense of whether this would be a common case.

Also, +1 for `intern`, +1 for `lookup`. I'm fine with both names.

On Wed, Jun 29, 2016 at 4:57 PM David Thomas wrote:

...
Well, "intern" includes a "and if it is not there, add it". Calling this "intern" without that behavior would be highly misleading. That said, maybe we just want an "intern" function? It would save us a dip into the set, for new strings and leave (marginally) less room to make a mistake. Are there many cases where we want `lookup` where we don't actually want `intern`?

...
Python uses "intern", so perhaps that can serve as the name.

(See https://docs.python.org/2/library/functions.html#intern)

On Tue, Jun 28, 2016 at 9:47 AM, David Feuer wrote:

...
+1 on the function. -1/2 on the name.

On Jun 27, 2016 5:45 PM, "Nicolas Godbout" wrote:

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

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

On Tue, Jun 28, 2016 at 2:22 AM, Chris Wong wrote: the 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

-- Chris Wong (https://lambda.xyz)

"I had not the vaguest idea what this meant and when I could not remember the words, my tutor threw the book at my head, which did not stimulate my intellect in any way." -- Bertrand Russell _______________________________________________ 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

Alec

5:48 p.m.

`lookupEntry` seems fine to me... \begin{bikeshedding} but it bugs me a little that (according to the API) Sets have "members" (`member`, `notMember`, and `splitMember`) and "elems" (`elems`, `elemAt`), but (at least as of yet) no "entries". (In my brief scan of the docs, it appears "element" is the preferred English for "thing that can be in a Set"). Andreas' suggestion applies the name to Map as well, so I buy that "entry" is actually a new notion distinct from "element" or "member"---but if a user isn't expected to have that notion in mind when seeking this functionality, it seems mildly disadvantageous to introduce a new word for "thing that can be in a Set" to the API. \end{bikeshedding} On Wed, Jun 29, 2016 at 5:18 PM David Feuer wrote:

...

Let me be firm (co-maintainer's prerogative): the function will not be named `lookup`. The current leader in my eyes is Andreas Abel's `lookupEntry`, but I could be convinced to use something else if others prefer On Jun 29, 2016 5:12 PM, "Alec" wrote:

...
...
Are there many cases where we want `lookup` where we don't actually want `intern`?

Anecdotally, the majority of the times I've wanted `intern` functionality, I've been implementing something full-text-search-like. This meant having a "load the lexicon" phase, where a set of blessed words get `intern`ed, and then a query phase where I want is `lookup` because my lexicon is doing double duty as a stoplist. I have no sense of whether this would be a common case.

Also, +1 for `intern`, +1 for `lookup`. I'm fine with both names.

On Wed, Jun 29, 2016 at 4:57 PM David Thomas wrote:

...
Well, "intern" includes a "and if it is not there, add it". Calling this "intern" without that behavior would be highly misleading. That said, maybe we just want an "intern" function? It would save us a dip into the set, for new strings and leave (marginally) less room to make a mistake. Are there many cases where we want `lookup` where we don't actually want `intern`?

...
Python uses "intern", so perhaps that can serve as the name.

(See https://docs.python.org/2/library/functions.html#intern)

On Tue, Jun 28, 2016 at 9:47 AM, David Feuer wrote:

...
+1 on the function. -1/2 on the name.

On Jun 27, 2016 5:45 PM, "Nicolas Godbout"
...
wrote:

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

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

On Tue, Jun 28, 2016 at 2:22 AM, Chris Wong wrote: the 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

-- Chris Wong (https://lambda.xyz)

"I had not the vaguest idea what this meant and when I could not remember the words, my tutor threw the book at my head, which did not stimulate my intellect in any way." -- Bertrand Russell _______________________________________________ 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

Bardur Arantsson

6:06 p.m.

On 06/29/2016 11:48 PM, Alec wrote:

...

`lookupEntry` seems fine to me...

\begin{bikeshedding} but it bugs me a little that (according to the API) Sets have "members" (`member`, `notMember`, and `splitMember`) and "elems" (`elems`, `elemAt`), but (at least as of yet) no "entries". (In my brief scan of the docs, it appears "element" is the preferred English for "thing that can be in a Set"). Andreas' suggestion applies the name to Map as well, so I buy that "entry" is actually a new notion distinct from "element" or "member"---but if a user isn't expected to have that notion in mind when seeking this functionality, it seems mildly disadvantageous to introduce a new word for "thing that can be in a Set" to the API. \end{bikeshedding}

"I love bikesheds! Don't you!?" :) I can only agree that it's a little incongrouous... but I'll defer to maintainer's privilege in the interest of getting things done :). Regards,

David Feuer

6:16 p.m.

Paint it what you like. Just not `lookup` :-). On Wed, Jun 29, 2016 at 6:06 PM, Bardur Arantsson wrote:

...

On 06/29/2016 11:48 PM, Alec wrote:

...
`lookupEntry` seems fine to me...

\begin{bikeshedding} but it bugs me a little that (according to the API) Sets have "members" (`member`, `notMember`, and `splitMember`) and "elems" (`elems`, `elemAt`), but (at least as of yet) no "entries". (In my brief scan of the docs, it appears "element" is the preferred English for "thing that can be in a Set"). Andreas' suggestion applies the name to Map as well, so I buy that "entry" is actually a new notion distinct from "element" or "member"---but if a user isn't expected to have that notion in mind when seeking this functionality, it seems mildly disadvantageous to introduce a new word for "thing that can be in a Set" to the API. \end{bikeshedding}

"I love bikesheds! Don't you!?" :)

I can only agree that it's a little incongrouous... but I'll defer to maintainer's privilege in the interest of getting things done :).

Regards,

_______________________________________________ Libraries mailing list Libraries@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

wren romano

30 Jun 30 Jun

3:26 p.m.

FWIW, as someone who often interns strings in her programs, I'd suggest *not* naming it "intern" (or variations thereon). One issue is the "and store it if it's not there yet" issue already mentioned. But another —and imo more important— issue is that one of the main goals of interning things is so that you can get a fast equality check. In general whenever we intern things we're going to return some token, which supports fast equality, and takes up as little memory as possible, but which can later on be cashed in for the original (shared) value if we actually need it. In impure languages we can use the pointer to the object as our token, but we can't do that (without serious grossness) in Haskell so we'd return some other token like an integer, perhaps with a newtype wrapper to keep track of its providence so we can avoid mixing up tokens from different intern tables. I already have an implementation of intern tables for ByteString in my local libraries; it'd be trivial to extend that to intern tables for String or Text or anything else supporting either (a) equality and hashability, or (b) orderability. IMO, if users want an intern table then they should ask for one, they shouldn't use some ad hoc combination of other data types which obfuscates the true purpose. Adding this to containers should be proposed on a separate thread, but I'm entirely willing to do it if people actually want it -- Live well, ~wren

Nicolas Godbout

4 Jul 4 Jul

11:32 a.m.

Here is recap of the numerous answers to this proposal one week into voting. As a reminder, the original proposal is to add the following to Data.Set lookup :: Ord a => a -> Set a -> Maybe a There is essentially unconditional support for inclusion of such a function. The debate centers around the name given to the function. There were quite a number of +1 votes for the ‘lookup’ name as is. There were also quite a number of valid objections, in particular from the "containers" package containers. The final name will _not_ be 'lookup', it remains to decide what the name is. The following names have been floated so far, together with opinions (expressed on the list and my own). * lookupEQ pro: it fits in the lookupGT, lookupLT, lookupGE, lookupLE cluster of existing Data.Set functions con: the cluster set of functions have atypical names and don't seem to generate any enthusiasm on the list * find pro: closer to the semantics, similar to Data.Map.findWithDefault con: nothing to do with the signature of Data.List.find In my opinion, this one is dead. * lookupSharedPointer, lookupWithSharing, lookupIntern pro: express the intention of returning a pointer to enable sharing con: new pattern for libraries, explicitly mentions pointers which is decidedly un-Haskell-like My strong vote goes to eliminating these. Pointer behaviour is fairly obvious to expert Haskellers, but should not be mentioned to beginners. Let them ask on the Haskell mailing list why there is a 'lookup'-like function on Sets and let us just briefly mention the sharing behavior in the Haddock docs. * lookupEntry, lookupKey, lookupWithKey pro: These names are in the spirit of "container" functions. con: In the case of 'Entry', it introduces a new concept distinct from a member or element. These are the names deserving discussion and voting. There is already a (+1) for 'lookupEntry' It was mentioned that a pattern emerges with 'insertWithKey', 'adjustWithKey', 'updateWithKey' functions from Data.Map > lookupWithKey :: Ord k => k -> Map a -> Maybe (k,a) suggesting the current proposal to converge to > lookupWithKey :: Ord a => a -> Set a -> Maybe a As a side note, it was noted in several replies that all relevant "container" lookup functions should come with the guarantee that the copy from the container is returned. I vote (+1) on that! My personal take on the current matter is that whatever we choose should be compatible with Data.List. > lookup??? :: Ord a => [a] -> a -> Maybe a > lookup??? :: Ord a => a -> Set a -> Maybe a > lookup??? :: Ord k => k -> Map k a -> Maybe (k,a) where the element returned is the one from the container, enabling sharing. This kills the name 'lookup' since it is already taken in Data.List. What seems to make the most sense is 'lookupEntry', which defines the concept of 'entry' as whatever is logically stored in the container. A Map is therefore defined as logically storing key-value pairs, exactly as in an association list. +1 on 'lookupEntry' Nicolas.

David Feuer

11:49 a.m.

I think it bears mentioning that there's no need to discuss pointers to explain these functions. == in general may be coarser than structural equality, since most interesting data structures can represent the same abstract object in more than one way. So we need only explain that the result is the element stored in the set that is == to the requested value. On Jul 4, 2016 11:32 AM, "Nicolas Godbout" wrote:

...

Here is recap of the numerous answers to this proposal one week into voting. As a reminder, the original proposal is to add the following to Data.Set

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

There is essentially unconditional support for inclusion of such a function. The debate centers around the name given to the function. There were quite a number of +1 votes for the ‘lookup’ name as is. There were also quite a number of valid objections, in particular from the "containers" package containers. The final name will _not_ be 'lookup', it remains to decide what the name is.

The following names have been floated so far, together with opinions (expressed on the list and my own).

* lookupEQ pro: it fits in the lookupGT, lookupLT, lookupGE, lookupLE cluster of existing Data.Set functions con: the cluster set of functions have atypical names and don't seem to generate any enthusiasm on the list

* find pro: closer to the semantics, similar to Data.Map.findWithDefault con: nothing to do with the signature of Data.List.find In my opinion, this one is dead.

* lookupSharedPointer, lookupWithSharing, lookupIntern pro: express the intention of returning a pointer to enable sharing con: new pattern for libraries, explicitly mentions pointers which is decidedly un-Haskell-like My strong vote goes to eliminating these. Pointer behaviour is fairly obvious to expert Haskellers, but should not be mentioned to beginners. Let them ask on the Haskell mailing list why there is a 'lookup'-like function on Sets and let us just briefly mention the sharing behavior in the Haddock docs.

* lookupEntry, lookupKey, lookupWithKey pro: These names are in the spirit of "container" functions. con: In the case of 'Entry', it introduces a new concept distinct from a member or element. These are the names deserving discussion and voting. There is already a (+1) for 'lookupEntry' It was mentioned that a pattern emerges with 'insertWithKey', 'adjustWithKey', 'updateWithKey' functions from Data.Map > lookupWithKey :: Ord k => k -> Map a -> Maybe (k,a) suggesting the current proposal to converge to > lookupWithKey :: Ord a => a -> Set a -> Maybe a

As a side note, it was noted in several replies that all relevant "container" lookup functions should come with the guarantee that the copy from the container is returned. I vote (+1) on that!

My personal take on the current matter is that whatever we choose should be compatible with Data.List. > lookup??? :: Ord a => [a] -> a -> Maybe a > lookup??? :: Ord a => a -> Set a -> Maybe a > lookup??? :: Ord k => k -> Map k a -> Maybe (k,a) where the element returned is the one from the container, enabling sharing. This kills the name 'lookup' since it is already taken in Data.List. What seems to make the most sense is 'lookupEntry', which defines the concept of 'entry' as whatever is logically stored in the container. A Map is therefore defined as logically storing key-value pairs, exactly as in an association list.

+1 on 'lookupEntry'

Nicolas.

_______________________________________________ Libraries mailing list Libraries@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

David Feuer

2:46 p.m.

To add to the summary, we also considered a function to insert an element into a set or a pair into a map preserving the existing key. For maps, we'd want a variant of insertWithKey, I suppose. TBH, I find the current insertion behavior perplexing. Perhaps it would make sense to add modules with more sensible insertion functions? How much risk is there of breaking things by changing the behavior of the current functions to *preserve* elements/keys rather than replacing them, and making insertWithKey give the passed function the stored key rather than the given one? On Jul 4, 2016 11:32 AM, "Nicolas Godbout" wrote:

...

Here is recap of the numerous answers to this proposal one week into voting. As a reminder, the original proposal is to add the following to Data.Set

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

There is essentially unconditional support for inclusion of such a function. The debate centers around the name given to the function. There were quite a number of +1 votes for the ‘lookup’ name as is. There were also quite a number of valid objections, in particular from the "containers" package containers. The final name will _not_ be 'lookup', it remains to decide what the name is.

The following names have been floated so far, together with opinions (expressed on the list and my own).

* lookupEQ pro: it fits in the lookupGT, lookupLT, lookupGE, lookupLE cluster of existing Data.Set functions con: the cluster set of functions have atypical names and don't seem to generate any enthusiasm on the list

* find pro: closer to the semantics, similar to Data.Map.findWithDefault con: nothing to do with the signature of Data.List.find In my opinion, this one is dead.

* lookupSharedPointer, lookupWithSharing, lookupIntern pro: express the intention of returning a pointer to enable sharing con: new pattern for libraries, explicitly mentions pointers which is decidedly un-Haskell-like My strong vote goes to eliminating these. Pointer behaviour is fairly obvious to expert Haskellers, but should not be mentioned to beginners. Let them ask on the Haskell mailing list why there is a 'lookup'-like function on Sets and let us just briefly mention the sharing behavior in the Haddock docs.

* lookupEntry, lookupKey, lookupWithKey pro: These names are in the spirit of "container" functions. con: In the case of 'Entry', it introduces a new concept distinct from a member or element. These are the names deserving discussion and voting. There is already a (+1) for 'lookupEntry' It was mentioned that a pattern emerges with 'insertWithKey', 'adjustWithKey', 'updateWithKey' functions from Data.Map > lookupWithKey :: Ord k => k -> Map a -> Maybe (k,a) suggesting the current proposal to converge to > lookupWithKey :: Ord a => a -> Set a -> Maybe a

As a side note, it was noted in several replies that all relevant "container" lookup functions should come with the guarantee that the copy from the container is returned. I vote (+1) on that!

My personal take on the current matter is that whatever we choose should be compatible with Data.List. > lookup??? :: Ord a => [a] -> a -> Maybe a > lookup??? :: Ord a => a -> Set a -> Maybe a > lookup??? :: Ord k => k -> Map k a -> Maybe (k,a) where the element returned is the one from the container, enabling sharing. This kills the name 'lookup' since it is already taken in Data.List. What seems to make the most sense is 'lookupEntry', which defines the concept of 'entry' as whatever is logically stored in the container. A Map is therefore defined as logically storing key-value pairs, exactly as in an association list.

+1 on 'lookupEntry'

Nicolas.

_______________________________________________ Libraries mailing list Libraries@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

Nicolas Godbout

11:48 a.m.

Correction, there are several errors in the signatures at the end of my last message. > lookup??? :: Eq a => a -> [a] -> Maybe a > lookup??? :: Ord a => a -> Set a -> Maybe a Also, copying the pattern for maps gives a slightly stranger signature > lookup??? :: (Ord k, Eq a) => (k,a) -> Map k a -> Maybe (k,a) which combines a key lookup with an equality test on the value. Nicolas.

Henning Thielemann

28 Jun 28 Jun

5:19 a.m.

On Mon, 27 Jun 2016, Nicolas Godbout wrote:

...

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.

I think I'd prefer the (Map String String) variant to an obscure Set lookup function. I wonder whether you will later use the Map anyway, as the compiler grows and you need to attach more data to tokens. In order to make your intent clearer you might define newtype SharedToken = SharedToken String and use (Map String SharedToken).

Ben Millwood

14 Jul 14 Jul

11:33 a.m.

I agree with Henning, and moreover with wren's point that Data.Set is an often-unsatisfactory data structure for interning in general. Map can do the job more obviously and more comprehensively, at the cost of a few more pointers -- and when has Haskell ever been about trading clarity for fewer pointers? I don't think I'll formally vote, since I haven't written any Haskell in months, but I think the addition of this at-first-glance seemingly-useless function adds surprise and a little bit of headscratching to the user interface as a whole, to the extent that I feel like it has a "weirdness cost" even if most users can just ignore it. It also complicates (in my mind) the semantic story of Data.Set, from something purely about a collection of elements and a membership test to something which has specific opinions on which of two notionally "equal" things are most appropriate in a given situation. I think the cost of turning Data.Set from a simple thing into a complicated thing is a subtle one that should not totally be overlooked -- API simplicity is a virtue in itself. Add to that Henning and wren's evidence, which I interpret as saying that this function isn't quite the *perfect* tool for seemingly *any* job, and it doesn't seem worth the cognitive / maintenance cost to me. (I perhaps do not expect these considerations to be very strong or very important, but I think it would be unwise to ignore them altogether.) On Tue, Jun 28, 2016 at 11:19:16AM +0200, Henning Thielemann wrote:

...

On Mon, 27 Jun 2016, Nicolas Godbout wrote:

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

I think I'd prefer the (Map String String) variant to an obscure Set lookup function. I wonder whether you will later use the Map anyway, as the compiler grows and you need to attach more data to tokens. In order to make your intent clearer you might define

newtype SharedToken = SharedToken String

and use (Map String SharedToken). _______________________________________________ Libraries mailing list Libraries@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

David Turner

28 Jun 28 Jun

12:38 p.m.

+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

David Feuer

29 Jun 29 Jun

2:12 a.m.

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

Joachim Breitner

4:18 a.m.

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

Edward Kmett

5:17 a.m.

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

Andreas Abel

8:36 a.m.

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 mailto: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 > mailto:dct25-561bs@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@haskell.org mailto:Libraries@haskell.org > > http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries > > > > _______________________________________________ > > Libraries mailing list > > Libraries@haskell.org mailto:Libraries@haskell.org > > http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries > > > _______________________________________________ > Libraries mailing list > Libraries@haskell.org mailto:Libraries@haskell.org > http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries --

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

_______________________________________________ Libraries mailing list Libraries@haskell.org mailto: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

-- Andreas Abel <>< Du bist der geliebte Mensch. Department of Computer Science and Engineering Chalmers and Gothenburg University, Sweden andreas.abel@gu.se http://www2.tcs.ifi.lmu.de/~abel/

David Feuer

1:39 p.m.

+1 for lookupEntry. I think that's very intuitive. On Wed, Jun 29, 2016 at 8:36 AM, Andreas Abel 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 mailto: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 > mailto:dct25-561bs@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@haskell.org mailto:Libraries@haskell.org > > http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries > > > > _______________________________________________ > > Libraries mailing list > > Libraries@haskell.org mailto:Libraries@haskell.org > > http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries > > > _______________________________________________ > Libraries mailing list > Libraries@haskell.org mailto:Libraries@haskell.org > http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries --

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

_______________________________________________ Libraries mailing list Libraries@haskell.org mailto: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

-- Andreas Abel <>< Du bist der geliebte Mensch.

Department of Computer Science and Engineering Chalmers and Gothenburg University, Sweden

andreas.abel@gu.se http://www2.tcs.ifi.lmu.de/~abel/ _______________________________________________ Libraries mailing list Libraries@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

David Feuer

10:35 a.m.

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

3232

Age (days ago)

3249

Last active (days ago)

List overview

Download

32 comments

16 participants

participants (16)

Alec
Andreas Abel
Bardur Arantsson
Ben Millwood
Chris Wong
David Feuer
David Thomas
David Turner
Edward Kmett
Henning Thielemann
Joachim Breitner
Malcolm Wallace
Michael Snoyman
Nicolas Godbout
Oliver Charles
wren romano