Construct Histograms with Functional JavaScript

Recently, I accepted a coding challenge that reinforced my conviction of the superiority of functional programming, and specifically, functional JavaScript. The challenge required I take a massive piece of JSON, and from its data, abstract histograms representing fuel efficiencies — as with city and highway mileage — for a variety of vehicles. As a timed challenge, it was vital I furnish a solution requiring less time and fewer lines of code.

What I learned was that programming in the functional paradigm triumphs over more imperative approaches — even for more imperative languages such as JavaScript. And, in hindsight, I don’t believe I would have solved the problem in the allotted time period had I it from an imperative mindset.

By introducing some code samples, I intend to show you why. I hope that I might contrast an imperative approach with my own, which I — perhaps presumptuously — might hazard the consequence of the functional paradigm.

Let us begin, then, by unpacking the expectations of the coding challenge.

First off, what is a histogram? For our purposes here, the definition furnished by Wikipedia will suffice:

A histogram is an accurate representation of the distribution of numerical data.

So, in my case, I needed to traverse a large array of objects — where each object represented different vehicles by make, model, and year — in order that I might segregate the vehicles into varying bins, organized according to city mileage and highway mileage.

So, what is a bin? In the context of histograms, again according to Wikipedia, bins are:

…usually specified as consecutive, non-overlapping intervals of a variable. The bins (intervals) must be adjacent, and are often (but are not required to be) of equal size.

These intervals, per se, may also be referred to as widths. I was asked to create bins in intervals of five, as with: ... 11-15, 16-20, 21-25.

To recap, I had some JSON that looked like:

[
  {
    cityFuelEfficiency: '19',
    highwayFuelEfficiency: '27',
    ...
  },
  {
    cityFuelEfficiency: '20',
    highwayFuelEfficiency: '31',
    ...
  },
  ...
]

I, therefore, needed to take an input of type:

[{Symbol: String}]

And return something to the effect of:

{
  ...
  "15,19": 7,
  "20,24": 8,
  "25,29": 1,
  "30,34": 0,
}

So. Let’s work through this.

The first thing that occurred to me is that I would need a way to create the range of bins. Now, I could have hard-coded them, but I wanted to generate them dynamically. Ideally, we might write a function that, when provided a minimum value, a maximum value, and an interval, could produce an array of numerical ranges. Following is an annotated version of the code I used. Of particular note is that our consBins function uses recursion.

/*
 * Sum.
 * sum :: (Number, Number) → Number
 *
 * Provided two numbers, return their summation.
 **/
const sum = (numX, numY) => numX + numY

/*
 * Increment.
 * incr :: Number → Number
 *
 * Provided a number, return its value incremented by one.
 **/
const incr = num => sum(num, 1)

/*
 * Construct bins.
 * consBins :: Object → [[Number]]
 *
 * Configuration parameters:
 * min - The numerical floor from which to initialize the first interval.
 * max - The numerical ceiling by which we limit the last of intervals.
 * width - The range encompassed by each interval.
 **/
const consBins = ({min = 0, max = 100, width = 1, accum = []}) =>
  // Ensure `max` does not exceed the range of our current interval...
  sum(min, width) > max
    ? // If so, return our accumulator;
      accum
    : // Otherwise, call upon our method recursively until we fulfill our
      // predicating condition.
      consBins({
        // Increment interval, so as to preclude overlap.
        min: incr(sum(min, width)),
        // `max` and `width` remain constant.
        max,
        width,
        // Wax upon our accumulator, combining it with a new array, in which the
        // current interval is represented.
        accum: accum.concat([[min, sum(min, width)]]),
      })

Provided we have our bins, we need now ascertain the problem at hand, and by asking the right questions, we very likely can happen upon our solution.

All we want to achieve is this: we want to iterate through our list of objects, grabbing values that conform to the ranges afforded by our bins, and using these derived values, build a new map that outlines:

  • Each of our bins; and
  • The aggregate sum for all values conforming to said bins.

In the context of functional JavaScript — and, I might hazard, functional programming more generally — there are three methods that comprise something of a Holy Trinity. For our purposes here, we will be using two of them, namely, filter and reduce.

We shall employ filter to derive all values associated with a given key and that fall within range for any of our given bins. Our use of filter is the crux of this whole procedure.

As its name would suggest, when provided an array, filter returns a new array, albeit including only those items comprising the collection that pass a given test. This test — or, perhaps, more technically accurate, predicate — assumes the form of a callback function, which furnishes up to three arguments, namely element, index, and array. We invoke our callback once per each item in our array, and accordingly, our callback should return a value of either true or false, although it should be noted that any truthy return value will merit inclusion in the filtered list.

