12th October 2009
I was writing simple JavaScript the other day and, to make sure that my code works in all browsers, instead of using Array.map, I wrote a trivial map implementation myself. Then, just out of curiosity, I wrote two more implementations and posted them on StackOverflow to see what other fellow programmers think.
Here’s my original implementation, pretty simple:
var map = function(arr, func) {
var newarr = [];
for (var i = 0; i < arr.length; i++) {
newarr[i] = func(arr[i]);
}
return newarr;
};
My second implementation is my favorite, in terms of style, but I am not going to use it anytime soon because, although such approach is adequate and fast in such languages as Scheme, it is terribly slow without tail call optimization. Plus, as mentioned in the StackOverflow thread, concat function is too expensive to use it here.
var map1 = function(arr, func) {
if (arr.length === 0) return [];
return [func(arr[0])].concat(map1(arr.slice(1), func));
};
In my third implementation I used iterative recursion; it has no real advantages over the first method.
var map2 = function(arr, func) {
var iter = function(result, i) {
if (i === arr.length) return result;
result.push(func(arr[i]));
return iter(result, i+1);
};
return iter([], 0);
};
I received a few code samples after I posted my code chunks on the StackOverflow and below are interesting things I noticed.
What if obj.length property is not a positive number?
The code in SpiderMonkey makes sure that the obj.length is a positive number with bit manipulation. And although this works with strings and objects, it fails if value is a negative number.
"string" >>> 0; // 0
var obj = {}; obj >>> 0; // 0
-1 >>> 0; // 4294967295
So with SpiderMonkey approach, in case of negative obj.length value, we will initialize a huge array and try to iterate over it.
What about this inside a callback function?
My implementations don’t care about this object and this is probably a bad thing. The code from mikesamuel uses an empty object while the code in SpiderMonkey provides an optional parameter for this.
jQuery, as we see, does not care about that either.
Why jQuery flattens resulting array?
Here’s the line from jQuery source code that flattens result before returning it.
return ret.concat.apply( [], ret );I don’t know why they do that but it may cause unexpected results if you want to generate an array of arrays.
$.map([1,2,3], function(i) { return [i, i + 1]; });
// Expected: [ [1,2], [2,3], [3,4] ]
// Returned: [1, 2, 2, 3, 3, 4]
My latest version
With all the knowledge I got from the StackOverflow thread mentioned above I wrote another version of map implementation.
var map = function(arr, func /*, context */) {
if (typeof(arr.length) != 'number' || arr.length < 0) {
throw new TypeError();
}
if (typeof(func) != 'function') {
throw new TypeError();
}
var mapped = new Array(arr.length);
var context = (arguments.length > 2 ? arguments[2] : {});
for (var i = 0; i < arr.length; i++) {
mapped[i] = func.call(context, arr[i]);
}
return mapped;
};
The code (with some trivial tests) is also on my github page.
Update: Jesse Farmer reminded that map is a special case of inject and thus can be implemented as a call to the latter. His code: http://gist.github.com/208582.
