0

I'm studying functional programming and I'm having some question concerning array population.

Actually, I'm trying to rebuild the Array.prototype.map function, and here's what I've got:

Array.prototype.map = function(callback) {
  let newArray = [];
  for (let item of this) {
    newArray.push(callback(item));
  }
  return newArray;
};

It's working, bug I'm having some trouble with the fact that I'm allocation memory on each iteration, meaning that I'm breaking functional principles (no references, only new things).

Is that true when dealing with arrays? I mean there, is it correct to loop and assign in to a new array?

closed as unclear what you're asking by Robert Harvey, Ixrec, user22815, Bart van Ingen Schenau, user40980 Jan 26 '16 at 22:59

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 2
    'Functional principles' do not prevent you from allocating memory, although Javascript arrays are not a very good functional data structure. – Lee Jan 18 '16 at 12:45
  • 5
    Why is it surprising/bad that creating a new array involves allocating memory for that array to live in? Functional languages need memory too. – Ixrec Jan 18 '16 at 12:48
  • 4
    You are using an imperative data structure (array) and an imperative control flow mechanism (the for loop). Unfortunately, there's not really any functional content to what you are trying to do here. – David Arno Jan 18 '16 at 13:39
3

The code you have there is about as far from functional as could possibly be. The entire function is built around a side-effecting loop which mutates a value.

Here's the trivial functional implementation of a map operation:

Array.prototype.map = function (fn) {
  const [first, ...rest] = this;
  return this.length === 0 ? [] : [fn(first)].concat(rest.map(fn));
};

This will, however, blow the stack for a sufficiently large array. To avoid that, we need to make the function tail-recursive. In the version above, the tail-call is to the concat method. That call will be optimized away, but that doesn't help us much: we want the recursive call to map to be the tail-call, so that it gets optimized away.

The standard trick to make a function tail-recursive is to introduce an accumulator that gets passed along and then reverse the result.

Array.prototype.map = function (fn) {
  const mapTailrec = (ary, acc) => 
    ary.length === 0 ? 
      acc : 
      mapTailrec(ary.slice(0, -1), acc.concat([fn(ary[ary.length-1])]));
  return mapTailrec(this, []).reverse();
};

[Note: I'm actually cheating here, because Array.prototype.reverse is unfortunately not referentially transparent. It is however, pretty simple to write a tail-recursive referentially-transparent reverse, so I'll let that slide.]

As it turns out, fold is a general method of iteration: everything that can be done with loops can be done with folds, and so every collection operation is actually just a special case of fold:

Array.prototype.map = function (fn) {
  return this.reduce([], (acc, el) => acc.concat([fn(el)]));
};
  • ... if JavaScript supported TCO :-) – Florian Margaine Jan 20 '16 at 12:07
  • Proper Tail Calls were added to ECMAScript 2015. JavaScript ist no longer being developed, Mozilla abandoned it in favor of ECMAScript. (Or, put another way: JavaScript is now the name for a family of ECMAScript implementations by Mozilla and no longer a language designed by Mozilla.) – Jörg W Mittag Jan 20 '16 at 13:02
  • 1
    That's just being pedantic, at this point. ES2015's TCO is far from being out there in any of the major engines. Talking about it as if it's a commodity is a bit early. – Florian Margaine Jan 20 '16 at 13:07
  • 2
    I didn't say anything about any engine. I was talking about the ES2015 language. The ES2015 language has Proper Tail Calls. If any ES2015 engine doesn't, then it's broken, or, in other words, it's not an ES2015 engine. But that's irrelevant, since I'm not talking about any engines anyway. – Jörg W Mittag Jan 20 '16 at 14:26

Not the answer you're looking for? Browse other questions tagged or ask your own question.