Re: Comparing two hash tables for equality?

[John Cowan <cowan@ccil.org>]

On Sun, Aug 26, 2018 at 6:51 PM Mark H Weaver <mhw@netris.org> 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
<https://en.wikipedia.org/wiki/Hash_array_mapped_trie>.
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