Recursive Data Structures

4. Accidental complexity

Rotating a square in this recursive manner is intellectually stimulating, but our code is encumbered with some accidental complexity. Here's a flashing strobe-and-neon hint of what it is:

const firstHalf = (array) => array.slice(0, array.length / 2);
const secondHalf = (array) => array.slice(array.length / 2);

const divideSquareIntoRegions = (square) => {
  const upperHalf = firstHalf(square);
  const lowerHalf = secondHalf(square);

  const upperLeft = upperHalf.map(firstHalf);
  const upperRight = upperHalf.map(secondHalf);
  const lowerRight = lowerHalf.map(secondHalf);
  const lowerLeft= lowerHalf.map(firstHalf);

  return [upperLeft, upperRight, lowerRight, lowerLeft];
};

divideSquareIntoRegions is all about extracting region squares from a bigger square, and while we've done our best to make it readable, it is rather busy. Likewise, here's the same thing in rotateAndCombineArrays:

const rotateAndCombineArrays = ([upperLeft, upperRight, lowerRight, lowerLeft]) => {
  // rotate
  [upperLeft, upperRight, lowerRight, lowerLeft] =
    [lowerLeft, upperLeft, upperRight, lowerRight];

  // recombine
  const upperHalf = [...zipWith(concat, upperLeft, upperRight)];
  const lowerHalf = [...zipWith(concat, lowerLeft, lowerRight)];

  return concat(upperHalf, lowerHalf);
};

rotateAndCombineArrays is a very busy function. The core thing we want to talk about is actually the rotation: Having divided things up into four regions, we want to rotate the regions. The zipping and concatenating is all about the implementation of regions as arrays.

We can argue that this is necessary complexity, because squares are arrays, and that's just what we programmers do for a living, write code that manipulates basic data structures to do our bidding.

But what if our implementation wasn't an array of arrays? Maybe divide and combine could be simpler? Maybe that complexity would turn out to be unnecessary after all?