Re: a short article about equality in Lisp (for beginners)

From: Rob Warnock (rpw3_at_rpw3.org)
Date: 08/08/04 

Date: Sat, 07 Aug 2004 19:49:43 -0500

Robert Strandh <strandh@labri.fr> wrote:
+---------------
| Perhaps this is the moment to submit my modest proposal for a new
| equality predicate + hash function.
...
| The standard specifies only four types of hash tables possible,
| according to whether the equality function is eq, eql, equal or equalp.
+---------------

Are you familiar with EXTENSIONS:DEFINE-HASH-TABLE-TEST in CMUCL?
(...and presumably in SBCL as well?)

    The hash-tables defined by Common Lisp have limited utility
    because they are limited to testing their keys using the equality
    predicates provided by (pre-CLOS) Common Lisp. CMUCL overcomes
    this limitation by allowing its users to specify new hash table
    tests and hashing methods. The hashing method must also be
    specified, since the compiler is unable to determine a good
    hashing function for an arbitrary equality (equivalence) predicate.

    [Function]
    define-hash-table-test hash-table-test-name test-function hash-function

    The hash-table-test-name must be a symbol. The test-function takes
    two objects and returns true iff they are the same. The hash-function
    takes one object and returns two values: the (positive fixnum) hash
    value and true if the hashing depends on pointer values and will
    have to be redone if the object moves.

    To create a hash-table using this new ``test''
    (really, a test/hash-function pair), use
    (MAKE-HASH-TABLE :TEST hash-table-test-name ...).

I believe that this is a simpler protocol that does not require
introducing the notion of "situations" or the generic functions
they depend on.

As usual with CMUCL/SBCL, the code is available for perusal and/or
re-use in other implementations.

-Rob

-----
Rob Warnock <rpw3@rpw3.org>
627 26th Avenue <URL:http://rpw3.org/>
San Mateo, CA 94403 (650)572-2607

Relevant Pages

  • Re: A newbie needs insight into some Ruby proboems...
    ... My first problem is that I have a class and I want to define some operators, like equality. ... def initialize ... What I'm trying to do is automate iterating over my member variables performing a cumulative equality test. ... I have to define something like a "hash" method but I don't know what hash is supposed to return, exactly, for things like Set and Hash to work. ...
    (comp.lang.ruby)
  • Re: a short article about equality in Lisp (for beginners)
    ... equality predicate + hash function. ... The standard specifies only four types of hash tables possible, ... for hash and eqv. ... This class is a subclass of builtin-key-situation. ...
    (comp.lang.lisp)
  • Re: indexes vs sorted files in range and equality search
    ... Equality search time: D.log2 ... the cost of the index searching depends on the depth ... values that hash to the same value (not all of which need be the value ... best, then we have sorted files, then unclustered tree indexes ...
    (comp.databases.theory)
  • Re: Hash function for float.
    ... A hash is used to generate a map. ... compare floating-point values for equality. ... Figuring out the NaNs, and Infs are platform specific, though C99 ...
    (comp.lang.c)
  • Re: in praise of tabling
    ... Well, tabling is, to a first order approximation, Prolog-speak for ... Whenever a new result for the predicate is computed, ... result is recorded in the hash table. ... upon whether the cost of recomputation outweighs the cost of checking ...
    (comp.lang.prolog)