More notes while implementing:

alist->hash-table should specify that the order of associations from the alist is maintained. (Forward or reverse order? I chose forward order for the sample impl.)

hash-table=? should take a comparison procedure, not a comparator. It should also arguably be called hash-table= following the example of list= from SRFI 1.

hash-table-pop! should delete the last i.e. most recently added association (which is cheaper to do than any other deletion), not the first (which adds an unnecessary tombstone to the hash table)

hash-table-map takes a comparator argument as though it would create a table with new keys as well as new values. As specified, it creates a mapping with the same set of keys so the comparator from the original hash table should suffice, unless I misunderstand the purpose of this procedure. (hash-table-map!, the destructive variant, already gets this right)

hash-table-map->list seems of questionable value given the existence of hash-table-fold and hash-table-fold-right

hash-table-empty-copy returns a new, empty hash table with the ‘same properties’ as another hash table. Does this include assuming it will contain roughly the same number of entries as the original hash table, i.e. the k for make-hash-table is roughly the hash-table-size of the original?

hash-table-size is listed twice in the ‘The whole hash table’ section of the index

In general, error cases need to be a lot better specified; I will send a follow-up mail once I have started identifying a list of places where these are currently problematic.

I have just posted a new version of the sample implementation which is much more complete and functional; I think the broken cases in the old code which I was concerned about have been taken care of.
<https://gitlab.com/dpk/presrfis/-/tree/b0df09903bf40a5aecb41b209020c7f67bec3213/srfi-125-ordered>

The following procedures are still missing:
• hash-table-mutable? and hash-table-copy
• hash-table-empty-copy
• hash-table-comparator
• hash-table-pop!
• hash-table-key-vector, hash-table-value-vector, hash-table-entry-vectors
• hash-table-map, hash-table-map!, hash-table-map->list
Attentive readers will note that this is exactly the set of procedures I have concerns and doubts about.

hash-table=? uses a comparison procedure and not a comparator, as suggested above.

Also exported is a hash-table-fold-right procedure.

Provided, and used internally but not yet exported, is an example of the cursor-based iteration protocol I suggested:
<https://gitlab.com/dpk/presrfis/-/blob/b0df09903bf40a5aecb41b209020c7f67bec3213/srfi-125-ordered/srfi-125-ordered.scm#L376-408>
You can iterate in left-to-right or right-to-left order, or you can mix scanning left and right as you please. The only constraint is that any insertion or deletion during iteration will invalidate the cursor; continuing to use it will lead to undefined behaviour. (hash-table-prune! does delete during a cursor iteration; but do as I say, not as I do.)
Examples of its use are plentiful, especially in the code immediately following the implementation of cursors.
The cursor in this impl is an integer; while I expect this is what most implementations will use, what type it is should be unspecified, I think.

The implementation needs an extensive test suite: I would like to put it through some hard stress tests. Because of the technique used, it should be one of the more memory efficient Scheme hash table implementations out there, though I make no guarantee about its performance or correctness yet.

Daphne