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

[Nicolas Godbout]

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.