Test-first

Master the art of Test-driven Development (TDD)

Behind the scenes of filter, map & reduce

Have you ever faced coding challenges like this one:

Write a function that returns the amount of all fatal error log messages for a given date.

Here’s an example log file:

D, [2019-03-17T03:13:44.907Z #27783] DEBUG a88a272d-dc18-4553-b4da-5208b2c53467: calculating open-source application
D, [2019-03-17T11:16:04.171Z #21244] DEBUG 97721470-e329-421e-8599-10772d8dc6e4: hacking cross-platform monitor
W, [2019-03-17T11:59:40.232Z #2355] WARN 1e56556c-c292-43bd-a8e5-a84c32d99bbb: connecting online bandwidth
F, [2019-03-17T20:20:57.106Z #27857] FATAL 962c2c0d-180e-4c5a-b81d-89dc085d6a31: bypassing primary monitor
E, [2019-03-17T02:58:20.885Z #72082] ERROR 7505a518-d650-43ea-a53a-2d345236ce4e: generating 1080p driver
...

Or did you face a problem like the following one:

Display a red bubble that shows the amount of all unread messages.

Here’s an example of the data returned from the API:

{
  "messages": [
    { "contact": "John", "text": "Hi!", "readTime": null },
    { "contact": "Jane", "text": "LOL", "readTime": "2020-01-02T14:35:02+01:00" },
    { "contact": "Jim", "text": "Here's the video: http://youtu.be/7f3a8d", "readTime": null },
    { "contact": "Jane", "text": "Ok, let's do it!", "readTime": "2020-01-02T14:36:05+01:00" },
    { "...": "..." }
  ]
}

Many companies love to incorporate coding challenges in their interview process. Often, junior developers start to sweat when facing a task like the above ones. Especially when under time pressure.

I don’t think that failing to solve coding challenges is a good indicator of your skill as a developer. Yet, your life as developer will involve solving these kinds of problems from time to time.

So if you are a bootcamp graduate or a lucky junior developer who’s found their first job, keep on reading. I want to show you, how you can solve these kinds of problems faster, with more confidence, and less code.

My Name is Bond, James Bond

Imagine, your job is to write a function that identifies when a Bond actor retired as James Bond.

Sean Connery for instance retired in 1983.

Here is an unsorted list of all James Bond movies:

[
  { title: 'You Only Live Twice', year: 1967, actor: 'Sean Connery' },
  { title: 'The Spy Who Loved Me', year: 1977, actor: 'Roger Moore' },
  { title: 'License to kill', year: 1989, actor: 'Timothy Dalton' },
  { title: 'Live and Let Die', year: 1973, actor: 'Roger Moore' },
  { title: 'Thunderball', year: 1965, actor: 'Sean Connery' },
  { title: 'Never say never again', year: 1983, actor: 'Sean Connery' },
  { title: 'Goldfinger', year: 1964, actor: 'Sean Connery' },
  { title: 'Moonraker', year: 1979, actor: 'Roger Moore' },
  { title: 'No Time to Die', year: 2020, actor: 'Daniel Craig' },
  { title: 'For your eyes only', year: 1981, actor: 'Roger Moore' },
  { title: 'Diamonds are Forever', year: 1971, actor: 'Sean Connery' },
  { title: 'A view to a kill', year: 1985, actor: 'Roger Moore' },
  { title: 'Die another day', year: 2002, actor: 'Pierce Brosnan' },
  { title: 'Casino Royale', year: 2006, actor: 'Daniel Craig' },
  { title: 'The world is not enough', year: 1999, actor: 'Pierce Brosnan' },
  { title: 'Octopussy', year: 1983, actor: 'Roger Moore' },
  { title: 'Quantum of solace', year: 2008, actor: 'Daniel Craig' },
  { title: 'On Her Majesty's Secret Service', year: 1969, actor: 'George Lazenby' },
  { title: 'GoldenEye', year: 1995, actor: 'Pierce Brosnan' },
  { title: 'Tomorrow never dies', year: 1997, actor: 'Pierce Brosnan' },
  { title: 'Skyfall', year: 2012, actor: 'Daniel Craig' },
  { title: 'The living daylights', year: 1987, actor: 'Timothy Dalton' },
  { title: 'Casino Royale', year: 1967, actor: 'David Niven' },
  { title: 'Dr. No', year: 1962, actor: 'Sean Connery' },
  { title: 'The Man with the Golden Gun', year: 1974, actor: 'Roger Moore' },
  { title: 'From Russia with Love', year: 1963, actor: 'Sean Connery' },
  { title: 'Spectre', year: 2015, actor: 'Daniel Craig' },
]

We need to develop a function called whenDidBondActorRetire. It will take two arguments. movies is an array with Bond movie objects like the above. actor is of type string and identifies the actor.

function whenDidBondActorRetire(movies, actor) {
  // ...
}

The function will return a single number – the year of the last movie, the given actor performed in.

Here is a Jest test suit, testing the function whenDidBondActorRetire:

// 007.test.js
const whenDidBondActorRetire = require('./007')

describe('whenDidBondActorRetire', () => {
  it('returns year of movie when there is only one matching movie', () => {
    const movies = [
      { title: 'Title 1', year: 1901, actor: 'John Doe' }
    ]
    expect(whenDidBondActorRetire(movies, 'John Doe')).toBe(1901)
  })

  it('returns year of last movie when there are many matching movies', () => {
    const movies = [
      { title: 'Title 1', year: 1901, actor: 'John Doe' },
      { title: 'Title 2', year: 1902, actor: 'John Doe' },
    ]
    expect(whenDidBondActorRetire(movies, 'John Doe')).toBe(1902)
  })

  it('returns year of matching movie when there is a matching and non-matching movie', () => {
    const movies = [
      { title: 'Title 1', year: 1901, actor: 'John Doe' },
      { title: 'Title 2', year: 1902, actor: 'Jim Doe' },
    ]
    expect(whenDidBondActorRetire(movies, 'John Doe')).toBe(1901)
  })

  it('returns rating of newest matching movie when there are matching and non-matching movies', () => {
    const movies = [
      { title: 'Title 1', year: 1901, actor: 'John Doe' },
      { title: 'Title 2', year: 1902, actor: 'Jim Doe' },
      { title: 'Title 3', year: 1903, actor: 'John Doe' },
      { title: 'Title 4', year: 1904, actor: 'Jane Doe' },
    ]
    expect(whenDidBondActorRetire(movies, 'John Doe')).toBe(1903)
  })
})

Test Setup

This article is not about test-driven development. I will cover that another time. But, if you’re interested in running the test suite, follow these steps:

  1. Create a new NPM project
    mkdir bond
cd bond
npm init
# use default answers for all questions by hitting enter
  2. Install the Jest testing library as development dependency
    npm install --save-dev jest
  3. Setup the NPM test script in package.json
    {
  "...": "...",
  "scripts": {
    "...": "...",
    "test": "jest"
  }
}
  4. Copy the above test file code into a file called 007.test.js
  5. Run the tests
    npm test

The tests will fail. There is no file with an implementation yet.

Imperative Solution

Here is a potential implementation of whenDidBondActorRetire that satisfies all the above tests:

// 007.js
function whenDidBondActorRetire(movies, actor) {
  let lastYear = 0
  for (let movie of movies) {
    if (movie.actor !== actor) {
      continue
    }
    if (movie.year > lastYear) {
      lastYear = movie.year
    }
  }
  return lastYear
}

module.exports = whenDidBondActorRetire

Create the file 007.js and run the tests again.

The solution starts off with initializing lastYear with 0 (line 3). As we check one movie after another, we will use lastYear to keep track of the movie with the latest year so far. Initializing lastYear with a very low number (here: 0), will ensure that the first processed movie becomes the latest movie.

The function uses then a for...of loop to check every movie in the list of movies. When the actor in a movie does not match the given actor, we will skip the movie with continue (line 6). If the actor in a movie matches the given actor, we will compare the movie’s year with the last known lastYear (line 8). If the current movie was released later, we will remember the current movie’s year instead (line 9).

After having processed all movies, we return lastYear. It now contains the year of the last Bond movie for the given actor.

If you can provide a solution like the above one, look into a mirror, smile and clap yourself on the back! You mastered procedural programming and can call yourself a programmer!

This solution uses an imperative or algorithmic approach. Statements (e.g. return) and control flow (e.g. for...of) change the programs state (here: lastYear).

Handling state in software always comes at a cost. You can say, the more state a program has, the more complex it is. We should try to avoid state wherever possible.

Functional Solution

Functional programming provides an alternative programming approach. It focuses on creating pure functions without side effects. Functional programming also helps avoiding state. And when there is no state, then there is no need for state manipulation.

With the functions of JavaScript’s Array it is possible to provide a functional solution to the above problem:

// 007.js
const whenDidBondActorRetire = (movies, actor) => movies
  .filter(movie => movie.actor === actor)
  .map(movie => movie.year)
  .reduce((last, year) => year > last ? year : last)

module.exports = whenDidBondActorRetire

This functional solution is equivalent to the first imperative solution. It satisfies all the tests. Try it out and run the tests again.

First, only movies are filtered where the Movie’s actor matches the given actor.

Then, the remaining list of movies is mapped (transformed) into a list of years.

And finally, the list of years is reduced to one year – the largest year.

Comparison

It’s ok if you struggle to comprehend the functional solution at the moment. But what do you notice when comparing it with the imperative solution?

First of all, notice that the functional solution is shorter; 7 instead of 15 lines of code.

You might even say that the functional solution looks cleaner. As a reader of the code, the intent of the program is easier to grasp. Kick irrelevant movies out, focus on the years, find latest year.

And there is no state manipulation happening in the functional solution. That means the solution is less complex.

You as a developer will directly benefit from functional programming:

  • You will have to write less code.
  • You won’t have to mess around with loop variables like i.
  • You won’t have to keep track of the final result (e.g. lastYear).
  • And your solution will be easier to understand and to adjust as you go along.

All this will make you faster.

So let’s dig in and start dissecting the first Array function: filter

Filter

Data sets often contain data that is wrong, incomplete or not what we are looking for. Sometimes we are only interested in a subset of an array where the elements have certain features.

Filtering Long Words

Here is an example of using Array‘s filter in a function filterLongWords. It filters words that contain more than 5 characters.

Here’s the test:

// filterLongWords.test.js
const filterLongWords = require('./filterLongWords')

describe('filterLongWords', () => {
  it('keeps words longer than 5 characters', () => {
    const words = [ 'short', 'longer', 'shrt', 'longest' ]
    const longWords = filterLongWords(words)
    expect(longWords).toEqual([ 'longer', 'longest' ])
  })
})

Here’s a traditional (imperative) implementation:

// filterLongWords.js
function filterLongWords(words) {
  let filteredWords = []
  for (let word of words) {
    if (word.length > 5) {
      filteredWords.push(word)
    }
  }
  return filteredWords
}

module.exports = filterLongWords

And here is a more elegant (functional) implementation that uses filter:

// filterLongWords.js
function filterLongWords(words) {
  return words.filter(word => word.length > 5)
}

module.exports = filterLongWords

How does filter work?

The filter function expects a callback. It calls the callback for every array element. filter passes each array element to the callback as parameter.

The filter callback is expected to make a decision. It decides whether to include the array element in the resulting array or whether to kick it out.

Provide a callback that returns something truthy and the element stays. Return something falsy and the array element will not be part of the resulting array.

Filter
Filter

In the code example above, every word is tested for its length. If a length is larger than 5, the condition evaluates to true and the word stays.

Notice how I use plural (words) and singular (word) to make clear what is the array and what is the array element. Always try to come up with good variable and parameter names. Your fellow developers will appreciate the effort.

The worst name for an array is array.

Filtering arrays results in a new array. The new array is either shorter than the original array (some elements didn’t make it) or has the same length (no element was kicked out).

A filter callback actually receives two more parameters. Besides the element, there will be i and elements. These extra parameters can be useful. But most of the time they are not needed and thus skipped (not mentioned).

const filteredArray = elements.filter((element, i, elements) => {
  return /* truthy|falsy */
})

A look inside filter

But how does one end up with an Array function like filter?

When comparing solutions to similar problems, a pattern emerges.

Solution 1:

function filterLongWords(words) {
  let filteredWords = []
  for (let word of words) {
    if (word.length > 5) {
      filteredWords.push(word)
    }
  }
  return filteredWords
}

Solution 2:

function filterBondMoviesByActor(movies, actor) {
  let filteredMovies = []
  for (let movie of movies) {
    if (movie.actor === actor) {
      filteredMovies.push(movie)
    }
  }
  return filteredMovies
}

The highlighted sections look very similar. The high-level algorithm is basically the same:

  • start with an empty array
  • loop over every array element of the original array
    • make a decision for the current array element
    • if the condition is truthy
      • add element to filtered array
  • return the final filtered array

The only thing that changes is the criterion that decides whether an array element is relevant or not.

function filter(elements) {
  let filteredElements = []
  for (let element of elements) {
    if (filter condition) {
      filteredElements.push(element)
    }
  }
  return filteredElements
}

We are facing two concerns – the high-level algorithm and the decision making process.

If we separate the two concerns, we can write the high-level algorithm in a more generic way that suits all filter operations.

function filter(elements, isRelevant) {
  const filteredElements = []
  for (let element of elements) {
    if (isRelevant(element)) {
      filteredElements.push(element)
    }
  }
  return filteredElements
}

The filter criterion isRelevant is a callback function. It will be called for every array element. The filter function does not know how isRelevant decides. And it doesn’t have to as long as isRelevant returns something truthy or falsy so that the if statement can work.

As mentioned earlier, Array‘s filter method also passes the index and the whole array to the callback. Furthermore, an Array knows already its elements. There’s no need to pass them to the filter function.

Here’s how Array‘s filter method might look like under the hood:

class Array {
  constructor(elements) {
    this.elements = elements
  }
  // ...
  filter(isRelevant) {
    const filteredElements = []
    for (let i = 0; i < this.elements.length; i++) {
      if (isRelevant(element, i, elements)) {
        filteredElements.push(element)
      }
    }
    return filteredElements
  }
}

isRelevant is a callback. It represents a criterion that decides whether an array element should become part of the filtered array or not.

filter loops over all array elements and calls the provided isRelevant callback for each array element. When isRelevant returns truthy for a given element, the element will be pushed into the new array. And when isRelevant returns falsy, the given element will be ignored.

Remember, you are the one who calls filter. And you are the one who provides the callback that internally is called isRelevant. In case of filtering long words, isRelevant becomes word => word.length > 5. And in case of bond movies it becomes movie => movie.actor === actor.

What’s next?

filter, map and reduce are the 3 most popular Array functions. There are other useful functions like some and every.

Learning how to use these functions is well worth the effort. And going forward you will be able to avoid writing loop statements altogether.

So don’t miss part two of this look behind the scenes of filter, map and reduce. There, I will dissect map.

See you around,
-David

Connect

Discover

www.cultivate.software

Legal

Imprint  ·  Privacy Policy  ·  Cookie Policy