Add lookup function to Data.Set #290
Description
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.