Polyfill array methods

Why rebuild built-ins?

A built-in is a method that JavaScript already gives you, such as map. A polyfill is code that adds a standard feature to a browser (or another place that runs JavaScript) that doesn't have it yet.

In this lesson, you write your own versions of four array methods:

• map changes every item.
• filter keeps some of the items.
• reduce combines all the items into one value.
• flat takes items out of the arrays inside an array.

You write each one as a plain function, such as myMap. Writing it yourself shows the small rules that the real method follows without telling you.

This is the first lesson in Build it from scratch. The goal is to understand the real methods, not to replace them. Along the way you will meet these rules:

• what the callback (the function you pass in) receives,
• what happens with empty slots in an array,
• which errors the methods throw,
• how the official rule book for JavaScript, the spec, writes each step.

Job interviews often ask you to write these functions. One small missing rule shows whether someone knows how the method really behaves.

Read this lesson after map, filter & reduce and Higher-order functions. It also links to Array basics, Iterating arrays, Recursion, Property descriptors, Native prototypes, and Manuals and specs at the places where those ideas come up.

Each version is a plain function that takes the array as its first argument. It is not a method on every array. A plain function is easy to test, and it doesn't change anything that other code shares.

Each function starts with the same three steps:

1. Turn the input into an object. This throws an error for null and undefined.
2. Read the length once, before the loop.
3. Throw an error if the callback is not a function, before the loop starts.

The code below holds three small helpers for these steps.

1function toObject(value) {2  if (value == null) {3    throw new TypeError("Cannot convert undefined or null to object");4  }5  return Object(value);6}7 8function toLength(value) {9  const number = +value;10  if (!Number.isFinite(number) || number <= 0) return 0;11  return Math.min(Math.floor(number), Number.MAX_SAFE_INTEGER);12}13 14function toDepth(value) {15  const number = +value;16  if (number === Infinity) return Infinity;17  if (!Number.isFinite(number) || number <= 0) return 0;18  return Math.floor(number);19}

• Line 1, toObject, turns the input into an object. A string becomes an object you can read by index. null and undefined throw a TypeError, just like the real methods.
• Line 8, toLength, turns the length into a whole number. +value turns it into a number first. Anything that is not a positive number becomes 0.
• Line 14, toDepth, does the same for the depth of flat, but keeps Infinity.

Because of toObject, array methods also work on strings and on array-like objects. An array-like object has a length and numbered keys, like { length: 2, 0: "a", 1: "b" }. Because the length is read once, adding items during the loop doesn't make the loop longer.

1function myMap(arrayLike, callback, thisArg) {2  const object = toObject(arrayLike);3  const length = toLength(object.length);4  if (typeof callback !== "function") {5    throw new TypeError(String(callback) + " is not a function");6  }7  const result = new Array(length);8  for (let index = 0; index < length; index += 1) {9    if (index in object) {10      result[index] = callback.call(thisArg, object[index], index, object);11    }12  }13  return result;14}

• Lines 2 to 5 are the three steps above.
• Line 7 makes the result array, with the same length as the input.
• Line 8 goes through each index, from 0 up to the length.
• Line 9 checks that the index exists. index in object is false for an empty slot, so the callback is skipped there.
• Line 10 calls the callback with three things: the value, the index, and the whole object. It stores the answer at the same index.

Line 10 uses callback.call(thisArg, ...). The .call() method runs a function and sets what this means inside it. Here this becomes thisArg, an optional last argument you can pass to myMap.

1function myFilter(arrayLike, callback, thisArg) {2  const object = toObject(arrayLike);3  const length = toLength(object.length);4  if (typeof callback !== "function") {5    throw new TypeError(String(callback) + " is not a function");6  }7  const result = [];8  for (let index = 0; index < length; index += 1) {9    if (index in object) {10      const value = object[index];11      if (callback.call(thisArg, value, index, object)) {12        result.push(value);13      }14    }15  }16  return result;17}

myFilter uses the same checks. Line 7 starts with an empty result. The difference is on lines 11 and 12. When the callback returns a truthy value (a value that counts as true in an if), push adds the original value to the end of the result. So the result has no gaps, and a kept value can end up at a new index.

