-1

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?

3
  • 2
    'Functional principles' do not prevent you from allocating memory, although Javascript arrays are not a very good functional data structure.
    – Lee
    Jan 18, 2016 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, 2016 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, 2016 at 13:39

1 Answer 1

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)]));
};
4
  • ... if JavaScript supported TCO :-) Jan 20, 2016 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.) Jan 20, 2016 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. Jan 20, 2016 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. Jan 20, 2016 at 14:26

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