[racket-dev] Iteration and Mutation on dictionaries

On 07/18/2012 12:05 AM, Eric Dobson wrote:
> 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
> mutation.
>
> Both the hash and dict have the same disclaimer about mutation during iteration:
> hash-iterate-first:
> 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.
> hash-iterate-next:
> 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.
>
> ; EXAMPLE
> ;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
> way.
>
> 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?

FWIW, I've fixed id-tables so that their iterators are not invalidated 
by mutation of existing keys. My inclination would be to require this 
behavior for all dictionaries, not to add another operation to the 
interface.

Ryan