Scheme Request for Implementation 250,
“Insertion-ordered hash tables”,
by John Cowan,
is now available for discussion.

Its draft and an archive of the ongoing discussion are available at https://srfi.schemers.org/srfi-250/.

You can join the discussion of the draft by filling out the subscription form on that page.

You can contribute a message to the discussion by sending it to srfi-250@srfi.schemers.org.

Here’s the abstract:

This SRFI defines an interface to hash tables, which are widely recognized as a fundamental data structure for a wide variety of applications. A hash table is a data structure that:

  • Is disjoint from all other types.
  • Provides a mapping from objects known as keys to corresponding objects known as values.
    • Keys may be any Scheme objects in some kinds of hash tables, but are restricted in other kinds.
    • Values may be any Scheme objects.
  • Provides an equality predicate which defines when a proposed key is the same as an existing key. No table may contain more than one value for a given key.
  • Provides a hash function which maps a candidate key into a non-negative exact integer.
  • Supports mutation as the primary means of setting the contents of a table.
  • Provides key lookup and destructive update in (expected) amortized constant time, provided that a satisfactory hash function is available.
  • Does not guarantee that whole-table operations work in the presence of concurrent mutation of the whole hash table. (Values may be safely mutated.)

Unlike the hash tables of SRFI 125, which is the direct ancestor of this specification, the hash tables described here are ordered by insertion: that is, associations inserted earlier in the history of the hash table appear earlier in the ordering. Advances in the implementations of hash tables, as provided by C++, Python, JavaScript, etc., make the provision of this new facility practical. As a result, the hash tables of this SRFI do not interoperate with the hash tables of SRFI 125, SRFI 126, or existing R6RS implementations.

​

Regards,

​

SRFI Editor