Arbitrary instance for HashMap is unfortunate

[treeowl]

arbitrary for HashMap k v (in tests/Strictness.hs) is based on fromList. This means that only HashMap shapes that can be produced by fromList will be represented in the inputs to test functions.

[treeowl]

I looked into trying to improve this myself. Unfortunately, doing so requires a clear understanding of the data structural invariants, which don't seem to be specified in the source.

[tibbe]

It's a bit tricky to create valid structures without going via the public API, you essentially have to mirror what insertion does.

[treeowl]

Is repeated insertion sufficient to achieve all possible trees, or is deletion necessary too? For instance, if I insert two keys that collide, and then delete the first, will I get the same tree as if I'd only inserted the second?

…

On Jun 12, 2017 10:02 PM, "Johan Tibell" ***@***.***> wrote: It's a bit tricky to create valid structures without going via the public API, you essentially have to mirror what insertion does. — You are receiving this because you authored the thread. Reply to this email directly, view it on GitHub <#154 (comment)>, or mute the thread <https://github.com/notifications/unsubscribe-auth/ABzi_a8PtgfNvtzbugcBZI2B3zrYy0t1ks5sDdkJgaJpZM4N2qFH> .

[tibbe]

We should probably not assume that only insertions get you all trees, because there's an implementation option to either collapse unnecessarily deep branches eagerly or lazily on deletion.

[sjakobi]

I just now noticed the work in #157.

@treeowl In #157 (comment) you said

I think we've removed the need for it by removing the representation
redundancy. See the changes in Eq implementation.

Could you expand a bit on this? Which changes does this refer to? Which redundancy was removed?

Do these changes mean that this issue was already fixed?

[treeowl]

It used to be that certain paths weren't compressed under some circumstances. I don't remember the circumstances. So there could have been multiple tree shapes representing the same map. That meant maps could sometimes get inefficient, and it made the Eq instance less efficient, so we changed it.

[sjakobi]

Thanks! #39 and #193 look related.

Is there any documentation on these invariants? Are they tested?

Seems like something that we'd need to be careful about when addressing #225 or #226.

[sjakobi]

Since HashMaps have been canonicalized I think we can close this issue now.