From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!.POSTED!not-for-mail From: Aleksandar Sandic Newsgroups: gmane.lisp.guile.user Subject: Comparing two hash tables for equality? Date: Sun, 26 Aug 2018 12:01:17 +0200 Message-ID: <2418985.EcWt8OQBW1@aleksandar-ixtreme-m5740> NNTP-Posting-Host: blaine.gmane.org Mime-Version: 1.0 Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable X-Trace: blaine.gmane.org 1535292371 27934 195.159.176.226 (26 Aug 2018 14:06:11 GMT) X-Complaints-To: usenet@blaine.gmane.org NNTP-Posting-Date: Sun, 26 Aug 2018 14:06:11 +0000 (UTC) To: guile-user@gnu.org Original-X-From: guile-user-bounces+guile-user=m.gmane.org@gnu.org Sun Aug 26 16:06:07 2018 Return-path: Envelope-to: guile-user@m.gmane.org Original-Received: from lists.gnu.org ([208.118.235.17]) by blaine.gmane.org with esmtp (Exim 4.84_2) (envelope-from ) id 1ftvg7-00079W-Dn for guile-user@m.gmane.org; Sun, 26 Aug 2018 16:06:07 +0200 Original-Received: from localhost ([::1]:49200 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1ftviD-0005Dk-HS for guile-user@m.gmane.org; Sun, 26 Aug 2018 10:08:17 -0400 Original-Received: from eggs.gnu.org ([2001:4830:134:3::10]:47050) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1fts5b-00031i-QU for guile-user@gnu.org; Sun, 26 Aug 2018 06:16:14 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1ftrrI-0001oX-PU for guile-user@gnu.org; Sun, 26 Aug 2018 06:01:28 -0400 Original-Received: from mout01.posteo.de ([185.67.36.141]:49675) by eggs.gnu.org with esmtps (TLS1.0:DHE_RSA_AES_256_CBC_SHA1:32) (Exim 4.71) (envelope-from ) id 1ftrrI-0001md-EZ for guile-user@gnu.org; Sun, 26 Aug 2018 06:01:24 -0400 Original-Received: from submission (posteo.de [89.146.220.130]) by mout01.posteo.de (Postfix) with ESMTPS id E9393210D7 for ; Sun, 26 Aug 2018 12:01:18 +0200 (CEST) Original-Received: from customer (localhost [127.0.0.1]) by submission (posteo.de) with ESMTPSA id 41yrBk2Ycrz6tm6 for ; Sun, 26 Aug 2018 12:01:18 +0200 (CEST) X-detected-operating-system: by eggs.gnu.org: GNU/Linux 2.2.x-3.x [generic] X-Received-From: 185.67.36.141 X-Mailman-Approved-At: Sun, 26 Aug 2018 10:07:48 -0400 X-BeenThere: guile-user@gnu.org X-Mailman-Version: 2.1.21 Precedence: list List-Id: General Guile related discussions List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: guile-user-bounces+guile-user=m.gmane.org@gnu.org Original-Sender: "guile-user" Xref: news.gmane.org gmane.lisp.guile.user:14757 Archived-At: Hello everyone, I have been looking through the reference manual, but there does not seem t= o=20 be a procedure for comparing two hash tables for equality. The procedure=20 '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 =3D #f scheme@(guile-user)> (equal? h1 h1) $2 =3D #t Is this the intended behaviour? If so, how can I compare two hash tables fo= r=20 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. =20 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?' =20 Two hash tables are always 'hash-equal?' if they are 'eq?'." ;; First take care of the trivial cases. Then compare the length of t= he ;; tables; if the lengths don't match the tables not equal. Finally,= =20 loop ;; over the keys of one table and compare the values with those in th= e=20 other ;; table. ;; ;; This algorithm traverses the first tables thrice and the second ta= ble ;; twice in the worst case: Once each to count the keys, once the fir= st=20 one ;; to collect the keys, and once both to compare all values. The loop= =20 will ;; terminate the instant a mismatch is found. ;; ;; If the first value is a hash table we call this function recursive= ly ;; 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 (=CE=BB (k v keys) (1+ keys)) 0 h1)) (n-keys2 (hash-fold (=CE=BB (k v keys) (1+ keys)) 0 h2))) (if (not (=3D n-keys1 n-keys2)) #f (do ((keys (hash-fold (=CE=BB (k v keys) (cons k keys)) '() h= 1) (cdr=20 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-equ= al?=20 v1 v2))) ((not (equal? v1 (cdr v2))) (set! same? #f))))))))))