[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

*To*: common-lisp@sail.stanford.edu*Subject*: re: EQUAL, and hash tables, and value/object distinctions*From*: goldman@vaxa.isi.edu*Date*: Tue, 05 Jul 88 17:49:37 PDT*Posted-date*: Tue, 05 Jul 88 17:49:37 PDT*Sender*: goldman@vaxa.isi.edu

Proposal: EQUAL should check for isomorphism of hash tables. I think that's fine; the issue is what properties define, and thus derive from, two hash tables being isomorphic. An interesting question arises when two hash tables have different key equality predicates, and (suppose) we've already decided to treat equality predicates as implementation details, and ignore them directly. Here's one answer: Declare two hash tables EQUAL if they include each other. That is, for every key K in hash table A, require that (EQUAL (GETHASH A K) (GETHASH B K *UNIQUE-UNKNOWN-VALUE*)) and the same for every key in table B. I definitely do not like that definition. I don't think that two hash tables with different equality predicates should be considered EQUAL unless they are both EMPTY. Rationale: A hash table is best though of as a mapping from (a subset of) the EQUIVALENCE CLASSES of an equivalence predicate to associated values. The fact the CommonLisp's functions for dealing with hash tables (GETHASH, MAPHASH) deal with an equivalence class through an exemplary member of the class should not lead us astray. The suggested semantics, as I read it, makes the issue of whether two hash tables are EQUAL dependent on which exemplars happen to be stored. For example, suppose HEQ and HEQUAL are hash tables, with equivalence predicates EQ and EQUAL, respectively. Further suppose (EQUAL xxx '(a b c)) and (EQUAL yyy '(a b c)) , but (NOT (EQ xxx yyy)) if I do (setf (gethash xxx HEQ) 1 (gethash yyy HEQUAL) 1) then, by my reading of the above definition, (NOT (EQUAL HEQ HEQUAL)) because the key yyy, in HEQUAL, is not a key in HEQ. But if I do (setf (gethash xxx HEQ) 1 (gethash xxx HEQUAL) 1) then they are EQUAL. I claim that the choice between two different exemplars of an E equivalence class should be transparent for a hash table with equivalence predicate E. I would define EQUALity of hash tables H1 and H2 in the following manner: either H1 and H2 are both empty, or the suggested mutual inclusion definition, with the added requirment that H1 and H2 have the same equivalence predicate. Note that this does not imply that MAPHASH applied to the two tables will generate the same sequence of key/value pairs -- the ordering used by maphash is an implementation detail, and could even change from one invocation to another on the same, unaltered, hash table. Also, "it is an error" to destructively modify a value that has been used as a key for a hashtable of equivalence E (or obtained via a MAPHASH over such a hashtable) in a manner that changes the E-class to which it belongs. I.e., the following is an incorrect program: (setf h (make-hash-table :test 'equal) xxx '(a b c)) (setf (gethash xxx h) 1) (setf (second xxx) nil) Neil

**Follow-Ups**:**EQUAL, and hash tables, and value/object distinctions***From:*jrose@Sun.COM (John Rose)

- Prev by Date:
**What have hashing and equality to do with each other?** - Next by Date:
**EQUAL, and hash tables, and value/object distinctions** - Previous by thread:
**Re: dynamic extent lisp objects** - Next by thread:
**EQUAL, and hash tables, and value/object distinctions** - Index(es):