IntMap should offer an unsafe variant of insert

[Boarders]

It would be nice for IntMap and Map to offer variants on insert (probably called unsafeInsertNew) for keys we happen to know cannot be in the map. I'm happy to implement this if you all think it would be a worthwhile addition.

[treeowl]

Interesting. And a deletion version too? Should we add an Unsafe module for these, and slowly migrate the other unsafe operations to such modules?

[Boarders]

I think that'd be a good idea and it would allow us to add functions like the one suggested in this issue too: https://github.com/haskell/containers/issues/798

[sjakobi]

What would be the advantage of unsafeInsertNew over the existing insert function? Better performance I suspect?! How so?

[Boarders]

It would be better performance as we don't need to do any of the checks necessary to see if the key is already present in the map (e.g. if we are constructing a IntMap from nothing or from an ascending list of key value pairs then there is no point in such a check)

[Boarders]

To be more specific the code is:

insert :: Key -> a -> IntMap a -> IntMap a
insert !k x t@(Bin p m l r)
  | nomatch k p m = link k (Tip k x) p t
  | zero k m      = Bin p m (insert k x l) r
  | otherwise     = Bin p m l (insert k x r)
insert k x t@(Tip ky _)
  | k==ky         = Tip k x
  | otherwise     = link k (Tip k x) ky t
insert k x Nil = Tip k x

We can get rid of the check for equality at the tip and it may make sense to do something other than using nomatch.

[sjakobi]

We can get rid of the check for equality at the tip

One branch less.

and it may make sense to do something other than using nomatch.

What could that be?! I don't have the internals paged in right now, so I fail to understand how that branch could be different when we know that the key is new.

if we are constructing a IntMap from nothing or from an ascending list of key value pairs

fromDistinctAscList already skips any key equality checks.

So far I wouldn't expect any large performance gains from this, but I can imagine code where it might still matter.

[Boarders]

One branch less for a heavy workload of inserts when the writer knows the check is unnecessary seems like a free win to me. With regards to the specifics, I haven't thought about whether there is truly a better algorithm, I was just stating that it is a possibility.