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

/ NoParentSelected / Cookbook.HashRecipePresenceOfKeys

This Web


WebHome 
WebChanges 
TOC (with recipes)
NewRecipe 
WebTopicList 
WebStatistics 

Other Webs


Chicken
Cookbook
Erlang
Know
Main
Plugins
Sandbox
Scm
TWiki  

Schematics


Schematics Home
Sourceforge Page
SchemeWiki.org
Original Cookbook
RSS

Scheme Links


Schemers.org
Scheme FAQ
R5RS
SRFIs
Scheme Cross Reference
PLT Scheme SISC
Scheme48 SCM
MIT Scheme scsh
JScheme Kawa
Chicken Guile
Bigloo Tiny
Gambit LispMe
GaucheChez

Lambda the Ultimate
TWiki.org

Testing for the Presence of a Key in a Hash

Problem

You need to know wheter a hash has a particular key, regardless of whatever value may be associated with a key.

Solution

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

Discussion

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!


Contributors

-- 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:

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

CookbookForm
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