unofficial mirror of guile-user@gnu.org 
 help / color / mirror / Atom feed
* Comparing two hash tables for equality?
@ 2018-08-26 10:01 Aleksandar Sandic
  2018-08-26 22:49 ` Mark H Weaver
  0 siblings, 1 reply; 8+ messages in thread
From: Aleksandar Sandic @ 2018-08-26 10:01 UTC (permalink / raw)
  To: guile-user

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






^ permalink raw reply	[flat|nested] 8+ messages in thread

end of thread, other threads:[~2018-08-29  4:46 UTC | newest]

Thread overview: 8+ messages (download: mbox.gz follow: Atom feed
-- links below jump to the message on this page --
2018-08-26 10:01 Comparing two hash tables for equality? Aleksandar Sandic
2018-08-26 22:49 ` Mark H Weaver
2018-08-26 23:37   ` John Cowan
2018-08-27 22:14     ` Aleksandar Sandic
2018-08-29  4:46       ` Mark H Weaver
2018-08-27 20:25   ` Arne Babenhauserheide
2018-08-27 21:53   ` Aleksandar Sandic
2018-08-28  7:37     ` Mark H Weaver

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).