1function myReduce(arrayLike, callback, initialValue) {2  const object = toObject(arrayLike);3  const length = toLength(object.length);4  if (typeof callback !== "function") {5    throw new TypeError(String(callback) + " is not a function");6  }7 8  let index = 0;9  let accumulator = initialValue;10  if (arguments.length < 3) {11    while (index < length && !(index in object)) index += 1;12    if (index >= length) {13      throw new TypeError("Reduce of empty array with no initial value");14    }15    accumulator = object[index];16    index += 1;17  }18 19  for (; index < length; index += 1) {20    if (index in object) {21      accumulator = callback(accumulator, object[index], index, object);22    }23  }24  return accumulator;25}

reduce keeps a running result, called the accumulator. Its starting value is optional. Lines 10 to 17 handle the case where you don't pass one:

• Line 10 counts the arguments. Fewer than 3 means there is no starting value.
• Line 11 skips empty slots until it finds an item that exists.
• Lines 12 and 13 throw the same error as the real reduce if there is no such item.
• Lines 15 and 16 use that first item as the accumulator and move the loop past it.
• Line 21 calls the callback for each item left and keeps its answer as the new accumulator.

An array can have an empty slot, also called a hole. In [1, , 3], the two commas side by side leave index 1 with nothing at all. An array with holes is called sparse.

The real map skips a hole. It doesn't call the callback there, and it leaves the same hole in the result. A hole is not the same as a slot that holds undefined. The method first checks whether the index exists, and only then reads the value.

1const sparse = [1, , 3];2const calls = [];3const mapped = sparse.map((value, index) => {4  calls.push(index);5  return value * 2;6});7 8console.log(calls.join(","));9console.log(0 in mapped, 1 in mapped, 2 in mapped);10console.log(mapped);

• Line 8 prints 0,2. The callback ran for index 0 and index 2, but not for index 1.
• Line 9 prints true false true. The result has nothing at index 1.
• Line 10 prints [ 2, <1 empty item>, 6 ]. The console shows the hole as an empty item.

1const values = [, undefined];2const calls = [];3const mapped = myMap(values, (value, index) => {4  calls.push(index);5  return value === undefined ? "present" : value;6});7 8console.log(calls.join(","));9console.log(0 in mapped, 1 in mapped);

• Line 1 makes an array with a hole at index 0 and the value undefined at index 1.
• Line 4 records each index the callback runs for.
• Line 5 returns "present" when the value is undefined.
• Line 8 prints 1. Only index 1 ran the callback.
• Line 9 prints false true. Only index 1 exists in the result.

1const sparse = [1, , 3];Run2const context = { bonus: 10 };3const result = myMap(sparse, function (value, index, array) {4  return value + index + this.bonus;5}, context);6console.log(0 in result, 1 in result, result);

filter skips holes too. But it puts the kept values next to each other in a new array, with no gaps. That is why map keeps the same length, while filter often gives back a shorter array.

1const sparse = [0, , 2, 3];Run2const kept = myFilter(sparse, function (value, index) {3  return value >= 2;4});5console.log(kept);

Each method also takes an optional last argument, thisArg. It sets what this means inside the callback. The next example passes it to a normal function and to an arrow function.

1const context = { bonus: 10 };2 3const withFunction = myMap([1], function (value) {4  return value + this.bonus;5}, context);6 7const runner = {8  bonus: 100,9  run() {10    return myMap([1], value => value + this.bonus, context);11  },12};13 14console.log(withFunction);15console.log(runner.run());

• Lines 3 to 5 pass a normal function. myMap calls it with callback.call(thisArg, ...), so this is context and this.bonus is 10. Line 14 prints [ 11 ].
• Line 10 passes an arrow function. An arrow function has no this of its own. It uses the this of the code around it. Here that is runner, because run() was called as runner.run(). So this.bonus is 100, and line 15 prints [ 101 ].

reduce has the trickiest start. It depends on whether you pass a starting value:

• With a starting value, the accumulator starts there. The callback runs for every item that exists.
• Without one, the first item that exists becomes the accumulator. The callback starts at the next item.

In both cases, holes are skipped.

1const prices = [5, , 12];Run2const total = myReduce(prices, (acc, price, index) => {3  return acc + price;4}, 0);5console.log(total);

1const add = (total, value) => total + value;2 3try {4  myReduce([], add);5} catch (error) {6  console.log(error.name);7}8console.log(myReduce([], add, undefined));9console.log(myReduce([], add, 0));10console.log(myReduce([, 5], add));

