s c h e m a t i c s : c o o k b o o k

/ NoParentSelected / Cookbook.HashRecipePresenceOfKeys

This Web

TOC (with recipes)

Other Webs



Schematics Home
Sourceforge Page
Original Cookbook

Scheme Links

Scheme FAQ
Scheme Cross Reference
Scheme48 SCM
MIT Scheme scsh
JScheme Kawa
Chicken Guile
Bigloo Tiny
Gambit LispMe

Lambda the Ultimate

Testing for the Presence of a Key in a Hash


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:

500 Can't connect to (connect: Connection refused)

An example of its use:

500 Can't connect to (connect: Connection refused)


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:

500 Can't connect to (connect: Connection refused)

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

Comments about this recipe

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:

500 Can't connect to (connect: Connection refused)

or an arguably more readable solution:

500 Can't connect to (connect: Connection refused)

-- DaveHerman - 26 Feb 2006

Another alternate implementation:

500 Can't connect to (connect: Connection refused)

-- BrianJ - 11 Dec 2006

TopicType: Recipe
ParentTopic: HashRecipes
TopicOrder: 030

Copyright © 2004 by the contributing authors. All material on the Schematics Cookbook web site is the property of the contributing authors.
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