guile-user
[Top][All Lists]

## Comparing two hash tables for equality?

 From: Aleksandar Sandic Subject: Comparing two hash tables for equality? Date: Sun, 26 Aug 2018 12:01:17 +0200

```Hello everyone,

I have been looking through the reference manual, but there does not seem to
be a procedure for comparing two hash tables for equality. The procedure
'equal?' only returns true if the two tables are also 'eq?':

scheme@(guile-user)> (define h1 (make-hash-table))
scheme@(guile-user)> (define h2 (make-hash-table))
scheme@(guile-user)> (equal? h1 h2)
\$1 = #f
scheme@(guile-user)> (equal? h1 h1)
\$2 = #t

Is this the intended behaviour? If so, how can I compare two hash tables for
equality then? I have rolled my own function for the time being:

(define (hash-table-equal? h1 h2)
"- Scheme procedure: hash-table-equal? h1 h2
Compare two hash tables for entry-wise equality.

The arguments 'h1' and 'h2' are not equal if and only if either:
- One of them is not a hash table
- They do not have the same number of entries
- Values for the same key are not 'equal?' or 'hash-equal?'

Two hash tables are always 'hash-equal?' if they are 'eq?'."
;; First take care of the trivial cases. Then compare the length of the
;; tables; if the lengths don't match the tables not equal. Finally,
loop
;; over the keys of one table and compare the values with those in the
other
;; table.
;;
;; This algorithm traverses the first tables thrice and the second table
;; twice in the worst case: Once each to count the keys, once the first
one
;; to collect the keys, and once both to compare all values. The loop
will
;; terminate the instant a mismatch is found.
;;
;; If the first value is a hash table we call this function recursively
;; because hash tables are never 'equal?' (unless they are 'eq?')
(cond
((not (hash-table? h1)) #f)
((not (hash-table? h2)) #f)
((eq? h1 h2) #t)
(else
(let ((n-keys1 (hash-fold (λ (k v keys) (1+ keys)) 0 h1))
(n-keys2 (hash-fold (λ (k v keys) (1+ keys)) 0 h2)))
(if (not (= n-keys1 n-keys2))
#f
(do ((keys (hash-fold (λ (k v keys) (cons k keys)) '() h1) (cdr
keys))
(same? #t))
((or (not same?) (null? keys))
same?)
(let* ((key (car keys))
(v1 (hash-ref h1 key))
(v2 (hash-get-handle h2 key)))
(cond
((not v2)                   (set! same? #f))
((hash-table? v1)           (set! same? (hash-table-equal?
v1 v2)))
((not (equal? v1 (cdr v2))) (set! same? #f))))))))))

```