• Line 4 leaves out the third argument. The array is empty, so there is nothing to start with. Line 6 prints TypeError.
• Line 8 passes undefined on purpose. That still counts as a starting value, so it prints undefined.
• Line 9 passes 0 and prints 0.
• Line 10 has no starting value, so myReduce starts with the first item that exists, 5. Nothing comes after it, so it prints 5.

1try {2  [].reduce((acc, value) => acc + value);3} catch (error) {4  console.log(error.name + ": " + error.message);5}6 7try {8  myReduce([], (acc, value) => acc + value);9} catch (error) {10  console.log(error.name + ": " + error.message);11}

Line 2 uses the real reduce, and line 8 uses myReduce. Lines 4 and 10 both print TypeError: Reduce of empty array with no initial value. Matching the exact message is useful in tests. It shows your version took the same path as the real one.

flat copies values into a new array with no gaps. When it finds an array inside the array, it can open it and copy its values too. The depth says how many levels to open:

• The default depth is 1: open one level.
• Infinity opens every level, however deep.

1function myFlat(arrayLike, depth = 1) {2  const result = [];3  flattenInto(result, toObject(arrayLike), toDepth(depth));4  return result;5}6 7function flattenInto(target, source, depth) {8  const length = toLength(source.length);9  for (let index = 0; index < length; index += 1) {10    if (!(index in source)) continue;11    const value = source[index];12    if (Array.isArray(value) && depth > 0) {13      flattenInto(target, value, depth === Infinity ? Infinity : depth - 1);14    } else {15      target.push(value);16    }17  }18}

Recursion means a function calls itself. Here flattenInto calls itself for each inner array.

• Line 3 starts the work with the result, the input, and the depth.
• Line 8 reads the length once.
• Line 10 skips holes.
• Line 12 checks for an inner array while the depth is above zero.
• Line 13 calls flattenInto again for that inner array, with one less depth.
• Line 15 copies any other value into the result.

JavaScript keeps track of every call that hasn't finished yet on the call stack. The call stack has a size limit. A very deeply nested input makes many calls at once and can go past that limit. A version that keeps its own list of work avoids this.

1function myFlatWithStack(arrayLike, depth = 1) {2  const root = toObject(arrayLike);3  const result = [];4  const stack = [{5    source: root,6    index: 0,7    length: toLength(root.length),8    depth: toDepth(depth),9  }];10 11  while (stack.length > 0) {12    const frame = stack.pop();13    if (frame.index >= frame.length) continue;14    const index = frame.index;15    frame.index += 1;16    stack.push(frame);17    if (!(index in frame.source)) continue;18    const value = frame.source[index];19    if (Array.isArray(value) && frame.depth > 0) {20      stack.push({21        source: value,22        index: 0,23        length: toLength(value.length),24        depth: frame.depth === Infinity ? Infinity : frame.depth - 1,25      });26    } else {27      result.push(value);28    }29  }30  return result;31}

Here the stack is a plain array of jobs still to do. Each job remembers four things: an array, the next index to read, its length, and its depth.

• Line 4 starts the stack with one job: the whole input.
• Line 11 keeps going while jobs are left.
• Line 12 takes the last job off the stack.
• Lines 19 and 20 find an inner array and add a new job for it, instead of calling a function.
• Line 27 copies a plain value into the result.

1const nested = [1, [2, [3, [4]]], , 5];2 3console.log(myFlat(nested));4console.log(myFlat(nested, 2));5console.log(myFlat(nested, Infinity));6console.log(myFlatWithStack(nested, Infinity));

• Line 3 uses depth 1 and prints [ 1, 2, [ 3, [ 4 ] ], 5 ].
• Line 4 uses depth 2 and prints [ 1, 2, 3, [ 4 ], 5 ].
• Lines 5 and 6 use Infinity, with both versions. Both print [ 1, 2, 3, 4, 5 ].

The hole at index 2 of nested never shows up in any result.

1const nested = [1, [2, [3, [4]]], , 5];Run2const result = myFlat(nested, 1);3console.log(result);

The spec is the official rule book for JavaScript. Its name is ECMA-262. It describes Array.prototype.map as a list of exact steps, which is more than "loop and push". Below is a short version of those steps.

Spec steps read like a recipe. Words like ToObject and HasProperty are the names of smaller recipes in the spec. The short names stand for:

