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.
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!