Iteration in JavaScript
In JavaScript, there are basically two kinds of object iteration:
All objects support property enumeration:
for (var propName in someObject) { var value = someObject[propName]; }Some objects support the "Array protocol":
for (var i=0; i<someObject.length; i++) { var value = someObject[i]; }
These both suck.
Property enumeration is only really useful for debugging, since chances are the objects will have a lot of properties that you do not want them to have, and there is no standard way to have properties that are hidden from enumeration.
Array protocol enumeration sucks because:
- Writing for loops is so "C"
- Not every object that supports the "array protocol" is actually an array, so the "higher order" methods to manipulate the array such as Array.prototype.slice aren't going to be available everywhere. DOM NodeList objects and the special arguments array are particularly common examples of these array-like objects.
Fortunately, this doesn't stop you from writing your own iteration protocol. Here is an example of a JavaScript iterator in the style of Python's PEP 234 - Iterators:
StopIteration = function () {};
StopIteration.prototype = new Error();
StopIteration.name = 'StopIteration';
StopIteration.message = 'StopIteration';
arrayLikeIterator = function (arrayLike) {
var i = 0;
return {
'next': function () {
if (i >= arrayLike.length) {
throw StopIteration;
}
return arrayLike[i++];
}
};
};
var countToFive = arrayIterator([1, 2, 3, 4, 5]);
try {
while (true) {
var item = countToFive.next();
// do something with item here
}
} catch (e) {
if (e != StopIteration) {
throw e;
}
// pass
}
As you can see, it's not pleasant to work directly in this style. We've actually made things worse, but we've gained two important things in the process:
The concept of an iterator separate from the object being iterated
This separation is very important. When you have iterators that are separate from the object being iterated, you can do crazy things like iterate in reverse without creating a new array, define an iteration over objects that aren't normally iterable (particularly important since JavaScript doesn't have operator overloading), or define an alternative kind of iteration over something (such as walking a tree in pre-order, or iterating over every even item in an array, etc.).
Iterators that don't need to know about length or index
This basically means that iterators are lazy. You can define infinite iterators, filter chains, etc. This can be extremely important when doing some kinds of programming in a functional style.
Unfortunately, as-is, we've made things too hard to use liberally. That's when you bring in the sledgehammers, er, functions that make this less painful. Basically, these fall into three groups:
- Functions that create iterators from an iterable object (not necessarily an iterator)
- Functions that transform an iterator into some kind of primitive object
- Functions that transform one iterator into another iterator
The most important function in the first group (following the Pythonisms) is iter(iterable[, sentinel]). iter's job is to determine if iterable is already an iterator, or match it up with the appropriate iterator factory to make one out of it. The optional sentinel argument is just an additional convenience (which I carried over into MochiKit's iterators).
Determining whether an iterable is already an iterator is trivial, simply check typeof(iterable.next) == 'function'. However, if it's not, then it has to do some grunt work. In Python style, our implementation of iter allows an object to implement an iter() method (like Python's __iter__) which returns an iterable. However, since we don't do any built-in object prototype hacking, we've also allowed for adapters (using the same methodology that's in Comparison and Adaptation in JavaScript) to be defined.
Just like registering comparators, registering an iterable is a matter of writing a function that detects the kind of object you want to iterate (check), and another function (wrap) that is the iterator factory for that kind of object. Note that we recommend adapting on how objects act, not their type. Since JavaScript's type system is sufficiently weak, adapting based on type is a non-starter. For example, many of the objects you may run across in JavaScript will behave similarly to an Array, but aren't quite. The DOM's NodeList is a particularly ugly example. It has a length property, and it supports the [``same syntax]`` as Arrays do, but they aren't Arrays. The arguments special object is similarly Array-like, but isn't a real Array.
In order to work around this, Duck Typing is usually the right answer. Instead of checking the constructor, instanceof, etc., you simply introspect the object to see if it looks like a duck, and quacks like one. For example, the registration for turning array-like objects into iterables looks like this:
isArrayLike = function (obj) {
// working around blog-bug with "and" due to ampersands
return !(typeof(obj) != 'object' || typeof(obj.length) != 'number');
}
arrayLikeIterator = function (arrayLike) {
var i = 0;
return {
'next': function () {
if (i >= arrayLike.length) {
throw StopIteration;
}
return arrayLike[i++];
}
};
};
registerIteratorFactory(
// name of the adapter
"arrayLike",
// check function
isArrayLike,
// wrap function
arrayLikeIterator
);
With this, given a suitable definition of iter, we can write iter(someIterable) without having to worry so much about what someIterable is.
The second group of functions let you do the inverse: take something iterable, and make it primitive again. There are two basic examples of this, reduce and list. The implementations are as follows (the documentation is better in MochiKit, I shortened it for brevity):
list = function (iterable) {
/***
Create an array from an iterable.
***/
// fast-path if they passed in an Array already
if (typeof(iterable.slice) == 'function') {
return iterable.slice();
}
// it's good to do this for convenience,
// it's cheap if it's already iterable
iterable = iter(iterable);
var rval = [];
try {
while (true) {
rval.push(iterable.next());
}
} catch (e) {
if (e != StopIteration) {
throw e;
}
}
return rval;
}
reduce = function (func, iterable, /* optional */initial) {
/***
Create a value from an iterable by applying a function of two arguments
cumulatively to all of its elements.
***/
iterable = iter(iterable);
if (arguments.length < 3) {
try {
initial = iterable.next();
} catch (e) {
if (e == StopIteration) {
e = new TypeError("reduce() of empty sequence with no initial value");
}
throw e;
}
}
try {
while (true) {
initial = func(initial, iterable.next());
}
} catch (e) {
if (e != StopIteration) {
throw e;
}
}
return initial;
}
The last group of functions completes the toolkit by allowing you to transform an iterator into another iterator. These functions are imap, ifilter, ifilterfalse, etc. Effectively what these let you do is compose something a bit more declarative. For example:
// reduce(operator.add, sequence, 0) is also sum(sequence) in MochiKit
sumOfAllObjectsGreaterThanTen = reduce(operator.add,
// all objects that are greater than 10 (10 is less than them)
ifilter(partial(operator.lt, 10),
// skip all objects that are undefined or null
ifilterfalse(isUndefinedOrNull, allObjects)
),
// use 0 as the initial value, i.e. (((0 + p0) + p1) + p2 ...)
0
);
The equivalent in idiomatic JavaScript looks more like this:
var sumOfAllObjectsGreaterThanTen = 0;
for (var i = 0; i < allObjects.length; i++) {
var o = allObjects[i];
// working around blog-bug with "and" due to ampersands
if (!(isUndefinedOrNull(o) || o <= 10)) {
sumOfAllObjectsGreaterThanTen += o;
}
}
Granted, this particular example doesn't give you much. However, if you're familiar with the functional style of programming you can easily see where this goes. Unfortunately, I'm not really in the mindset to teach at the moment, so if you don't get it yet, you're not going to get it from me (today).
- UPDATE:
- Check out the full implementation of this in MochiKit!