Re: Scheme style auto-resizing hashtable (fwd)

[Tel <telford@eng.uts.edu.au>]

> On Sat, 31 Oct 1998, Ian Bicking sagely murmured:
> 
> > A rich set of datatypes could also be a powerful addition.  Make
> > dictionaries, not hash tables -- mostly that's just a matter of
> > terminology, but I think it's important.  As a programmer, I don't
> > care about the fact that hash tables use hashing, I care about the
> > fact that hash tables are a collection of values indexed by keys.
> 
> and
> 
> On Sat, 31 Oct 1998, Maciej Stachowiak hummed this tune:
> 
> > ... Scheme has a tradition of using meaningful identifiers and uniform
> > surface syntax ... 
> 
> <taken slightly out of context>
> 
> so what do I have here?  "dictionary" and "meaningful identifiers". hmm.
> I also considered using "hash-table" (used by CL, so I just said "No."),
> "assoc-array" (one letter longer than "dictionary", you lose), and even
> "auto-hash" (where did that come from?).

Hash tables don't maintain order of the keys. Dictionaries are in
alphabetical order (last time I looked at a paper one was a while back).
You have to be a little bit careful when freely associating concepts.

The main competitors to hash tables are the various balanced trees
which do maintain order of the keys.

``uniform surface syntax'' is nice but it won't turn a hash table into
a tree or vice versa. I like the idea of using the same operations on
both trees and hash tables, maybe even similar sounding function names
but I don't like the idea of pretending that they are really all the same
thing.

On this note, some common nomenclature used by programmers to cover such
well established concepts would be nice but probably isn't likely soon.

> 	dictionary-add!
> 	dictionary-lookup
> 	dictionary-remove!
> 	dictionary->pairs
> 	dictionary->keys
> 	dictionary->values

I'm currently using (for the plain B-tree):
   index-insert!     -- adds an item or replaces existing item
   index-find        -- returns an item or #f if not found
   index-remove!     -- removes an item or do nothing if not found
   index-list        -- return a sorted list of items between given bounds
   index-length      -- count items

NB: items are keys or key/pairs or whatever, you supply the comparison
function, I just keep them sorted. These structures are quite flexible.

(for the double B-tree that does poor-man's relational stuff):
   table-insert!          -- Add an ID/attribute/value tuple
   table-get-data         -- like find but inconsistently named
   table-remove!          -- delete tuples
   table-list-ids         -- return a sorted list of matching ids
   table-list-attributes  -- return a sorted list of attributes
   table-length           -- number of tuples stored
   table-biggest          -- largest ID number stored
   table-get-next         -- lookup the next item after given value
   table-get-prev         -- lookup the previous item before given value

NB: here attributes are symbols, IDs are integers, you get more functions
but less flexibility. The value can be anything you like but you can't
guarantee sorting unless it's a string, number or symbol (other stuff will
store OK but not sort). You can't define your own comparison function.

For what it's worth, I like the sound of ``index-lookup'' and ``table-lookup''
so I'll switch those over. Since the -> is used extensively in guile for
symbols that convert between types, I'll change over to these names:

   index-lookup
   table-lookup
   table-next
   table-prev
   index->list
   table->ids
   table->attributes

That should be reasonably standard... I might take a while to change these
over.

Don't think that there is any precedent on ``add!'' vs ``insert!'' but
I personally prefer insert... the existing hash tables use ``hash-set!''
and ``hash-remove!''. I don't like the use of set! in this way because
the normal set! won't create a new binding (as the SIOD discussion is
pointing out) but ``hash-set!'' will create an entry in the hash table
(and to put icing on the cake, hash-set! returns the newly set value).
I don't like inconsistent behaviour being defined for a similar sounding
name.

> 	dictionary-map
> 	dictionary-foreach
> 	dictionary-copy!

I've been meaning to get around to writing something equivalent to these.

> 	dictionary-clear!

My table-remove! and index-remove! have optional arguments, if you
only supply one argument (the table) they delete everything, as you
supply more args they get more selective. I'm still wondering if this
use for optional arguments is clever or just confusing.

> 	dictionary-update!

what does this do?

	- Tel