Here’s a first pass at developing such a filter:

/*
 * Filter property by minimum and maximum values.
 * filterPropByMinMax :: ([Object], Object) → Array
 *
 * From an array of objects, return only those cases where the given object
 * property falls within range of specified minimum and maximum values.
 *
 * Configuration parameters:
 * {String} key - The property to -- and by which to -- filter.
 * {String} min - The minimum value by which to filter our attribute.
 * {String} min - The maximum value by which to filter our attribute.
 **/
const filterPropByMinMax = (arr, {key = '', min = '0', max = '100'}) =>
  arr.filter(
    // The numerical values encompassed by our JSON list assume the form of
    // strings; hence, we need abstract their numerical values via `parseInt`.
    // Our callback will return `true` provided the item's value is greater than
    // or equal to our minimum _and_ less than or equal to our maximum.
    item => parseInt(item[key], 10) >= min && parseInt(item[key], 10) <= max
  )

From here, we shall use reduce to construct our representation of the histogram we mean to delineate. Such is to say, we we have used filter to extract the data, and we will use reduce to present the data.

An aside: despite its nomenclature, reduce is an incredibly powerful means by which to build — or contract — virtually anything. Of map, filter, and reduce, I would contend that reduce is the most abstract of the three, as one very easily could implement map or filter by way of reduce, though I am not certain the inverse is true. Furthermore, although all three methods are meant to act upon a list as input, map and filter are designed to return new collections; reduce, however, can be leveraged to return virtually any data type that can accumulate, be it a list, an object, string, or number.

We know we love reduce, so let’s try our hand at using it:

/*
 * Construct histogram object.
 * consHistObj :: (Array, [[Number]]) → String → Object
 **/
const consHistObj = (arr = [], bins = []) => (key = '') =>
  // For each of the nested arrays within our `bins` list...
  bins.reduce(
    (accum, currVal) => ({
      // Build upon our accumulator, which we initialize as an empty object...
      ...accum,
      // And where each entry is an object, whereof the the key shall represent
      // the minimum and maximum values encompassed by each bin (e.g., `15,19`),
      // and whereof the value shall delineate all vehicles encompassed by such
      // bin. We retrieve such values by of `filterPropByMinMax`...
      [currVal]: filterPropByMinMax(arr, {
        key,
        min: currVal[0],
        max: currVal[1],
        // And we calculate a total by way of `Array.prototype.length`.
      }).length,
    }),
    {}
  )

Now it is time we pull all of our functions together.

We might first observe that consHistObj expects one of its supplied arguments to be an array of bins, so let us devise a reusable utility that pre-loads consHistObj with a call to consBins:

/*
 * Construct histogram object provided bins.
 * consHistObjWithBins :: (Object → [Object] → String) → Object
 *
 * Configuration parameters:
 * {Number} min - The minimum value by which to filter our attribute.
 * {Number} min - The maximum value by which to filter our attribute.
 * {Number} width - The range encompassed by each interval.
 **/
const consHistObjWithBins = (arr = [], {min = 0, max = 100, width = 1}) => (
  key = ''
) => consHistObj(arr, consBins({min, max, width}))(key)

It is important to note that consHistObjWithBins is in place to simply return a new function. We will create one more such utility, which we will supply hard-coded arguments for use by consHistObjWithBins:

/*
 * Construct mileage histogram.
 *
 * NB: `getData()` is the function we call, so as to pull in the massive piece
 * of JSON we need process.
 **/
const consMileageHist = (key = '') =>
  consHistObjWithBins(getData(), {min: 0, max: 50, width: 4})(key)

And now — for the finale — we can can call our helper function consMilageHist, and in each instance supply our desired keys:

const consCityMileageHist = () => consMileageHist('cityFuelEfficiency')
const consHighwayMileageHist = () => consMileageHist('highwayFuelEfficiency')

console.log('City mileage', consCityMileageHist())
console.log('Highway mileage', consHighwayMileageHist())

Let me know what you think. You can see the source code for these code samples here.

If you love making great software, maybe you’ll love working with us.

At Revelry, we’ve created many open source tools and we’d love for you to collaborate with us. And, we’re transparent about how we work. For a look at how we build digital products, check out
Lean Agile Processes and Tools.

Revelry is hiring! Check out our open positions.

Join in the conversation: follow us on Twitter or connect with us on LinkedIn!