Hacker News Reader

Comment by mkoryak | Hacker News Reader

I really like this js question (whiteboarding):

Implement function foo which takes an integer size, and returns an array of that size where each element in that array is a function that returns the index of that function in the array. Testcase: 42 === foo(1000)[42]()

There are 3 different correct solutions. Discuss which solution is better, worse... etc (if they get there)

(could probably be worded better, I'm not an english major)

View on HN

It's a good question, and a pretty fair one for a Javascript developer to know, given the role that closures play in the language.

That said, I'm not thinking of a 3rd solution. Closures(best?), a global(worse), what else?

Edit: As Daiz points out, the bind I was thinking of doesn't even have to even be to a global. But we still have seen only two solutions: variations of binding and closures. What's the third? Inquiring minds want to know!

The 3 solutions that I came up with are:

  - bind
  - function creator outside of the loop called from within
  - create an anon function on each loop iteration that acts like the function creator in #2

The bind is best in terms of memory and simplicity, but will not run on on IE 8 or crappier, so in that case #2 is preferred.

The last one creates anon functions needlessly, but is very compact to write.

5 solution with eval

  function foo(s) {
    a = Array(s);
    for (var i = 0; i < s; i++) {
      a[i] = eval('(function () { return ' + i + '})');
    }
    return a;
  }

fourth solution would be naming the function with the iterator (as in my example below) and calling indexOf(iterator) when the function is invoked

I feel bad, because as I was writing a solution to this I knew why it wouldn't work and why (returning my counter variable returns the value at the end of the count) but I still couldn't come up with a fix :(

Edit: A good Google seems to suggest using JSON.stringify and JSON.parse to copy the value.

Edit 2: But even that doesn't seem to work :(

Edit 3: Got it, using a generator function. Which makes sense. I guess I'm not an expert yet! :)

Here's a solution using closure: http://codepen.io/anon/pen/KwmQam

Using a closure:

  function foo(s) {
    function generator(i) {
      return function () {
        return i;
      };
    }

    var r = new Array(s);
    
    for (var i = 0; i < s; i++) {
      r[i] = generator(i);
    }
    
    return r;
  }

  console.log(foo(1000)[42]());

Using Function.prototype.bind():

  function foo(s) {
    function generator(i) {
      return i;
    }

    var r = new Array(s);
    
    for (var i = 0; i < s; i++) {
      r[i] = generator.bind(window, i);
    }
    
    return r;
  }

  console.log(foo(1000)[42]());

Here's another one. Probably not very performant

  function foo(count) {
     var ret = []
     for (var i=0; i < count; i++) {
        ret [i] = function i() { return this.indexOf(i) }
     }
     return ret;
  }

Just fyi indexOf is O(n), which means if you tried to do:

  var count = 1000000;
  var arr = foo(count);
  for (var i = 0; i < count; i++)
    arr[i]();

It will take O(n^2) and will probably never complete whereas all the other solutions here will probably take ~1second.

I may have discovered the worst correct answer:

    var foo = function (arr, i) {
      if (typeof arr === 'number') { 
        arr = new Array(arr);
        foo(arr, arr.length - 1);
        return arr;
      }
      if (i === -1) {
        return;
      }
      arr[i] = function () {
        return i;
      }
      foo(arr, i - 1);
    };

The only solution I could think of is this:

    function foo(n) {
        var result = [];
        for (var i = 0; i < n; i++)
            (function(j) { result.push(function() { return j; }); })(i);
        return result;
    }

What are the two others?

You could use Function.prototype.bind in a couple ways, or even Array.prototype.map (though sadly you can't really do new Array(n).map, if that was true you could make this a one-liner).

    // new Array(n) could just be [] in all examples
    //
    // using Array.prototype.map
    // sadly you can't do new Array(n).map
    // because it doesn't iterate over undefined functions
    function foo(n) {
      for (var ret = new Array(n), i = 0; i < n; ++i) {
        ret[i] = i;
      }
      return ret.map(function(_,n) { return function() { return n; }; });
    }

    // using Function.prototype.bind in a couple ways
    function foo(n) {
      function num() { return +this; }
      for (var ret = new Array(n), i = 0; i < n; ++i) {
        ret[i] = num.bind(i);
      }
      return ret;
    }

    function foo(n) {
      function num(a) { return a; }
      for (var ret = new Array(n), i = 0; i < n; ++i) {
        ret[i] = num.bind(null, i); // could bind this to pretty much whatever here
      }
      return ret;
    }

  function foo(a){
    return Array.apply(0, new Array(a)).map(function(_, b){
      return Number.bind(null, b)
    });
  }

If you're into one-liners, CoffeeScript is your friend :)

  foo = (n) -> (-> i) for i in [0..n]

Close, but I checked it and the value of `i` won't bind to the function. You also have to use `...` (exclusive range) instead of `..` to prevent an off-by-one error.

Here's one way:

    foo = (n) -> ((a) -> a).bind(null, i) for i in [0...n]

Here's a more esoteric/bad style (but cute) way:

    foo = (n) -> (-> +@).bind i for i in [0...n]

I've been preferring explicit `map()`s in my CoffeeScript for exactly that reason.

That's using a closure, another would be to use Function.prototype.bind (but really that's still using a closure, just putting it out of sight), can't think of any others.

>Function.prototype.bind (but really that's still using a closure, just putting it out of sight),

How is `bind` still using a closure? `bind` just allows users to alter a function's execution context. However, the implementation varies according to the JS engine. Some of them may use a closure internally as a part of the process, but I don't think V8 does.

Sure, I was cheating there a little bit. I was thinking in terms of how one would actually implement bind in user land JS code, which would use a closure. V8's implementation of bind likely does not.

    var foo = function (len) {
      return Array(len)
        .join(0)
        .split(0)
        .map(function (e, i) {
          return function () {
            return i;
          };
        });
    };

Reply on news.ycombinator.com