Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

better instance Hashable IntSet? #964

Open
jwaldmann opened this issue Jul 17, 2023 · 8 comments
Open

better instance Hashable IntSet? #964

jwaldmann opened this issue Jul 17, 2023 · 8 comments

Comments

@jwaldmann
Copy link
Contributor

cross reference to haskell-unordered-containers/hashable#269

@jwaldmann
Copy link
Contributor Author

jwaldmann commented Jul 19, 2023

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
Copy link
Contributor

treeowl commented Jul 19, 2023

@jwaldmann Correct.

@meooow25
Copy link
Contributor

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
Copy link
Contributor

treeowl commented Jul 19, 2023

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
Copy link
Contributor Author

Ah yes, the Tip includes the prefix.

@treeowl
Copy link
Contributor

treeowl commented Jul 19, 2023

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
Copy link
Contributor Author

@treeowl
Copy link
Contributor

treeowl commented Jul 20, 2023

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.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

No branches or pull requests

3 participants