• O: the array, turned into an object.
• len: its length.
• k: the current index, and Pk: that index as a property name.
• A: the result array.

11. ToObject(this value)22. LengthOfArrayLike(O)33. If IsCallable(callbackfn) is false, throw a TypeError44. ArraySpeciesCreate(O, len)55. For each index k from 0 to len - 1:66.   If HasProperty(O, Pk), Get(O, Pk) and call callbackfn77.   CreateDataPropertyOrThrow(A, Pk, mappedValue)

In plain words, line by line:

1. Turn the array into an object. In our code, this is toObject.
2. Read its length once. In our code, this is toLength(object.length).
3. If the callback is not a function, throw a TypeError.
4. Make the result array, A, with that length.
5. Go through each index, from 0 up to the length minus 1.
6. If the index exists, read its value and call the callback. In our code, this is index in object.
7. Store the callback's answer in A, at the same index.

Step 4 says ArraySpeciesCreate. It lets a subclass of Array, made with class MyList extends Array, choose what kind of array the result is. Our functions always return a normal array. It still helps to know the step is there when you read Manuals and specs.

The next example shows step 2 at work: the length is read once.

1const values = [1, 2];2const native = values.map((value, index, array) => {3  if (index === 0) array.push(99);4  return value * 2;5});6 7const polyfilled = myMap([1, 2], (value, index, array) => {8  if (index === 0) array[2] = 99;9  return value * 2;10});11 12console.log(native);13console.log(values);14console.log(polyfilled);

• values starts with two items.
• At index 0, line 3 pushes 99, so values now has three items.
• Line 12 still prints [ 2, 4 ], because the loop stops after index 1.
• Line 13 shows that values really changed: [ 1, 2, 99 ].
• Lines 7 to 10 try the same with myMap. Line 8 adds 99 at index 2. Line 14 prints [ 2, 4 ] too.

1const values = ["tea", "cake", "juice"];2const visited = [];3const result = myMap(values, (value, index, array) => {4  visited.push(value);5  if (index === 0) {6    delete array[1];7    array[2] = "coffee";8    array.push("water");9  }10  return value.toUpperCase();11});12 13console.log(visited.join(","));14console.log(result);15console.log(values);

At index 0, the callback changes the array in three ways:

• Line 6 deletes index 1.
• Line 7 changes index 2 to "coffee".
• Line 8 adds "water" at the end.

The loop still stops at the length it read at the start, 3. Each index is checked only when the loop gets there:

• Index 1 no longer exists, so it is skipped.
• Index 2 now holds "coffee", so that new value is read.
• "water" is at index 3, past the end, so it is never visited.

Line 13 prints tea,coffee. Line 14 prints [ 'TEA', <1 empty item>, 'COFFEE' ]. Line 15 prints [ 'tea', <1 empty item>, 'coffee', 'water' ].

1const letters = { length: 2, 0: "a", 1: "b" };2 3const native = Array.prototype.map.call(4  letters,5  (value, index) => value + index,6);7const polyfilled = myMap(letters, (value, index) => value + index);8 9console.log(native);10console.log(polyfilled);

• Line 1 makes letters. It is not an array. It is an object with a length and numbered keys.
• Lines 3 to 6 borrow the real map with .call(), so this inside map is letters.
• Line 7 passes letters to myMap.
• Lines 9 and 10 both print [ 'a0', 'b1' ].

You meet array-like objects in DOM lists, in the arguments object, and in older code that borrows array methods with call.

1const inheritedValues = Object.create({ 0: "tea" });2inheritedValues.length = 1;3 4console.log(myMap(inheritedValues, value => value.toUpperCase()));

A prototype is the object JavaScript checks next when a property is missing. Line 1 makes an object whose prototype holds index 0. So index 0 is not on inheritedValues itself. Line 2 sets the length to 1. The in check looks at the prototype too, so myMap visits index 0. Line 4 prints [ 'TEA' ].

1for (const run of [2  () => myMap({ length: 1n, 0: "tea" }, value => value),3  () => myFlat(["tea"], 1n),4]) {5  try {6    run();7  } catch (error) {8    console.log(error.name);9  }10}

A BigInt is a whole number written with an n at the end, like 1n. Line 2 tries a length of 1n. Line 3 tries a flat depth of 1n. Line 6 runs each one, and line 8 prints TypeError twice. The +value in our helpers throws for a BigInt, and so do the real methods. Only Number(1n), written out, turns a BigInt into a normal number.

