From: Paulo J. Matos aka PDestroy
Subject: Same elements in hash tables
Date:
Message-ID: <3B113E85.C29B93FF@netcabo.pt>
Hi,
I'm not being able to imagine a way to check if 2 hash tables have the
same elements indexed by the same keys. How can I do that?
Best regards,
--
+------------------Paulo J. Matos aka PDestroy--------------------+
| ICQ # 361853 | http://www.pdestroy.net | ········@netcabo.pt |
| http://iascp.sourceforge.net | http://mega.ist.utl.pt/~pocm |
| "Fixed width font LIVEZ!" | "Portability came to rule!" |
+-----------------------------------------------------------------+
Life's no picnic and then... you die!
- Anonymous
"Paulo J. Matos aka PDestroy" <········@netcabo.pt> writes:
> Hi,
> I'm not being able to imagine a way to check if 2 hash tables have the
> same elements indexed by the same keys. How can I do that?
Seems like something like this would work. Note that I banged it out
kind of quickly and only tested it on a couple of simple examples.
Caveat emptor.
==============================================================================
(defun hash-table-equal (table1 table2 &key (test #'eql))
(flet ((half-test (table1 table2)
(maphash #'(lambda (key val)
(multiple-value-bind (other-val present-p)
(gethash key table2)
(unless (and present-p
(funcall test val other-val))
(return-from hash-table-equal
;; on failure, second value is a mismatched key
(values nil key)))))
table1)))
(half-test table1 table2)
(half-test table2 table1)
t))
(defvar *h1* (make-hash-table :test 'equalp))
(dotimes (i 10) (setf (gethash i *h1*) (format nil "~r" i)))
(defvar *h2* (make-hash-table :test 'eql))
(dotimes (i 10) (setf (gethash i *h2*) (format nil "~r" i)))
(hash-table-equal *h1* *h2*)
=> NIL, 0 ;; i.e., (not (eql (gethash 0 *h1*) (gethash 0 *h2*)))
(hash-table-equal *h1* *h2* :test #'equal)
=> T
(setf (gethash 11 *h1*) "eleven")
(hash-table-equal *h1* *h2* :test #'equal)
=> NIL, 11 ;; i.e., *h2* has no entry with key 0
(setf (gethash 11 *h1*) "eleven")
(hash-table-equal *h1* *h2* :test #'equal)
=> T
;; But note well:
(setf (gethash 11.0 *h2*) "eleven")
=> T
;; I think this is the behavior you want, but it may be surprising
;; nevertheless. These tables don't have the same elements; they just
;; yield the same mappings.
;;
;; If you really want the same elements, you'd probably instead do some
;; kind of set-equal test on the result of collecting all the keys and
;; values. It's not obvious to me how to do that efficiently without
;; some consing, but it doesn't seem very hard to do if you do allow
;; consing. By contrast, the routine above does not cons, which I happen
;; to think comparison predicates should try to have as a goal.
;; I'll leave the other version as an excercise.
"Paulo J. Matos aka PDestroy" <········@netcabo.pt> writes:
> I'm not being able to imagine a way to check if 2 hash tables have the
> same elements indexed by the same keys. How can I do that?
(equalp HASH1 HASH2) should do it.
Hrvoje Niksic <·······@arsdigita.com> writes:
> "Paulo J. Matos aka PDestroy" <········@netcabo.pt> writes:
>
> > I'm not being able to imagine a way to check if 2 hash tables have the
> > same elements indexed by the same keys. How can I do that?
>
> (equalp HASH1 HASH2) should do it.
Well, for varying meanings of "same", I suppose. Equality is no simple
matter, so certainly there are cases where EQUALP will be in the set
of reasonable interpretations the person wants; however, it's rarely
in the set I want.
Personally, I almost never use EQUALP except in a few situations
where I can prove it's not going to descend multiple levels of structure,
since the kinds of things it allows on recursive descent are pretty
liberal and therefore it's hard to assure correctness of the result.
This liberal interpretation upon descent coupled with the conservative
decision to test for equivalent table types leads to some weird stuff.
Consequently, I stand by my long-hand version as a "better" way of doing
it, because it gives you control of the predicate to descend with, and
because it doesn't rule out tables of different types as automatically
incompatible.
For example, the following "fringe cases" of the originally stated problem
have potentially surprising results under EQUALP if you're not used to
the degree of variation it permits:
(let ((x (make-hash-table)) (y (make-hash-table :test 'equal)))
(equalp x y))
=> NIL ; same elements and keys [i.e. none], but not same test
(let ((x (make-hash-table)) (y (make-hash-table :test 'equal)))
;; same elements and keys
(setf (gethash 1 x) "one")
(setf (gethash 1 y) "one")
(equalp x y))
=> NIL ; again, same elements and types, but not same test
(let ((x (make-hash-table)) (y (make-hash-table)))
;; same elements and keys
(setf (gethash 1 x) "one")
(setf (gethash 1 y) "ONE")
(equalp x y))
=> T ; EQUALP ignores case differences in sstrings
(let ((x (make-hash-table)) (y (make-hash-table)))
;; same elements and keys
(setf (gethash 1 x) 1)
(setf (gethash 1 y) 1.0")
;; equalp ignores mathematical type
(equalp x y))
=> T ; EQUALP uses =, which ignores representation types