Three map implementations in javascript. Which one is better?

Question

I wrote a simple map implementation for some task. Then, out of curiosity, I wrote two more. I like map1 but the code is kinda hard to read. If somebody is interested, I'd appreciate a simple code review.

Which one is better? Do you know some other way to implement this in javascript?

var map = function(arr, func) {
  var newarr = [];
  for (var i = 0; i < arr.length; i++) {
    newarr[i] = func(arr[i]);
  }
  return newarr;
};

var map1 = function(arr, func) {
  if (arr.length === 0) return [];
  return [func(arr[0])].concat(funcmap(arr.slice(1), func));
};

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);
};

Thanks!

EDIT

I am thinking about such function in general.

For example, right now I am going to use it to iterate like this:

map(['class1', 'class2', 'class3'], function(cls) { 
    el.removeClass(cls);
});

or

ids = map(elements, extract_id); 
/* elements is a collection of html elements, 
   extract_id is a func that extracts id from innerHTML */

Answer 1

I think that depends on what you want map to do when func might change the array. I would tend to err on the side of simplicity and sample length once.

You can always specify the output size as in

var map = function(arr, func) {
  var n = arr.length & 0x7fffffff;  // Make sure n is a non-neg integer
  var newarr = new Array(n);  // Preallocate array size
  var USELESS = {};
  for (var i = 0; i < n; ++i) {
    newarr[i] = func.call(USELESS, arr[i]);
  }
  return newarr;
};

I used the func.call() form instead of just func(...) instead since I dislike calling user supplied code without specifying what 'this' is, but YMMV.

Answer 2

I'd say the first one wins on simplicity (and immediate understandability); performance will be highly dependent on what the engine at hand optimizes, so you'd have to profile in the engines you want to support.

Answer 3

As a reference, map is implemented as following in jQuery

map: function( elems, callback ) {
 var ret = [];

 // Go through the array, translating each of the items to their
 // new value (or values).
 for ( var i = 0, length = elems.length; i < length; i++ ) {
  var value = callback( elems[ i ], i );

  if ( value != null )
   ret[ ret.length ] = value;
 }

 return ret.concat.apply( [], ret );
}

which seems most similar to your first implementation. I'd say the first one is preferred as it is the simplest to read and understand. But if performance is your concern, profile them.

Answer 4

There's something wrong in second method. 'funcmap' shouldn't be changed to 'map1'?

If so - this method loses, as concat() method is expensive - creates new array from given ones, so has to allocate extra memory and execute in O(array1.length + array2.length).

I like your first implementation best - it's definitely easiest to understand and seems quick in execution to me. No extra declaration (like in third way), extra function calls - just one for loop and array.length assignments.

Answer 5

This first one is most appropriate. Recursing one level for every array item may make sense in a functional language, but in a procedural language without tail-call optimisation it's insane.

However, there is already a map function on Array: it is defined by ECMA-262 Fifth Edition and, as a built-in function, is going to be the optimal choice. Use that:

alert([1,2,3].map(function(n) { return n+3; })); // 4,5,6

The only problem is that Fifth Edition isn't supported by all current browsers: in particular, the Array extensions are not present in IE. But you can fix that with a little remedial work on the Array prototype:

if (!Array.prototype.map) {
    Array.prototype.map= function(fn, that) {
        var result= new Array(this.length);
        for (var i= 0; i<this.length; i++)
            if (i in this)
                result[i]= fn.call(that, this[i], i, this);
        return result;
    };
}

This version, as per the ECMA standard, allows an optional object to be passed in to bind to this in the function call, and skips over any missing values (it's legal in JavaScript to have a list of length 3 where there is no second item).

Answer 6

What about the map implementation used natively on Firefox and SpiderMonkey, I think it's very straight forward:

if (!Array.prototype.map) {
  Array.prototype.map = function(fun /*, thisp*/)   {
    var len = this.length >>> 0;  // make sure length is a positive number
    if (typeof fun != "function") // make sure the first argument is a function
      throw new TypeError();

    var res = new Array(len);  // initialize the resulting array
    var thisp = arguments[1];  // an optional 'context' argument
    for (var i = 0; i < len; i++) {
      if (i in this)
        res[i] = fun.call(thisp, this[i], i, this);  // fill the resulting array
    }

    return res;
  };
}

If you don't want to extend the Array.prototype, declare it as a normal function expression.