[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: hash tables

From: Alex Shinn
Subject: Re: hash tables
Date: 30 Jun 2001 11:36:13 -0400
User-agent: Gnus/5.09 (Gnus v5.9.0) Emacs/21.0.103

>>>>> "Thomas" == Thomas Bushnell, BSG <address@hidden> writes:

    Thomas> Importantly, how do I create a hash table?  What is the
    Thomas> tester function to tell me if a given object is a hash
    Thomas> table?

Unlike most other languages, Scheme doesn't have an atomic hash type.
It's implemented as a vector of alists.  So you tend to write programs
in Guile knowing where you're expecting and passing hashes.  This
presents a problem when writing translators for other languages like
Python and Perl, which will often write functions which accept either
a hash or a list (for instance), and need to know what type the
argument is.  Even a most thorough attempt at a hash? function:

(define hash?
  (letrec ((alist? (lambda (lst)
                     (or (null? lst)
                         (and (pair? lst)
                              (let ((first (car lst)))
                                (and (pair? first)
                                     (not (pair? (cdr first?)))))
                              (alist? (cdr lst)))))))
    (lambda (obj)
      (and (vector? obj)
            (lambda (false)
               (lambda (elt) (if (not (alist? elt)) (false #f)))

fails when someone simply wants an array of alists, and is not
considering them a hash.

One approach to solving this is that unlike most Unix scripting
languages, Scheme distinguishes between vectors and lists.  So in your
Python translator, you're probably representing tuples and (Python)
lists as one of these, leaving the other type free to uniquely
identify hashes.  Then you can use the simple

(define (hash? obj)
  (and (vector? obj)
       (let ((first (vector-ref obj 0)))
         (or (null? first) (pair? first)))))

to test for dictionaries.

Unfortunately this leaves out potential optimizations for knowing when
a Python tuple/list would be better implemented as a vector or list
(an approach which could in many cases make the Guile translation run
much faster than the original Python).

Another approach, which more closely matches Python's dictionaries, is
to define a hash record (or class), and give it some meta-information.
Such as the ahash (automatically-resizing hash):

(make-record-type "ahash" ' (table size elements))

which could keep track of the current size and number of elements in
the table and perform a re-hash when the ratio reaches a certain
limit.  The Perl version of this might also include a next slot,
holding a continuation referencing a hash-fold loop for use in Perl's

Alex Shinn <address@hidden>
Lisper, Smalltalker, and all around poor speaker

reply via email to

[Prev in Thread] Current Thread [Next in Thread]