Data.Set: add insertUnlessMember

[andreasabel]

For Data.Set, I am missing something comparable to Map.lookupInsertWithKey that combines a lookup and an insert. Suggestion (specification):

insertUnlessMember :: Ord a => a -> Set a -> Maybe (Set a)
insertUnlessMember a s = if member a s then Nothing else Just $ insert a s

Of course, that should have an efficient implementation that only traverses the tree once.

[tibbe]

Might be worth checking the performance gain. Lookups are usually much faster than inserts so a lookup + insert is often as fast as just an insert.

[andreasabel]

Yes, maybe, but why then has Map such a function and not Set?

[tibbe]

Someone probably thought it was faster (perhaps it is!), but I doubt it was tested.

[tibbe]

We could add it for consistency, but I would at least like to know if it actually helps. Our API suffers from a combinatoric explosion unfortunately, so I'd like to avoid growing it if not necessary.

[treeowl]

When comparison is expensive, the combined approach obviously wins. Obviously, that's not the best scenario for Set anyway, but it might be worth considering.

[tibbe]

@treeowl right, it can in theory be arbitrarily expensive. In the typical case however the runtime is dominated by the allocation done on insert. It's a typical memory bound problem (like most performance problems on modern CPUs).

[foxik]

Personally I am not sure we can make the implementation faster than the suggested one, notably when comparison is cheap like in the Set Int case. The reason are the Maybe allocations on every level.

Together with the fact that the proposed function is a simple combination of existing functions and is at most twice slower (assuming lookup complexity is dominated by insert complexity), I am not a big fan.

But please do not hesitate to surprise me with benchmark results :-)

[m-renaud]

This is very similar to #291, #166, #290 which propose:

lookupEntry :: (Ord a) => a -> Set a -> Maybe a
lookupEntry :: (Ord k) => k -> Map k v -> Maybe (k, v)

Would these functions address your use case? These have already (mostly*) been approved by the libraries committee and have the potential of going into the API soon.

* There was general agreement, but the discussion was a while ago so I'm going to raise it again to make sure everyone is on board still.

[treeowl]

No, I think they go together.

…

On Dec 26, 2017 1:48 PM, "Matt Renaud" ***@***.***> wrote: This is very similar to #291 <#291>, #166 <#166>, #290 <#290> which propose: lookupEntry :: (Ord a) => a -> Set a -> Maybe alookupEntry :: (Ord k) => k -> Map k v -> Maybe (k, v) Would these functions address your use case? These have already (mostly*) been approved by the libraries committee and have the potential of going into the API soon. * *There was general agreement, but the discussion was a while ago so I'm going to raise it again to make sure everyone is on board still.* — You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub <#161 (comment)>, or mute the thread <https://github.com/notifications/unsubscribe-auth/ABzi_d-gty8m_pwPrCJ5aK3J27zlqkMVks5tET-EgaJpZM4Fcx-Z> .

[m-renaud]

Oh yeah, duh, I read this wrong. Sorry for the noise.

[sjakobi]

With the Data.Set.alterF function added in 0.6.3.1, it's easy to define

insertUnlessMember = alterF (\member_ -> if member_ then Nothing else Just True)

I'll tentatively close this issue, but feel free to reopen, if there's more to do here.