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

From: Matthew Flatt (mflatt at cs.utah.edu)
Date: Thu May 29 09:24:14 EDT 2003

At Thu, 29 May 2003 08:16:03 -0500 (CDT), Jacob Matthews wrote:
> Here's a real-world situation that's affected by this property: a while
> back, Mike Machenry and I implemented a functional-sets library a using a
> binary search tree as the underlying set representation. Of course we had
> to have keys that would all be comparable with each other for this
> representation to work out, but it didn't particularly matter what the
> keys were, so we just used each item's hash value as its binary-tree key.
> Now it sounds as though symbols inserted into these sets will get lost in
> programs that rely on the property that 'a = 'a, so our sets have a bug.

Again, it sounds like you had to keep the item (such as 'a) in the
tree, so there's no bug.

The underlying principle here is that you're going to compare the items
eventually (since a hash key does not uniquely determine an item), so
the hash key will work correctly, by definition.

Matthew



Posted on the users mailing list.