You need to know wheter a hash has a particular key, regardless of
whatever value may be associated with a key.
The procedure
hash-table-get returns the value associated
to a key in the hash table. If no value is found it returns
the application of its failure-thunk (the third, optional
argument). So to check if a hash table contains a
particular key we must arrange the failure-thunk to return a
value that cannot possibly be held in the hash table. If
hash-table-get returns this value we know the hash table
does not contain the key.
How can the failure-thunk guarantee that the value it
returns will no be in the hash table? The secret is to use
an uninterned symbol, which is a symbol that is guaranteed
not
eq?,
eqv?, or
equal? to any other symbol. Most
Schemes, including
PltScheme, provide the function
gensym
to generate uninterned symbols.
So we can use the function
hash-has-key? below to test for the presence of a key:
(define hash-has-key?
(let ((symbol (gensym)))
(lambda (table key)
(not (eq? (hash-table-get table key (lambda () symbol)) symbol)))))
An example of its use:
> (define hash (make-hash-table))
> (hash-has-key? hash 'foo)
#f
> (hash-table-put! hash 'foo 1)
> (hash-has-key? hash 'foo)
#t
The definition of
hash-has-key? above uses
IdiomStaticVariables to avoid creating the unique symbol
more than once.
It is important that we use an uninterned symbol to check
for the absence of the key as
PltScheme allows any value,
including
#f and
void, to be stored as the value with a
hash table.
In addition to
gensym,
PltScheme provides the function
string->uninterned-symbol which is like
symbol->string
except the symbol is uninterned. This means that two
symbols created with
string->uninterned-symbol could
display the same but in fact not be
eq?,
eqv?, or
equal?
If
gensym was not available we could take use of the fact
that
eq? returns
#f is its two arguments represent
different values in the store (in other words are allocated
at different addresses) and
list is guaranteed to return a
new allocated list. So we could write
hash-has-key? as:
(define hash-has-key?
(let ((dummy (list '*no-such-element*)))
(lambda (table key)
(not (eq? dummy
(hash-table-get table
key
(lambda () dummy)))))))
There is a company called Gensym. There primary product is
a Lisp based Expert System shell. Now you know where their
name comes from!
--
KarlaRamirez - 19 May 2004
--
AshInn
--
NoelWelsh - 14 Sep 2004
--
JensAxelSoegaard - 15 Sep 2004
I don't understand the comment:
"However this is not guaranteed to work; it is possible that an
advanced Scheme compiler could allocate two identical lists to the same object.".
A call to
list is guaranteed by R5RS to return a
newly allocated list.
The
eq? test for object identity should work everywhere.
--
JensAxelSoegaard - 14 Sep 2004
You are correct. However
eq? is not guaranteed to return
#f in, for example,
(eq? (list 1 2) (list 1 2)). I shall modify the recipe accordingly. Thanks. --
NoelWelsh - 15 Sep 2004
Are you sure? The entry on
eq? says that one should look under
eqv?. And there it says:
The eqv? procedure returns #t if:
* obj1 and obj2 are pairs, vectors, or strings that denote the same
locations in the store (section 3.4).
The eqv? procedure returns #f if:
* obj1 and obj2 are pairs, vectors, or strings that denote distinct locations.
The example
(eq? '(a) '(a)) ==> unspecified illustrates that literals can be
coalesced by the compiler, but in this case we are making new pairs.
--
JensAxelSoegaard - 15 Sep 2004
I have been schooled! :-)
--
NoelWelsh
Alternative implementations:
(define hash-has-key?
(let ([secret (let-struct secret ()
(make-secret))])
(lambda (table key)
(not (eq? (hash-table-get table key (lambda () secret)) secret)))))
or an arguably more readable solution:
(define (hash-has-key? table key)
(with-handlers ([exn:fail:contract? (lambda (exn) #f)])
(hash-table-get table key)
#t))
--
DaveHerman - 26 Feb 2006
RSS