Reduce map and filter to their essence!

Let’s play some code golf and remove all the duplication from the following reimplementation of common list operations map, filter and reduce:

function map(fn, xs) {
  const result = [];

  for (let i = 0; i < xs.length; i++) {
    result.push(fn(xs[i], i));
  }

  return result;
}

function filter(fn, xs) {
  const result = [];

  for (let i = 0; i < xs.length; i++) {
    if (fn(xs[i], i)) {
      result.push(xs[i]);
    }
  }

  return result;
}

function reduce(fn, xs, init) {
  let result = init;

  for (let i = 0; i < xs.length; i++) {
    result = fn(result, xs[i], i);
  }

  return result;
}

First find the similarities: Each function introduces a result and then adds to it in some way in a for-loop.

The main difference between the first two and reduce is that in reduce we reassign the result whereas in map and filter something is pushed to result. Let’s unify those approaches by also reassigning in map and filter:

function map(fn, xs) {
  let result = [];

  for (let i = 0; i < xs.length; i++) {
    // result.push(fn(xs[i], i))
    result = [...result, fn(xs[i], i)];
  }

  return result;
}

function filter(fn, xs) {
  let result = [];

  for (let i = 0; i < xs.length; i++) {
    if (fn(xs[i], i)) {
      // result.push(xs[i])
      result = [...result, xs[i]];
    }
  }

  return result;
}

Let’s introduce a tiny function to help with that:

const append = (xs, x) => [...xs, x];

Note that this creates a new list everytime it is called. In performance critical application a mutating version of append should be preferred.

function map(fn, xs) {
  let result = [];

  for (let i = 0; i < xs.length; i++) {
    // result = [...result, fn(xs[i], i)]
    result = append(result, fn(xs[i], i));
  }

  return result;
}

function filter(fn, xs) {
  let result = [];

  for (let i = 0; i < xs.length; i++) {
    if (fn(xs[i], i)) {
      //   result = [...result, xs[i]]
      result = append(result, xs[i]);
    }
  }

  return result;
}

Now we compare the functions again:

function reduce(fn, xs, init) {
  let result = init;

  for (let i = 0; i < xs.length; i++) {
    result = fn(result, xs[i], i);
  }

  return result;
}

function map(fn, xs) {
  let result = [];

  for (let i = 0; i < xs.length; i++) {
    result = append(result, fn(xs[i], i));
  }

  return result;
}

function filter(fn, xs) {
  let result = [];

  for (let i = 0; i < xs.length; i++) {
    if (fn(xs[i], i)) {
      result = append(result, xs[i]);
    }
  }

  return result;
}

map and reduce look very similar, however filter with its if-statement inside the for-loop looks quite different. We use a ternary to make it more similar:

function filter(fn, xs) {
  let result = [];

  for (let i = 0; i < xs.length; i++) {
    // if (fn(xs[i], i)) {
    //   result = append(result, xs[i])
    // }
    result = fn(xs[i], i) ? append(result, xs[i]) : result;
  }

  return result;
}

If the predicate (fn) returns true append to the result otherwise just keep the result as is. Now all three functions look extremely similar, and we can locate the differences. Everything else is code duplication

function reduce(fn, xs, init) {
  let result = init;

  for (let i = 0; i < xs.length; i++) {
    result = fn(result, xs[i], i);
  }

  return result;
}

function map(fn, xs) {
  let result = [];

  for (let i = 0; i < xs.length; i++) {
    result = append(result, fn(xs[i], i));
  }

  return result;
}

function filter(fn, xs) {
  let result = [];

  for (let i = 0; i < xs.length; i++) {
    result = fn(xs[i], i) ? append(result, xs[i]) : result;
  }

  return result;
}

Besides initialization of result the biggest difference is on how the result is modified. It turns out we can use reduce to implement map as follows:

/*
function map(fn, xs) {
  let result = []

  for (let i = 0; i < xs.length; i++) {
    result = append(result, fn(xs[i], i))
  }

  return result
}
*/

function map(fn, xs) {
  return reduce((acc, x, i) => append(acc, fn(x, i)), xs, []);
}

function reduce(fn, xs, init) {
  let result = init;
  // init is []
  // -> let result = []

  for (let i = 0; i < xs.length; i++) {
    result = fn(result, xs[i], i);
    // fn is (acc, x, i) => append(acc, fn(x, i))
    // substitute acc with result and x with xs[i]
    // -> result = append(result, fn(xs[i], i))
  }

  return result;
}

We implement map by reducing over the given list xs. reduce creates a new list and fills it by appending the results of all fn calls for all elements.

For bonus points we can write the reduce powered map function in a single line:

const map = (fn, xs) => reduce((acc, x, i) => append(acc, fn(x, i)), xs, []);

The same for filter:

// function filter(fn, xs) {
//   let result = []

//   for (let i = 0; i < xs.length; i++) {
//     result = fn(xs[i], i) ? append(result, xs[i]) : result
//   }

//   return result
// }

function filter(fn, xs) {
  return reduce((acc, x, i) => (fn(x, i) ? append(acc, x) : acc), xs, []);
}

or

const filter = (fn, xs) =>
  reduce((acc, x, i) => (fn(x, i) ? append(acc, x) : acc), xs, []);

Result

From

function map(fn, xs) {
  const result = [];

  for (let i = 0; i < xs.length; i++) {
    result.push(fn(xs[i], i));
  }

  return result;
}

function filter(fn, xs) {
  const result = [];

  for (let i = 0; i < xs.length; i++) {
    if (fn(xs[i], i)) {
      result.push(xs[i]);
    }
  }

  return result;
}

function reduce(fn, xs, init) {
  let result = init;

  for (let i = 0; i < xs.length; i++) {
    result = fn(result, xs[i], i);
  }

  return result;
}

To

function reduce(fn, xs, init) {
  let result = init;

  for (let i = 0; i < xs.length; i++) {
    result = fn(result, xs[i], i);
  }

  return result;
}

const append = (xs, x) => [...xs, x];

const map = (fn, xs) => reduce((acc, x, i) => append(acc, fn(x, i)), xs, []);

const filter = (fn, xs) =>
  reduce((acc, x, i) => (fn(x, i) ? append(acc, x) : acc), xs, []);

Conclusion

This little exercise highlights how to spot redundancy and how to resolve it. The resulting map and filter functions are not only more concise but are also focussing more on the essence.

What is the essence of map? Create a new list and append to it using the given fn and the items from the old list.

What is the essence of filter? Create a new list and append to it only when a given predicate (fn) is true.