eq and hashing (was Re: [plt-scheme] How to make unit functors?)

From: Robby Findler (robby at cs.uchicago.edu)
Date: Thu May 29 11:09:47 EDT 2003

At 29 May 2003 10:46:50 -0400, andrew cooke wrote:
>   apologies if i've missed some scheme-specific point (i'm just
>   lurking here).  maybe eq-hash should only be used to test
>   (memory-address based) equality and there are other hash functions
>   that should be used when using the hash in data structures?

No worries! The only possibility of a scheme-specific point that you
may have missed (in fact, the one that was bugging me :) is that the
symbol:

   'x

should also be memeory-address based equal to

   'x

even if they weren't typed in at the same place. In fact, if you only
use eq? (which is the memory-address based equality predicate), you
will find that these symbols are always eq?.

But, if you take the hash-code of one of them and then wait a while
(and perform some garbage collections) then take the hash-code of the
other, you'll find that they are different. 

Since the docs have this guarantee:

  for all v1, v2
    (eq? v1 v2) => (= (eq-hash-code v1) (eq-hash-code v2))

or, equivalently:

   for all v1, v2
     not (= (eq-hash-code v1) (eq-hash-code v2)) => not (eq? v1 v2)

we have now discovered that the two 'xs weren't eq? (since their hash
codes are different).

Thus the problem.

Still, Matthew has made an effective argument that this won't matter in
practice (except, of course, to confuse at least two people on this
list :). 

Robby


Posted on the users mailing list.