Nesting Structure Comparison

This post is written as a set of Literate Commits. The goal of this style is to show you how this program came together from beginning to end.

Each commit in the project is represented by a section of the article. Click each section's header to see the commit on Github, or check out the repository and follow along.

Written by Pete Corey on Aug 3, 2016.

Project Setup

The goal of this code kata is to implement a method on the Array prototype that determines when the current array and another array provided as input have the same nested structure.

To get a better idea of what we mean by “nested structure”, these calls to sameStructureAs would return true:


[ 1, 1, 1 ].sameStructureAs( [ 2, 2, 2 ] );
[ 1, [ 1, 1 ] ].sameStructureAs( [ 2, [ 2, 2 ] ] );

And these would return false:


[ 1, [ 1, 1 ] ].sameStructureAs( [ [ 2, 2 ], 2 ] );
[ 1, [ 1, 1 ] ].sameStructureAs( [ [ 2 ], 2 ] );

We’ll start by initializing our project with a basic Babel and Mocha setup.

.babelrc

+{ + "presets": ["es2015"] +}

.gitignore

+node_modules/

package.json

+{ + "main": "index.js", + "scripts": { + "test": "mocha ./test --compilers js:babel-register" + }, + "dependencies": { + "babel-preset-es2015": "^6.9.0", + "babel-register": "^6.9.0", + "chai": "^3.5.0", + "lodash": "^4.12.0", + "mocha": "^2.4.5" + } +}

test/index.js

+import { expect } from "chai"; + +describe("index", function() { + + it("works"); + +});

Extending Array

The simplest test we can write to get going is to compare the structure of an empty array to another empty array:


expect([].sameStructureAs([])).to.be.true;

After writing this test, our test suite fails. A naively simple way to get our suite back into the green is to define a very simple sameStructureAs function on the Array prototype that always returns true.

index.js

+Array.prototype.sameStructureAs = function(other) { + return true; +}

test/index.js

+import "../"; import { expect } from "chai"; -describe("index", function() { +describe("sameStructureAs", function() { - it("works"); + it("works", () => { + expect([].sameStructureAs([])).to.be.true; + });

Comparing Types

Next, we’ll add our first real test. We expect an array who’s first element is a Number to have a different structure than an array who’s first element is an Array:


expect([1].sameStructureAs([[]])).to.be.false;

The most obvious way to make this test pass is to check the types of the first element of each array. If both first elements are arrays, or both are not arrays, we’ll return true. Otherwise, we’ll return false.

index.js

+import _ from "lodash"; + Array.prototype.sameStructureAs = function(other) { - return true; + if (_.isArray(this[0]) && _.isArray(other[0])) { + return true; + } + else if (!_.isArray(this[0]) && !_.isArray(other[0])) { + return true; + } + return false; }

test/index.js

... expect([].sameStructureAs([])).to.be.true; + expect([1].sameStructureAs([[]])).to.be.false; });

Generalizing

Now that we have our base case figured out, it’s time to generalize and check the structure of arrays of any length.

To guide us on this process, we added two new tests:


expect([[], []].sameStructureAs([[], []])).to.be.true;
expect([[], 1].sameStructureAs([[], []])).to.be.false;

The general idea is that we’ll want to compare each element of this and other using the same kind of structural comparison we previously wrote. Lodash’s _.zipWith function is a great way of comparing array elements like this:


let comparisons = _.zipWith(this, other, (a, b) => {
    ...
});

Now, comparisons will hold a list of true/false values representing whether the values at that position shared the same structure.

We can use _.every to return true if all comparisons are true, or false otherwise.

During this process, we also did some refactoring of our comparison code, just to clean things up a bit:


let bothArrays = _.isArray(a) && _.isArray(b);
let bothNot = !_.isArray(a) && !_.isArray(b);
return bothArrays || bothNot;

index.js

... Array.prototype.sameStructureAs = function(other) { - if (_.isArray(this[0]) && _.isArray(other[0])) { - return true; - } - else if (!_.isArray(this[0]) && !_.isArray(other[0])) { - return true; - } - return false; + let comparisons = _.zipWith(this, other, (a, b) => { + let bothArrays = _.isArray(a) && _.isArray(b); + let bothNot = !_.isArray(a) && !_.isArray(b); + return bothArrays || bothNot; + }); + return _.every(comparisons); }

test/index.js

... expect([1].sameStructureAs([[]])).to.be.false; + expect([[], []].sameStructureAs([[], []])).to.be.true; + expect([[], 1].sameStructureAs([[], []])).to.be.false; });

