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.<div>
<br></div><div>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.<br><div><br></div><div>-Edward<br><br><div class="gmail_quote">
On Wed, Feb 20, 2013 at 12:12 PM, Ian Lynagh <span dir="ltr"><<a href="mailto:ian@well-typed.com" target="_blank">ian@well-typed.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<div class="im">On Fri, Feb 15, 2013 at 02:45:19PM +0000, Simon Marlow wrote:<br>
><br>
> Remember that fingerprinting is not hashing. For fingerprinting we<br>
> need to have a realistic expectation of no collisions. I don't<br>
> think FNV is suitable.<br>
><br>
> I'm sure it would be possible to replace the C md5 code with some<br>
> Haskell. Performance *is* important here though - Typeable is in<br>
> the inner loop of certain generic programming libraries, like SYB.<br>
<br>
</div>We currently just compare<br>
hash(str)<br>
for equality, right? Could we instead compare<br>
(hash str, str)<br>
? That would be even more correct, even if a bad/cheap hash function is<br>
used, and would only be slower for the case where the types match<br>
(unless you're unlucky and get a hash collision).<br>
<br>
In fact, we may be able to arrange it so that in the equal case the<br>
strings are normally exactly the same string, so we can do a cheap<br>
pointer equality test (like ByteString already does) to make the equal<br>
case fast too (falling back to actually checking the strings are equal,<br>
if they aren't the same string).<br>
<br>
<br>
Thanks<br>
<span class="HOEnZb"><font color="#888888">Ian<br>
</font></span><div class="HOEnZb"><div class="h5"><br>
<br>
_______________________________________________<br>
Glasgow-haskell-users mailing list<br>
<a href="mailto:Glasgow-haskell-users@haskell.org">Glasgow-haskell-users@haskell.org</a><br>
<a href="http://www.haskell.org/mailman/listinfo/glasgow-haskell-users" target="_blank">http://www.haskell.org/mailman/listinfo/glasgow-haskell-users</a><br>
</div></div></blockquote></div><br></div></div>