Comparing two hash tables for equality?

[Aleksandar Sandic]

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))))))))))