Thomas Johnson

Algorithm Scripting -- Group By

In the last post, I explained how to solve Free Code Camp’s Sorted Union algorithm challenge. Today, I want to talk about a Codewars algorithm challenge that I recently submitted a solution for.

The challenge: Array.prototype.groupBy

Here’s a description of the challenge from the Codewars website:

Add a groupBy method to Array.prototype so that elements in an array could be grouped by the result of evaluating a function on each element.

The method should return an object, in which for each different value returned by the function there is a property whose value is the array of elements that return the same value.

If no function is passed, the element itself should be taken.

These examples are provided to illustrate the concept:

// I'm using the expect testing library to frame these assertions.

expect([1, 2, 3, 2, 4, 1, 5, 1, 6].groupBy()).toEqual({
  1: [1, 1, 1],
  2: [2, 2],
  3: [3],
  4: [4],
  5: [5],
  6: [6]
});

expect(
  [1, 2, 3, 2, 4, 1, 5, 1, 6].groupBy(function(val) {
    return val % 3;
  })
).toEqual({
  0: [3, 6],
  1: [1, 4, 1, 1],
  2: [2, 2, 5]
});

The description and the examples are pretty clear, so I don’t think there’s any reason to provide a detailed gloss on what is being asked for here. To put it briefly, the idea is to extend Array.prototype with a method that categorizes an array’s elements according to the value that gets generated when they are passed to a given function. The method should return an object, the structure of which is illustrated by the example cases.

The reason I like this challenge is because it gives me a good opportunity to talk about three features of ES6 that I find myself time and again: default parameters, arrow functions, and the spread operator.

Array.prototype

Before we get to those features, however, let’s take a quick look at the first sentence in the challenge description:

Add a groupBy method to Array.prototype so that elements in an array could be grouped by the result of evaluating a function on each element.

Unlike most algorithm challenges, the function we’re being asked to create here is intended to be a method on Array's prototype. Rather than writing a function that takes a targeted array as it’s first argument (and presumably the sorting function as its second), here we want to create something that can be called from individual arrays.

So how do we go about doing that? Let’s think for a few minutes about some of the other methods that we call from arrays, like push or slice. Have you ever wondered why it is that you call these types of functions directly from an array? The reason is because they exist on Array's prototype. What does that mean?

All arrays are instances of the Array object, a global object that is used to construct arrays. This fact is sometimes forgotten because the preferred way of constructing arrays is to use the array literal syntax:

var frenchies = ["Derrida", "Lacan", "Barthes"];

console.log(frenchies); // ['Derrida', 'Lacan', 'Barthes']

But remember that just like objects you can use the new keyword to build arrays as well:

var frenchies = new Array("Derrida", "Lacan", "Barthes");

console.log(frenchies); // ['Derrida', 'Lacan', 'Barthes']

The fact that arrays are objects is why if you want to test for whether or not something is an array you have to use the Array.isArray method instead of typeof:

var frenchies = ["Derrida", "Lacan", "Barthes"];

console.log(typeof frenchies); // 'object'
console.log(Array.isArray(frenchies)); // true

This isn’t a bug in JavaScript. Point typeof at an array and it will faithfully tell you that it’s an object because that’s what it is. The fact that we like to construct arrays by way of the array literal syntax instead of the new keyword doesn’t change the fact that all arrays are just instances of the Array global object.

Knowing that arrays are instances of the Array object informs us that there also exists an Array.prototype, an object from which all Array instances inherit certain properties and methods. push and slice are in fact methods on Array.prototype, and when you call them from a specific instance of Array, all your doing is invoking those methods in such a way that within their execution the value of this refers to the specific array from which they are being invoked.

There’s nothing special about Array.prototype. It’s just an object with a bunch of methods that help out with traversing and mutating instances of Array. Beause it’s a prototype object, everything stored within Array.prototype is accessible by all of the instances of Array (that’s what it means when we say that Array inherits the methods and properties of Array.prototype). This fact can come in handy if we want to write a method that can be called from any array. All we need to do is simply add the method to Array.prototype just like we would do with any other object.

Let’s do that now with our groupBy method:

var frenchies = ["Derrida", "Lacan", "Barthes"];

Array.prototype.groupBy = function() {
  // We'll write out the logic required by the challenge later.
  // For now, let's just log this to the console.
  console.log(this);
};

var brits = ["Hall", "Williams", "Eagleton"];

frenchies.groupBy(); // ["Derrida", "Lacan", "Barthes"]
brits.groupBy(); // ["Hall", "Williams", "Eagleton"]

