Email list hosting service & mailing list manager


hash-by-identity guarantees of change consistency? Panu Kalliokoski 19 Apr 2006 21:18 UTC

A problem in the SRFI has been brought to my attention, namely that
hash-by-identity is not required to remain the same for mutable
structures if you change their contents (and indeed won't in the
reference implementation).  Arguably this guarantee should be made, as
lack of it seriously lowers the value of eq? hash tables.

However, there is this problem that there is no way to portably provide
an appropriate hash function that will provide change consistency.  The
best one can do is to give a dummy function that returns the same hash
value for e.g. all pairs (thus making hash table lookup an O(n)
operation) or to give a assq-cache backed hashing function (thus making
hashing on O(n) operation).  Both will fail the appropriateness
requirement of the SRFI.  So there's no way to implement the SRFI
portably, if change consistency is added.

Any ideas / suggestions on how to best approach this?

Panu

--
personal contact:	xxxxxx@helsinki.fi, +35841 5323835
technical contact:	xxxxxx@iki.fi, http://www.iki.fi/atehwa/
PGP fingerprint:	0EA5 9D33 6590 FFD4 921C  5A5F BE85 08F1 3169 70EC