loading...

Build Your Own Filter

kasrakhosravi profile image Kasra Khosravi ・6 min read

Photo by Capturing the human heart. on Unsplash.

Filtering is a common programming pattern in which we iterate over a set of elements and only return a new set of elements that pass the condition provided by a filter function. Unlike mapping, we cannot reverse the process of applying the filter function to get to the original dataset; however, this is possible to achieve in mapping via applying the reverse of mapping function on the transformed set to get to the original one.

Applying filtering in the context of functional programming will help us achieve readability in a much better sense. All we have to do is provide the original array as well as the filtering function. With this declarative approach, the steps of filtering items from a set of data (array, in the case of this article) is hidden, and we have a focus on the end result we want to achieve.

Photo by Capturing the human heart. on Unsplash.

For example in the picture above, we do provide the initial array of [🍕, 🍔, 🥗, 🍏] and the filtering function isHealthy. The filter iterates over each of these tasty foods and, based on the filtering function it has, decides which is healthy and which is not. Only the healthy ones will be preserved in the new array and, in the end, returned[🥗, 🍏].

Similar to mapping, we have a few options of filtering elements in an array, with both declarative and imperative approaches.


Tip: I completely understand that software interviews can be a bit scary, so my hope is to give you clear ideas about the interview process and offer you practical advice on how to do well at each step.

Map

This course can be very helpful for you to get an overview of all the common interview steps that companies go through to hire a developer. Sign up for SkillShare, Get two months of free trial and Join me on this journey


For Loop

Using for loop for a filter is an imperative approach of iterating over elements and pushing the ones to an array that pass a condition nested in the for loop.

let items = [1, 2, 3, 4, 5];
let isEven = item => item % 2 === 0;
const result = [];

for (let i = 0; i < items.length; i++) {
  if (isEven(items[i])) {
    result.push(items[i]);
  }
}

console.log(result);
// Result: [2, 4]

As you can see, we need to keep track of item indexes, define an initial array, and nest conditional statements inside the for loop. Even though this way of filtering can be performant, it is not very readable.


forEach

Another option we have is to use forEach, which, like a for loop, iterates over an array of elements. But the good thing about using it is we don't have to worry about index tracking. Let's see it with an example:

let items = [1, 2, 3, 4, 5];
let isOdd = item => item % 2 !== 0;
const result = [];

items.forEach(item => {
  if (isOdd(item)) {
    result.push(item);
  }
});

console.log(result);
// Result: [1, 3, 5]

This seems like an improvement to the previous alternative in terms of readability, but mutating the result array outside the context of our iterator is not ideal. It would have been better if we had a filtering method that always returns a new array.

In fact, we have access to a better alternative, called native JavaScript filter.


Native JavaScript Filter

Native JavaScript filter takes a declarative approach in filtering array elements. Since it is a method defined on Array.prototype, it iterates on a provided array and invokes a callback on it. This callback, which acts as our filtering function, takes three parameters:

  • element - the current item in the array being iterated over
  • index - the index or location of the current element in the array that is being iterated over
  • array - the original array that the filter method was applied on

Let's use this filter method in an example. Note that the filter can be applied on any sort of array. In this example, we are going to filter an array of objects based on an object property.

// Please do not hate me for bashing on pizza and burgers.
// and FYI, I totally made up the healthMetric param :)
let foods = [
  { type: "pizza", healthMetric: 25 },
  { type: "burger", healthMetric: 10 },
  { type: "salad", healthMetric: 60 },
  { type: "apple", healthMetric: 82 }
];

let isHealthy = food => food.healthMetric >= 50;

const result = foods.filter(isHealthy);

console.log(result.map(food => food.type));
// Result: ['salad', 'apple']

With just one line of code, we were able to filter an array of items. That is pretty awesome. Also, as you can see in line 12, chaining mapping and filtering methods can be really useful for working with different types of datasets.

So far, we have learned some basic stuff about filtering and different ways of handling it in JavaScript. Although our main focus was on readability, we should never forget performance when it comes to applying a method on our dataset.


Build a Filtering Function

We now turn our attention to building our own filtering functions. Building a production-ready filtering method that scales with larger datasets and considers different edge cases is not straightforward, as we can see in the polyfill made for JavaScript's native filter. However, in our example, we're going to focus on the core of filtering an array.

Own filter function (for loop version)

Abstracting the filtering process with for loop is very straightforward. We provide the filtering function and original array and let the FilterLoop handle the filtering process for us.