Getting Recursive

So far we’ve only handled a single layer of structure. However, the goal of sameStructureAs is to compare the nested structures of our inputs. Consider these examples:


expect([[], [1]].sameStructureAs([[], [1]])).to.be.true;
expect([[], [1]].sameStructureAs([[], [[]]])).to.be.false;

While at first glance this seems to add a lot of complexity, there’s actually a very elegant solution to this problem. When we find two matching arrays in our inputs, all we need to do is ensure that the contents of those arrays have the same structure:


return (bothArrays && a.sameStructureAs(b)) || bothNot;

This recursive call into sameStructureAs will handle any nested depths that we can throw at it (as long as we don’t blow our stack).

index.js

... let bothNot = !_.isArray(a) && !_.isArray(b); - return bothArrays || bothNot; + return (bothArrays && a.sameStructureAs(b)) || bothNot; });

test/index.js

... expect([[], 1].sameStructureAs([[], []])).to.be.false; + expect([[], [1]].sameStructureAs([[], [1]])).to.be.true; + expect([[], [1]].sameStructureAs([[], [[]]])).to.be.false; });

Bug Fixes

Submitting our solution revealed a few bugs in our solution. The first bug can be pointed out with this failing test:


expect([].sameStructureAs(1)).to.be.false;

We were assuming that other would be an array. Unfortunately in this case, other is 1, which causes _.zipWith to return an empty array.

We can fix this bug by adding an upfront check asserting that other is an Array.

After fixing that issue, another bug reared its ugly head:


expect([1].sameStructureAs([1, 2])).to.be.false;

In the last iteration of _.zipWith, a was undefined and b was 2. While checking if both of these values were not arrays returned true, we didn’t check if both values actually existed.

The fix for this bug is to check that both a and b are not undefined:


let bothDefined = !_.isUndefined(a) && !_.isUndefined(b);
let bothNot = bothDefined && !_.isArray(a) && !_.isArray(b);

With those fixes, out suite flips back to green!

index.js

... Array.prototype.sameStructureAs = function(other) { + if (!_.isArray(other)) { + return false; + } let comparisons = _.zipWith(this, other, (a, b) => { let bothArrays = _.isArray(a) && _.isArray(b); - let bothNot = !_.isArray(a) && !_.isArray(b); + let bothDefined = !_.isUndefined(a) && !_.isUndefined(b); + let bothNot = bothDefined && !_.isArray(a) && !_.isArray(b); return (bothArrays && a.sameStructureAs(b)) || bothNot;

test/index.js

... expect([[], [1]].sameStructureAs([[], [[]]])).to.be.false; + expect([].sameStructureAs(1)).to.be.false; + expect([1].sameStructureAs([1, 2])).to.be.false; });

Final Refactor

To make things a little more readable, I decided to move the undefined check into a guard, rather than including it withing the comparison logic of our zipWith function.

After implementing this refactor, our tests still pass.

index.js

... let comparisons = _.zipWith(this, other, (a, b) => { + if (_.isUndefined(a) || _.isUndefined(b)) { + return false; + } let bothArrays = _.isArray(a) && _.isArray(b); - let bothDefined = !_.isUndefined(a) && !_.isUndefined(b); - let bothNot = bothDefined && !_.isArray(a) && !_.isArray(b); + let bothNot = !_.isArray(a) && !_.isArray(b); return (bothArrays && a.sameStructureAs(b)) || bothNot;

Final Thoughts

Looking at the other submitted solutions to this kata, I realize that it’s a fairly interesting problem with lots of possible solutions. There are shorter solutions out there, but I like ours for its readability.

Brevity doesn’t always lead to better code. This is an important lesson that has taken me many years to fully appreciate.

Be sure to check out the final solution on GitHub. If you spot a bug or see a place ripe for improvement, be sure to submit a pull request!