containers
containers copied to clipboard
haskell
Add lookup function to Data.Set
WHAT?
It is proposed to add a lookup function on Set in the "containers" package. The proposal is logged here first for reference in a later discussion on the Haskell libraries mailing list.
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 Pull Request (to be added shortly) contains the straight-forward implementation of the lookup function on Set, with test cases.
I don't really like the name, since it doesn't really act like lookup for maps. You should certainly send the proposal to the libraries list, but I personally like the general idea. On Jun 27, 2016 5:25 PM, "Nicolas Godbout" [email protected] wrote:
WHAT?
It is proposed to add a lookup function on Set in the "containers" package. The proposal is logged here first for reference in a later discussion on the Haskell libraries mailing list.
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 Pull Request (to be added shortly) contains the straight-forward implementation of the lookup function on Set, with test cases.
— You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub https://github.com/haskell/containers/issues/290, or mute the thread https://github.com/notifications/unsubscribe/ABzi_V1KxHyvV3esUe3V_a-D51c3OCXaks5qQD-ugaJpZM4I_ha1 .
Hey @DrNico, did you get around to sending a proposal to the libraries list? I noticed in PR #291 that the current suggested name is lookupEntry which SGTM. Also, could you add a similar function to Data.IntSet and Data.IntMap (commented there as well)?