let candidates = [
  { name: "batman", isSuperHero: true },
  { name: "jon snow", isSuperHero: false },
  { name: "wonder woman", isSuperHero: true },
  { name: "sheldon cooper", isSuperHero: false }
];
let isSuperHero = candidate => candidate.isSuperHero;

// Loop Version of Filter
let FilterLoop = (validFn, arr) => {
  const filteredArr = [];
  for (let i = 0; i < arr.length; i++) {
    validFn(arr[i]) ? filteredArr.push(arr[i]) : null;
  }
  return filteredArr;
};

const result = FilterLoop(isSuperHero, candidates);
console.log(result.map(candidate => candidate.name));
["batman", "wonder woman"]

Own filter function (recursive version)

Now we are going to create a recursive version of the filtering function. Make sure to check building a recursive version of a mapping function first.

Like the for loop version, we need to pass both an array as well as a filtering function. However, as you can see in line 2, we are destructuring the array parameter and breaking it apart into two new variables called head and tail.

This approach allows us to decide at each step if we need to return the head element if it passes the validFn validation (shown on line 9). If not, we simply ignore the head element for that iteration and continue recursively calling the FilterRecursive function (shown on line 13).

After each iteration, the length of the original array shrinks down until we reach an empty array in the end. It is at that point that head will be set as undefined, since we will be trying to destructure an empty array. Then we start returning array elements that passed the validator.


let candidates = [
  { name: "batman", isSuperHero: true },
  { name: "jon snow", isSuperHero: false },
  { name: "wonder woman", isSuperHero: true },
  { name: "sheldon cooper", isSuperHero: false }
];
let isSuperHero = candidate => candidate.isSuperHero;

// Recursive Version of Filter
let FilterRecursive = (validFn, [head, ...tail]) => {

  // bailout
  if (head === undefined) {
    return [];
  }

  if (validFn(head)) {
    return[head, ...FilterRecursive(validFn, tail)];
  }

  return[...FilterRecursive(validFn, tail)];
};

const result = FilterRecursive(isSuperHero, candidates);
console.log(result.map(candidate => candidate.name));
["batman", "wonder woman"]

Own filter function (generator version)

This is a very rudimentary example of a filtering function built with generator functions. As you can see in the logs below the code, the generator function returns an iterator object each time it's called. With passing our validator function, we are only returning values in the iterator object that pass its validation.


let items = [1, 2, 3, 4, 5];
let isEven = item => item % 2 === 0;

// Generator version of Filter
let FilterGenerator = function*(fn, arr) {
  for (let x of arr) {
    if (fn(x)) {
      yield x;
    }
  }
};

const result = FilterGenerator(isEven, items);

console.log(result.next());
// Object {value: 2, done: false}
console.log(result.next());
// Object {value: 4, done: false}
console.log(result.next());
// Object {value: undefined, done: true}

Tip: I completely understand that software interviews can be a bit scary, so my hope is to give you clear ideas about the interview process and offer you practical advice on how to do well at each step.

Map

This course can be very helpful for you to get an overview of all the common interview steps that companies go through to hire a developer. Sign up for SkillShare, Get two months of free trial and Join me on this journey


Resources

https://www.freecodecamp.org/news/implement-array-map-with-recursion-35976d0325b2/

https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/filter

Posted on May 17 by:

kasrakhosravi profile

Kasra Khosravi

@kasrakhosravi

Software developer with a passion for maintainability and scalability design patterns as well as functional programming paradigm.

Discussion

markdown guide
 

Hi there, thanks for your article. I liked the fact that you gave multiple ways of doing this filter function.

I'm not sure if this was intended, but you didn't give any code example for the recursive solution. Here is my take.

const filter = (shouldBeKept, items) => {
    if (items.length === 0) {
        return [];
    }

    const [item, ...rest] = items;

    if (shouldBeKept(item)) {
        return [item, ...filter(shouldBeKept, rest)];
    }

    return filter(shouldBeKept, rest);
};

If we break it down:

  1. We first check if we didn't receive an empty array (this is our base-case for our recursive function to stop)
  2. If this is the case, we stop here and return an empty array as well
  3. Otherwise, we destructure our array to get the first item and the rest
  4. We check if we should keep the first item or not
  5. If this is the case, then we return an array concatenating the first item and we filter out the rest
  6. Otherwise, we just continue on filtering the rest and we return the result of this recursive call
  7. Again, the function is recursive, so this means that it will go back to the first step

What do you think?

 

Thanks Amin for letting me know :) I forgot to put the snippet code in the blog post. I just updated it.

I like your approach; it is very readable and understandable.