Paste in Data.Set and check if the item exists at the same time

Question

Is there an efficient way to insert a value into Data.Set , while at the same time checking to see if that value was already a member of the set?

If not, is there any specific reason why such a function would not be possible to record with the current set implementation in the containers library?

Answer 1

You can do this with O(log n) complexity, taking advantage of the fact that size is O(1) , and just compare before and after:

 -- | Inserts a value into the Set. If the value was not already in the set, -- | then True is returned, otherwise False insertIfMissing :: Ord a => a -> Set a -> (Set a, Bool) insertIfMissing as = (newSet, missing) where newSet = Set.insert as oldSize = Set.size s newSize = Set.size newSet missing = oldSize < newSize 

And if you are not interested in whether it was already present, then this should not calculate the missing part thanks to laziness.

Answer 2

In fact, you can write such a function by slightly changing the Set.insert function. I decided to return Maybe (Set a) , so the function creates a new Set if the element does not exist. It would also be possible to write a function with (Bool, Set a) as the return type.

 insertMember :: Ord a => a -> Set a -> Maybe (Set a) insertMember = go where go :: Ord a => a -> Set a -> Maybe (Set a) STRICT_1_OF_2(go) go x Tip = Just $ singleton x go x (Bin sz ylr) = case compare xy of LT -> do l' <- go xl return $ balanceL yl' r GT -> do r' <- go xr return $ balanceR yl EQ -> Nothing