Adding a method to every array

Every array gets its methods from one shared object, Array.prototype. Real polyfills sometimes add a method there, so that every array has it. Doing that in app code is risky:

• A future version of JavaScript may add a method with the same name.
• Libraries that loop over every property, including shared ones, may see your method.
• Tests can pass or fail depending on which file ran first.

Leave this job to build tools. And always check first whether the method already exists.

1(() => {2  const nativeMap = Array.prototype.map;3  const nativeFlat = Array.prototype.flat;4  const hadOwn = Object.prototype.hasOwnProperty.call(Array.prototype, "myMap");5  const previous = Array.prototype.myMap;6 7  if (typeof Array.prototype.myMap !== "function") {8    Object.defineProperty(Array.prototype, "myMap", {9      value(callback, thisArg) {10        return myMap(this, callback, thisArg);11      },12      enumerable: false,13      writable: true,14      configurable: true,15    });16  }17 18  console.log([1, 2].myMap(value => value * 3));19  const descriptor = Object.getOwnPropertyDescriptor(Array.prototype, "myMap");20  console.log(descriptor.enumerable, descriptor.writable, descriptor.configurable);21  console.log(Array.prototype.map === nativeMap, Array.prototype.flat === nativeFlat);22 23  if (hadOwn) {24    Object.defineProperty(Array.prototype, "myMap", {25      value: previous,26      enumerable: false,27      writable: true,28      configurable: true,29    });30  } else {31    delete Array.prototype.myMap;32  }33  console.log(hadOwn34    ? Array.prototype.myMap === previous35    : !Object.prototype.hasOwnProperty.call(Array.prototype, "myMap"));36})();

• Lines 2 to 5 save the real methods and any old myMap, so they can be checked and put back.
• Line 7 checks whether myMap already exists. Line 8 adds it only if it doesn't.
• Lines 12 to 14 set the property's settings. enumerable: false hides it from loops.
• Lines 23 to 32 put back the old method, or delete the new one.

The demo prints four lines:

• Line 18 prints [ 3, 6 ]. The new method works.
• Line 20 prints false true true. The method is hidden from loops (not enumerable), but it can still be changed (writable) and removed (configurable).
• Line 21 prints true true. The real map and flat were not touched.
• Line 33 prints true. The temporary method is gone.

The Native prototypes lesson explains how prototypes work. In normal app code, don't change them.

You can only trust a polyfill when it matches the real method on tricky inputs. The lab below runs each case twice: once with the real method, and once with the lesson function.

1const input = [1, , 3];2console.log(input.map(value => value * 2));3console.log(myMap(input, value => value * 2));

The table lists each case in the lab. Read each row as: in this case, the real method does this, so your version must do that.

Practical use and misconceptions

Rebuilding these methods helps you fix bugs faster. You will know why:

• a callback did not run,
• thisArg did nothing,
• an empty reduce crashed,
• a DOM list can borrow an array method.

You will also write better tests for helper functions that accept array-like inputs.

1const rows = [2  { name: "Ada", skills: ["math", "js"] },3  { name: "Lin", skills: [] },4];5 6const skillLabels = myFlat(7  myMap(rows, row => myMap(row.skills, skill => row.name + ": " + skill)),8);9 10console.log(skillLabels);

• Line 7 turns each row into a list of labels, like "Ada: math". That gives an array of arrays. Lin has no skills, so Lin's list is empty.
• Line 6 flattens that one level with myFlat.
• Line 10 prints [ 'Ada: math', 'Ada: js' ].

The first table compares the four methods. Read each row as: this method does this job, and gives back this.

The second table compares three ways to write a polyfill.

Work each answer out from the steps, not from memory. Each explanation names the rule the answer depends on.

Key takeaways

• Write plain functions first. Adding methods to Array.prototype is a separate, risky step.
• map keeps holes in its result. filter, reduce, and flat skip them and leave no gaps.
• The callback gets the value, the index, and the array. A normal function can also use thisArg as this.
• reduce with no starting value begins with the first item that exists. On an empty array, it throws a TypeError.
• Test your version against the real method on tricky inputs: holes, array-like objects, changes during the loop, bad callbacks, and deep nesting.

Up next in this module: rebuilding call, apply, and bind. There, you control what this means for any function yourself.