search

haskell / containers

Assorted concrete container types
https://hackage.haskell.org/package/containers
314 stars 177 forks source link

better instance Hashable IntSet? #964

Open jwaldmann opened 12 months ago

jwaldmann commented 12 months ago

cross reference to https://github.com/haskell-unordered-containers/hashable/issues/269

jwaldmann commented 12 months ago

for a given set of elements, the IntSet representation is unique? E.g., "the mask is the largest position ..." https://github.com/haskell/containers/blob/master/containers/src/Data/IntSet/Internal.hs#L261

Then a hash function could just use structure and contents of the internal representation generically?

treeowl commented 12 months ago

@jwaldmann Correct.

meooow25 commented 12 months ago

Correct, but it would be wasteful. The Tips contain all the elements, it would be sufficient to just hash the contents of those (ignoring Bins).

treeowl commented 12 months ago

Correct, but it would be wasteful. The Tips contain all the elements, it would be sufficient to just hash the contents of those (ignoring Bins).

Oh yeah, I think there is redundant info there. I'd have to review the representation; it's been a little while.

jwaldmann commented 12 months ago

Ah yes, the Tip includes the prefix.

treeowl commented 12 months ago

We could offer

serialize :: (Word -> r -> r) -> r -> IntSet -> r

This could be used to hash efficiently, with serialize written so it can inline. What would be a good matching deserialize type though?

jwaldmann commented 12 months ago
treeowl commented 12 months ago

I doubt that's quite what we'd want for Ord, but maybe close. The use case is that I'd be more comfortable with "publicly" exporting serialize/deserialize than a function that's only good for writing the Hashable instance.