Collection Alignment

Some operations on collections, such as mapping, are defined to allow the use of more than a single collection. The presence of potentially "unstable" collections, i.e., collections for which two iterations may produce values in different orders even though the collection remains unchanged, can create problems for multi-collection operations unless special care is taken. That is, if iteration is effectively performed in random order in the general case, then naively performing parallel iterations over two different collections would randomly pair values from the two collections, which would presumably have no meaning.

To prevent such random pairing, when operating on more than one collection, map, do, etc. must, in general, "align" the collections, by first computing the intersection of the collections' key sequences and then using the random-access operations (element and element-setter) to operate on the collections themselves. Collection alignment is only possible for collections whose key-test is identical, i.e. key-test(c1) == key-test(c2). Otherwise, an error is signalled. As a concrete example, here is the two-collection case for do:

define method do2 (f :: <function>, c1 :: <collection>, 
                   c2 :: <collection>)
  let keys = intersection(key-sequence(c1), key-sequence(c2));
  let (init, limit, next, end?, key, elt)
	= forward-iteration-protocol(keys);
  for (state = init then next(keys, state),
       until end?(keys, state, limit))
    let key = elt(keys, state);
    f(c1[key], c2[key]);
  end for;
end method do2;

Note that this definition has the potential for extreme inefficiency, because of its dependence on element and the potential loops implied by the calls to key-sequence.

An important special case of this problem is that of iterating over multiple sequences. In this case, the intersection of key sequences is clearly the non-negative integers up to the length of the shortest sequence. Further, unlike collections in general, sequences are required to exhibit stability, so no explicit computation of key sequences need be made. Instead, it is correct (and much more efficient) simply to iterate until one or more of the sequences is exhausted. Here is a concrete example for do2:

define method do2 (f :: <function>, c1 :: <sequence>, c2 :: <sequence>)
  let (init1, limit1, next1, end1?, key1, elt1)
		= forward-iteration-protocol(c1);
  let (init2, limit2, next2, end2?, key2, elt2)
		= forward-iteration-protocol(c2);
  for (state1 = init1 then next1(c1, state1),
       state2 = init2 then next2(c2, state2),
       until (end1?(c1, state1, limit1) | 
              end2?(c2, state2, limit2)))
    f(elt1(c1, state1), elt2(c2, state2));
  end for;
end method do2;

Most cases of iteration over more than a single collection will be iterations over sequences, rather than over arbitrary collections. Since this case is efficient, the requirement for alignment is probably not burdensome in practice.

Any iteration operations that modify a collection must also include the key sequence of the target collection during "alignment" of the collection arguments. For example, consider these definitions for a simplified map-into function:

define method map-into1 (target :: <mutable-collection>,
                         f :: <function>,
                         source :: <collection>)
  let keys = intersection(key-sequence(target), 
                          key-sequence(source));
  let (init, limit, next, end?, key, elt)
	= forward-iteration-protocol(keys);
  for (state = init then next(keys, state),
       until end?(keys, state, limit))
    let key = elt(keys, state);
    target[key] := f(source[key]);
  end for;
end method map-into1;

define method map-into1 (target :: <mutable-sequence>,
	         f :: <function>,
	         source :: <sequence>)
  let (init1, limit1, next1, end1?, key1, elt1, setter)
	= forward-iteration-protocol(target);
  let (init2, limit2, next2, end2?, key2, elt2)
	= forward-iteration-protocol(source);
  for (state1 = init1 then next1(target, state1),
       state2 = init2 then next2(source, state2),
       until (end1?(target, state1, limit1) |
              end2?(source, state2, limit2)))
    setter(target, state1, f(elt2(source, state2)));
  end for;
end method map-into1;