Comparing hash, ptr, str gives you a pretty good acceptance/rejection test.
hash for the quick rejection, ptr for quick acceptance, str for accuracy.
Especially since the particular fingerprints for Typeable at least are
usually made up of 3 bytestrings that were just stuffed in and forgotten
about.
That said, this would seem to bring ByteString or at least Ptr in at a
pretty low level for the level of generality folks seem to be suddenly
seeking.
-Edward
On Wed, Feb 20, 2013 at 12:12 PM, Ian Lynagh
On Fri, Feb 15, 2013 at 02:45:19PM +0000, Simon Marlow wrote:
Remember that fingerprinting is not hashing. For fingerprinting we need to have a realistic expectation of no collisions. I don't think FNV is suitable.
I'm sure it would be possible to replace the C md5 code with some Haskell. Performance *is* important here though - Typeable is in the inner loop of certain generic programming libraries, like SYB.
We currently just compare hash(str) for equality, right? Could we instead compare (hash str, str) ? That would be even more correct, even if a bad/cheap hash function is used, and would only be slower for the case where the types match (unless you're unlucky and get a hash collision).
In fact, we may be able to arrange it so that in the equal case the strings are normally exactly the same string, so we can do a cheap pointer equality test (like ByteString already does) to make the equal case fast too (falling back to actually checking the strings are equal, if they aren't the same string).
Thanks Ian
_______________________________________________ Glasgow-haskell-users mailing list Glasgow-haskell-users@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-users