[racket-dev] Iteration and Mutation on dictionaries

From: Eric Dobson (eric.n.dobson at gmail.com)
Date: Wed Jul 18 00:05:56 EDT 2012

Dictionaries provide an iteration interface with the primitive operations:

dict-iterate-first: Dict -> (U #f Iterator)
dict-iterate-next: Dict Iterator -> (U #f Iterator)
dict-iterate-key: Dict Iterator -> Key
dict-iterate-value: Dict Iterator -> Value

This interface matches the hash interface and allows a user to iterate
over all entries and view them. It does not provide support for

Both the hash and dict have the same disclaimer about mutation during iteration:
For a mutable hash, this index is guaranteed to refer to the first
item only as long as no items are added to or removed from hash.
For a mutable hash, the result index is guaranteed to refer to its
item only as long as no items are added to or removed from hash.

Note that there are no disclaimers about what happens if you mutate
the value associated with a key already in a hash, and thus I assume
it is ok to do this. Hashes support this but not all dictionaries do.
This is because the only way to mutate a key is to use dict-set! which
makes it hard to keep the index valid.

;Broken program using free identifier tables
#lang racket
(require syntax/id-table)

(define a #'a)
(define tbl (make-free-id-table))
(free-id-table-set! tbl a 2)
(define index (free-id-table-iterate-first tbl))
(free-id-table-set! tbl (free-id-table-iterate-key tbl index) 3)
(free-id-table-iterate-next tbl index)

The documentation needs to be clarified to whether this kind of
mutation is required to be supported or not. I can see it going either

One problem with forcing it to be required is that the only way to
mutate a dictionary is through the dict-set! function, which is not
related to the current iteration. A dict-iterate-set! function would
alleviate this and allow any necessary updating of the index, but it
has the issue that any idiom that hides away the iterator object could
not use it, i.e. for loops, dict-for-each.

dict-iterate-set!: Dict Iterator Value -> Void

What should the requirement be?

Posted on the dev mailing list.