As you can see, groupBy can now be called from any array in our code, including the ones that were instantiated before we modified Array.prototype. Neat!

*** A quick word of caution before proceeding: it’s typically frowned upon to modify any of the built-in prototypes in JavaScript, including Array.prototype, unless you have a really good reason. See this StackOverflow post for a good discussion on the issue. ***

Using reduce to solve the challenge

Now that we know how to extend the array prototype, lets go ahead and implement the groupBy function.

The challenge asks us to write groupBy so that when it’s called from an array, it will iterate through the array and apply a function (passed in as an argument to groupBy) to each element. It will return a object that has as properties the result of applying the passed in function to all of the elements, the values for which will be an array containing all of the original items that resulted in that value. And of course if no function is passed in, then the function groupBy uses should just simply return the value being considered.

We’ll cover that last bit later. For now, lets talk about how we cover the core functionality being asked.

Put broadly, the challenge is asking for a method that returns a single thing (in this case an object) that is the result of looping through an array and applying some code (the function passed to groupBy). This is a perfect use case for reduce, which I discussed in detail in the last post (go read that if you’re unfamiliar).

Since we know that we’re going to be using reduce, lets a get basic skeleton of our groupBy function written with some psuedo code for what we’re going to have reduce do:

Array.prototype.groupBy = function(fn) {
  //We call reduce on this because in this case the keyword this will refer to the array from which groupBy is being called.
  this.reduce(function(accum, item) {
    //apply fn to the item being considered and save the result. We'll call it prop.
    //Check to see if the accum object already has prop as a property. If it does, add item to the corresponding array. If it doesn't, add prop as a property with an array containing nothing but item.
    //return the updated copy so that it becomes the new accum on the next iteration.
  }, {});
};

First, we have to apply the function that’s being passed to groupBy to each item in the array. Because the returned result will become the property on the object being created by reduce, we’ll save it in a variable called prop:

var prop = fn(item);

Next, we’ll check to see if the accum object has prop as a property on it. We’ll do that using by hasOwnProperty, like this:

var prop = fn(item);

if (accum.hasOwnProperty(prop)) {
  //Add item to the array that is the value for that property
} else {
  //Add the property to accum and set the value to array containing item
}

If the property already exists, we’ll simply add the item onto the already existing array. We can do that like this:

var prop = fn(item);

if (accum.hasOwnProperty(prop)) {
  accum[prop].push(item);
} else {
  //Add the property to accum and set the value to array containing item
}

If it doesn’t exist, we’ll simply add it and set the value to an array containing just the item that we initially passed to fn. Here’s how to do that:

var prop = fn(item);

if (accum.hasOwnProperty(prop)) {
  accum[prop].push(item);
} else {
  accum[prop] = [item];
}

Last but not least, we’ll return our modified accum object so that it get’s considered during the next iteration of the reduce loop. Altogether it should look like this:

Array.prototype.groupBy = function(fn) {
return this.reduce(function(accum item) {
var prop = fn(item);

    if (accum.hasOwnProperty(prop)) {
      accum[prop].push(item);
    } else {
      accum[prop] = [item];
    }

    return accum;

}, {})
}

Okay, so what about that condition that says if no function is passed into groupBy to just return the item? Well, that’s pretty easy. Before we get to the reduce bit, we’ll just make sure that we have a default function for fn in cases when it’s groupBy is called with non-function arguments:

Array.prototype.groupBy = function(fn) {
  if (typeof fn !== "function") {
    fn = function(item) {
      return item;
    };
  }

  return this.reduce(function(accum, item) {
    var prop = fn(item);

    if (accum.hasOwnProperty(prop)) {
      accum[prop].push(item);
    } else {
      accum[prop] = [item];
    }
    console.log(accum);
    return accum;
  }, {});
};

And that’s it!

Refactoring for ES6

So how can we rewrite this code to use ES6 features?

Well, first of all we can use arrow functions and default parameters to rewrite the default function for fn:

Array.prototype.groupBy = function(fn = item => item) {
  // ...
};

We can also use Object.assign and the spread operator to change up the way we handle the accum object in our reduce function:

Array.prototype.groupBy = function(fn = item => item) {
  return this.reduce(function(accum, item) {
    var prop = fn(item);
    accum[prop] = accum.hasOwnProperty(prop) ? [...accum[prop], item] : [item];
    return accum;
  }, {});
};

Here, we employ a ternary (as opposed to the if...else syntax from above) to handle updating prop in accum. And rather than using push, we’re now using the spread operator to add the item when prop exists.