Add tryInsert for sets and maps

[meooow25]

tryInsert :: Ord k => k -> a -> Map k a -> Maybe (Map k a)
tryInsert :: Ord a => a -> Set a -> Maybe (Set a)
tryInsert :: Int -> a -> IntMap a -> Maybe (IntMap a)
tryInsert :: Int -> IntSet -> Maybe IntSet

Inserts the value if the key is not in the map/set, otherwise returns Nothing.

This will be useful in nubOrdOn to avoid member+insert:

containers/containers/src/Data/Containers/ListUtils.hs

Lines 86 to 88 in d82a404

	go s (x:xs)
	| fx `Set.member` s = go s xs
	| otherwise = x : go (Set.insert fx s) xs

Alternate name suggestions are welcome.

If we go with tryInsert I think we should rename pop from #1134 to tryDelete for consistency. I didn't think of this name at that time. Luckily we haven't released it yet, so we can still change the name.

[meooow25]

Thinking more about this, it seems more appropriate for the map functions to be

tryInsert :: Ord k => k -> Map k a -> Maybe (a -> Map k a)
tryInsert :: Int -> IntMap a -> Maybe (a -> IntMap a)

This avoids creating an unnecessary thunk for the value, it needs to be supplied only if the key is absent.

[alexfmpe]

Alternate name suggestions are welcome.

I'd say tryInsert is ambiguous. I was going to suggest replace until I noticed it's actually the other way around, so how about insertIfMissing ?

This avoids creating an unnecessary thunk for the value, it needs to be supplied only if the key is absent.

Also, it's more primitive as the original signature can be defined in terms of it
tryInsert' k a m = fmap ($ a) $ tryInsert k m
but AFAICT not the other way around - where would we get the a from?

[meooow25]

insertIfMissing doesn't seem bad, maybe a bit longer than ideal.

Do you have a name suggestion for pop too?

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

It would be nice if the names can reflect that they are inverses somewhat.
deleteIfPresent seems like an obvious candidate, though it doesn't indicate that in case of the map the result contains the value.

[treeowl]

I like the idea of tryInsert :: Ord k => k -> Map k a -> Maybe (a -> Map k a), which can be implemented using the same machinery as alterF. But I don't think it's always a performance win; it always walks the tree twice, though rather faster the second time. So it's great if you might want to insert the key with multiple different values, but maybe not so great otherwise.

[alexfmpe]

insertIfMissing doesn't seem bad, maybe a bit longer than ideal.

touch ? Kinda like the CLI util that also creates a file if it doesn't exist but does not overwrite contents.

[meooow25]

I like the idea of tryInsert :: Ord k => k -> Map k a -> Maybe (a -> Map k a), which can be implemented using the same machinery as alterF.

Yes, in fact

tryInsert :: Ord k => k -> Map k a -> Maybe (a -> Map k a)
tryInsert k m = getCompose (alterF (Compose . maybe (Just Just) (\_ -> Nothing)) k m)

I will check if it optimizes well, then we can simply use this definition.

But I don't think it's always a performance win; it always walks the tree twice, though rather faster the second time. So it's great if you might want to insert the key with multiple different values, but maybe not so great otherwise.

It is a win over if member k m then m else insert k x m because of the faster second walk, that's the use case I am aiming for.

touch ? Kinda like the CLI util that also creates a file if it doesn't exist but does not overwrite contents.

Interesting, though it is a bit of a stretch. touch also updates the file timestamps, so the analogy isn't as clean.

[meooow25]

I'm having second thoughts about adding these since they are easily implemented using alterF. I'll let this sit for a bit.

I do want to avoid the comparisons in nubOrdOn, so I will prepare a change for that.