From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!.POSTED!not-for-mail From: John Cowan Newsgroups: gmane.lisp.guile.user Subject: Re: Comparing two hash tables for equality? Date: Sun, 26 Aug 2018 19:37:54 -0400 Message-ID: References: <2418985.EcWt8OQBW1@aleksandar-ixtreme-m5740> <87o9dovj4z.fsf@netris.org> NNTP-Posting-Host: blaine.gmane.org Mime-Version: 1.0 Content-Type: text/plain; charset="UTF-8" X-Trace: blaine.gmane.org 1535326593 10784 195.159.176.226 (26 Aug 2018 23:36:33 GMT) X-Complaints-To: usenet@blaine.gmane.org NNTP-Posting-Date: Sun, 26 Aug 2018 23:36:33 +0000 (UTC) Cc: guile-user@gnu.org, asflin@gmx.de To: Mark H Weaver Original-X-From: guile-user-bounces+guile-user=m.gmane.org@gnu.org Mon Aug 27 01:36:28 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 1fu4a4-0002gQ-6f for guile-user@m.gmane.org; Mon, 27 Aug 2018 01:36:28 +0200 Original-Received: from localhost ([::1]:50722 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1fu4cA-0004HK-E1 for guile-user@m.gmane.org; Sun, 26 Aug 2018 19:38:38 -0400 Original-Received: from eggs.gnu.org ([2001:4830:134:3::10]:35642) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1fu4bk-0004H0-3p for guile-user@gnu.org; Sun, 26 Aug 2018 19:38:13 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1fu4bg-00023o-Cu for guile-user@gnu.org; Sun, 26 Aug 2018 19:38:11 -0400 Original-Received: from mail-wr1-x42b.google.com ([2a00:1450:4864:20::42b]:44862) by eggs.gnu.org with esmtps (TLS1.0:RSA_AES_128_CBC_SHA1:16) (Exim 4.71) (envelope-from ) id 1fu4be-000230-O7 for guile-user@gnu.org; Sun, 26 Aug 2018 19:38:08 -0400 Original-Received: by mail-wr1-x42b.google.com with SMTP id v16-v6so11907659wro.11 for ; Sun, 26 Aug 2018 16:38:06 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=ccil-org.20150623.gappssmtp.com; s=20150623; h=mime-version:references:in-reply-to:from:date:message-id:subject:to :cc; bh=i/wbd7kVmBBPJN7G0dqTUa19Eq5OOAPD6iXMeuSOucg=; b=gXBgSUESrHwL7LV8R+xrn35H8BHEFrn9545ozEYiD7SjPs5UA6JT+hO3bMA4ICfKsI a/MUMAFk03xViMj1SZRdqMzIiPSlSVAFNUutnOAsjEpTdaV9IN39syVckUdDbtom12Zx +VDqbm1WN+ozyqEqRPw8pDaSZPy38qhWvbB/IdzG3WEKUXc54kk+HZsNVb2phqO8MhwD KgoXkrYiKgpRfcaHeQtMAqx384PXTSpEYVxO2KxXeGTGs2rFT4tkingVt2p+e4Wy6KRs pFxDVDDzSf6SninC7PpuqUsIiaX1eDcrWhn83Fo0io4U+j3EQDkaPyKVN0DmQWwDZs/o 8Jwg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:references:in-reply-to:from:date :message-id:subject:to:cc; bh=i/wbd7kVmBBPJN7G0dqTUa19Eq5OOAPD6iXMeuSOucg=; b=fcbCBQqRR8tCC6em/yw0HyheYOeY9w7WpTXAPHi6OzB0XiSl/fsVhkCL0EiwmMidcH Qu/9xN02vbm3HxAqJc15Li2WDTiiWFWJ4c3i4Pb6ObYgmz8YRe+gFi3RN+2nq9UWZTpY 3LVh5bqAq91/JqP6k4Gm7+eIpLGxQpmb4HGRMUXlEgMBxOknAP13ZRZIug5UccAxW5Ky e1Qex7efZuGogd7n08YgIs/FHP5rXNIckhe4NujnuNS2P3IJP0zRpQG3DAHnxZRjZMOl JT5Ft/p4nPjbX6UrkQvZ0zp3vb/3Ihaz1eOmGlAO6xJo8TcZVCCf7IUl8rWsit8ZYe4Q PtUQ== X-Gm-Message-State: APzg51CHST56g9qZR5imIvIHFvawkmpgbg+Ih7ZvRKGa1fVxUu3h9AE0 3umXg90QaE03KzXNm/80F/1HezQp23SxEtuJMImaxQ== X-Google-Smtp-Source: ANB0VdZ7coN3b8kWx5H0n4cOFwjAv8tD0eCS9Ix1XOldcyAHpTOIFmi9NCmBiCTxRPvGgBZAV0anY4jpUX7rljQjnYY= X-Received: by 2002:a5d:4d82:: with SMTP id b2-v6mr6807953wru.80.1535326685577; Sun, 26 Aug 2018 16:38:05 -0700 (PDT) In-Reply-To: <87o9dovj4z.fsf@netris.org> X-detected-operating-system: by eggs.gnu.org: Genre and OS details not recognized. X-Received-From: 2a00:1450:4864:20::42b X-Content-Filtered-By: Mailman/MimeDel 2.1.21 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:14771 Archived-At: On Sun, Aug 26, 2018 at 6:51 PM Mark H Weaver wrote: > An equality test on hash tables needs to know how to compare the keys > and how to compare the values. There's no way to pass those additional > arguments to 'equal?', so it can't do that job. > Correct. However, it's possible given either SRFI 69 based or R6RS based hash tables to retrieve the key equality predicate. Therefore, a minimal hash-table equality function requires three arguments, the hash tables to be compared (which must have the same key equality predicate) and a value equality predicate. > Hash table implementations typically don't offer an equality test on the > hash tables themselves, SRFI 125, which is part of R7RS-large, does provide such a procedure exactly as described above, except that instead of a predicate you pass a comparator (a record containing a type test, an equality predicate, an optional ordering predicate, and a hash function), a data structure pervasive in R7RS-large and described in SRFI 128. > and I don't recall anyone ever asking for such > an operation before now. I guess that's because in the use case where > hash tables are beneficial -- when the tables are very large -- > comparing them for equality is expensive. > It's O(n), no worse than comparing lists, vectors, or strings for equality. > While hash tables are indispensible for certain use cases, they also > have very significant downsides, and I tend to avoid them whenever > possible. Their most severe downside, in my opinion, is that they are > fundamentally incompatible with a functional programming style. That's true for standard hash tables, such as are provided by Perl, Python, MRI Ruby, Common Lisp, R6RS, etc. But it is not true of hash array mapped tries (HAMTs), which are functional hash tables . They are standard in Haskell, Scala, Erlang, and Rubinius. Although SRFI 146 does not require the use of HAMTs to implement its hashmaps, the sample implementation does in fact provide them. > It's also not possible to efficiently create a new hash table based on > an existing one, but with one or more additional entries. > Again, this is not true of HAMTs. > There can be no sharing of storage between multiple hash tables, as can > be done with lists, association lists, or balanced trees. But not with vectors or strings. (SRFI 135 texts, which are immutable, can and do share.) In addition, lists can only safely share if you restrict yourself by never mutating them. -- John Cowan http://vrici.lojban.org/~cowan cowan@ccil.org It's like if you meet an really old, really rich guy covered in liver spots and breathing with an oxygen tank, and you say, "I want to be rich, too, so I'm going to start walking with a cane and I'm going to act crotchety and I'm going to get liver disease. --Wil Shipley