Iteration Stability and Natural Order

A collection is stable under iteration if any two iterations over the collection are guaranteed to produce the same values in the same order (unless, of course, the collection has been modified). A collection that is not stable under iteration is said to be unstable under iteration.

Collections in general are not required to be stable under iteration, although several important subclasses are so required. In particular, sequences are required to be stable under iteration.

The order in which elements (and keys) are enumerated by the iteration protocol for a particular iteration is known as the "natural order" for that iteration over the collection. If a collection is stable under iteration, then every iteration over that collection will have the same natural order, and we may speak of the natural order of the collection itself. Most of the higher order operations are required to operate in "natural order," usually for the purpose of understanding interactions among side effects.

Collection Keys All collections in Dylan are "keyed" collections, i.e., all collections can be viewed abstractly as partial functions that take keys to elements. (This choice precludes pure sets from being considered collections, although it is straightforward simply to ignore the keys for a collection and consider it simply as a set of elements.) The element function implements this partial mapping of keys to elements. In addition, it is possible to obtain all the keys for a given collection, formed into a sequence collection.

element   collection key #key default  =>  element	[Generic Function]

element returns the element associated with key in collection. If no element is associated with key, then the behavior of element depends on whether it was called with a default argument: if a default argument was passed, its value is returned; otherwise, an error is signaled.

All collections are required to implement element.

key-sequence   collection  =>  keys	[Generic Function]

key-sequence returns a sequence containing the keys of collection. Although elements may be duplicated in a collection, keys, by their nature, must be unique; two different elements in a collection may not share a common key, even though distinct keys may yield identical elements.

The order in which the keys from collection appear in the key sequence is unspecified if collection is unstable under iteration. In particular, different calls to key-sequence with the same argument may yield differently ordered key sequences. If collection is stable under iteration, however, the resulting sequence of keys will be in the natural order for collection. Iterating through a collection often involves examining keys as well as elements. To allow some freedom of implementation, the protocol recognizes two strategies for associating keys with states of iteration: explicitly or implicitly. The distinction between these strategies gives rise to two covering subclasses of <collection>. Every concrete subclass of <collection> must also be a subclass of either <explicit-key-collection> or <sequence> (or both):

<explicit-key-collection>	[Abstract Class]

<explicit-key-collection> is the class of all collections that are not sequences.

<sequence>	[Abstract Class]

<sequence> is a subclass of <collection> whose keys are consecutive integers ranging from zero up to (but not including) the size of the sequence.

Sequences must be stable under iteration, and the iteration order must match the order of keys. Thus, the key associated with a sequence's iteration state can be determined by keeping a counter in parallel with the iteration state, as in the next example. Since every collection must be a sequence or an explicit-key-collection, it is always possible to keep track of keys during an iteration by defining appropriate methods on <sequence> and <explicit-key-collection>.[24] For example, consider these two methods for a function that applies a function f to each key-and-element pair in a collection. The method on <explicit-key-collection> uses the current-key function returned by forward-iteration-protocol; the method on <sequence> keeps a counter "alongside" the state during the iteration:

define method do-with-keys (f :: <function>, 
                            c :: <explicit-key-collection>)
  let (init, limit, next, end?, key, elt) = 
               forward-iteration-protocol(c);
  for (state = init then next(c, state),
	    until end?(c, state, limit))
     f(key(c, state), elt(c, state));
  end for;
end method do-with-keys;

define method do-with-keys (f :: <function>, c :: <sequence>)
  let (init, limit, next, end?, key, elt) = 
                forward-iteration-protocol(c);
  for (key :: <integer> from 0,
	    state = init then next(c, state),
	    until end?(c, state, limit))
	 f(key, elt(c, state));
  end for;
end method do-with-keys;