Javascript instant iterators, at last

After yesterday’s entry, Bob Ippolito wrote in the comments of David Flanagan’s piece on Another Useful JavaScript Closure that the method I proposed was suboptimal:

Neither the C++ style iterators or the sentinel iterators are appropriate for JavaScript.

The C++ style iterator requires too many function calls. You need to do 2N function calls to iterate over a sequence of N length. Dumb, and slow.

The sentinel style iterator is too fragile. If you iterate over something that happens to contain StopIteration (i.e. values(MochiKit.Iter)), then you’re screwed. It’ll stop at a random place and you won’t know why. Also, you’ll be doing N additional comparisons, though comparisons are typically fast so this probably doesn’t really matter.

There is some number N where throwing 1 exception is more expensive than N comparisons… but for larger N, exceptions get more and more sensible. Especially for deep filter stacks.

In other words, exception based iterators are The Only Way To Do It. In general, modeling something after Python is the Right Way, and this is certainly one of those cases. If you don’t agree, you just haven’t thought about it enough :)

Well, I happen to have thought about it, but I reached a different conclusion anyhow. The solution I’m about to present was inspired by thinking how I’d do this in Perl.

It is funny how problems in distinguishing “no result found” from “an undefined element which is part of the data” always evaporate once you stop thinking in terms of “what value do I return” and start thinking of “what is the set of elements I return.” Lists are always the answer: lists have a cardinality, and when it is zero, that is cleanly distinguishable from a list with cardinality one, regardless of the actual value of the element of that list. In this case, because Javascript has only arrays, and an empty array still evaluates to true in boolean contexts, I’ll return either an array with one element or null, so that the iterator can be used in a conditional.

function iterate( iterable ) {
  var i = -1;
  return function() {
    return ++i < iterable.length ? [ iterable[ i ] ] : null;
  };
}

Carter’s compass. Yet more code deleted.

This time, the example code needs updating to accomodate the change:

for( var sheet, next = iterate( document.styleSheets ); sheet = next(); )
  if( sheet[0].href )
    do_something( sheet[0] );

Admittedly, the redundant, invariant [0] indexing that is now necessary looks a little weird. But hey, the alternative is having to bring out the try { } catch( e ) { } nuke for regular control flow in every single loop using an iterator, and if that’s not really ugly, I don’t know what is.

In Perl, or generally speaking in a language with true lists, this idiom would in fact be an entirely natural expression for this task: you’d just return an empty list when the iterator is depleted, and an empty list is false when speaking boolean.

function iterate( iterable ) {
  var i = -1, a = [];
  return function() {
    return ++i < iterable.length ? ( a[ 0 ] = iterable[ i ], a ) : null;
  };
}