Weird level-deletion in intersectionArrayBy

[sjakobi]

unordered-containers/Data/HashMap/Internal.hs

Lines 1862 to 1865 in 4da2c20

	case len of
	0 -> pure Empty
	1 -> A.read mary 0
	_ -> bitmapIndexedOrFull bFinal <$> (A.unsafeFreeze =<< A.shrink mary len)

I'm referring to line 1864 where, instead of returning a BitmapIndexed node, its only element is returned.

@oberblastmeister Could you clarify the reasoning behind this code?

I'm wondering whether this might mess with the shift/subkey-logic, effectively misplacing some elements, so they can't be found by lookups, deletions etc.

[sjakobi]

As a precaution, I've deprecated v0.2.19.0 on Hackage. I can un-deprecate it if it turns that this code is correct.

[oberblastmeister]

Why would this mess with shift/subkey-logic? This is done in other places of the code already, such as delete. Moreover, it has to be done whenever items could be removed, in order to satisfy the invariants in #366.

[oberblastmeister]

I think this may be wrong, because we need to check if it is a Leaf or Collision, like in delete.

[sjakobi]

I think this may be wrong, because we need to check if it is a Leaf or Collision, like in delete.

Exactly!

[treeowl]

It is a bit curious that we don't have general path compression. I suppose it's not supposed to be too important if the hashing is good? Of course, instances like Hashable Int are very not good, so we might want to experiment. OTOH, it might be better to just write a different data structure for Int. @wrengr was talking about non-hashed array-mapped tries at one point; I don't know how far she got exploring that.

[sjakobi]

@treeowl Let's not discuss design issues on a minor bug ticket. Feel free to investigate #391 if you like that idea.