Tue May 5 10:22:50 CEST 2009

Immutable hash tables

From the PLT Scheme reference manual:

3.13 Hash Tables

  "A hash table (or simply hash) maps each of its keys to a single
  value. For a given hash table, keys are equivalent via equal?, eqv?,
  or eq?, and keys are retained either strongly or weakly (see Weak
  Boxes). A hash table is also either mutable or immutable; immutable
  tables support constant-time functional update.

I didn't know about the immutable constant-time functional update.
That's pretty cool!  I wonder how it is implemented.

Red-black trees [1] [2].

[1] http://groups.google.com/group/plt-scheme/browse_thread/thread/d6da66d2bb3855e6/445f23588930fc90?lnk=raot
[2] http://en.wikipedia.org/wiki/Red-black_tree