/ NoParentSelected / Cookbook.HashRecipePresenceOfKeys

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 -- BrianJ - 11 Dec 2006

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

Another alternate implementation:

(define hash-has-key? (let* ([result #t] [fail-thunk (lambda () (set! result #f))]) (lambda (table key) (hash-table-get table key fail-thunk) (begin0 result (set! result #t)))))

CookbookForm | |
---|---|

TopicType: | Recipe |

ParentTopic: | HashRecipes |

TopicOrder: | 030 |

The copyright for certain compilations of material taken from this website is held by the SchematicsEditorsGroup - see ContributorAgreement & LGPL.

Other than such compilations, this material can be redistributed and/or modified under the terms of the GNU Lesser General Public License (LGPL), version 2.1, as published by the Free Software Foundation.

Ideas, requests, problems regarding Schematics Cookbook? Send feedback. / You are Main.guest