[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
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))))))))))
- Comparing two hash tables for equality?,
Aleksandar Sandic <=