Recursive Data Structures

7. But why?

Now, we argued above that we've neatly separated the concerns by making three separate functions, instead of interleaving dividing two-dimensional squares into regions, rotating regions, and then reassembling two-dimensional squares.

But the converse side of this is that what we're doing is now a lot less efficient: We're recursing through our data structures three separate times, instead of once. And frankly, multirec was designed such that the divide function breaks things up, and the combine function puts them back together, so these concerns are already mostly separate once we use  multirec instead of a bespoke recursive function.

One reason to break the logic up into three separate functions would be if we want to do lots of different kinds of things with quadtrees. Besides rotating quadtrees, what else might we do?

Well, we might want to superimpose one image on top of another. This could be part of an image editing application, where we have layers of images and want to superimpose all the layers to derive the finished image for the screen. Or we might be implementing  Conway's Game of Life, and might want to 'paste' a pattern like a glider onto a larger universe.

Let's go with a very simple implementation: We're only editing black-and-white images, and each 'pixel' is either a ⚪️ or ⚫️. If we use two-dimensional arrays to represent our images, we need to iterate over every 'pixel' to perform the superimposition:

const superimposeCell = (left, right) =>
  (left === '⚫️' || right === '⚫️') ? '⚫️' : '⚪️';

const superimposeRow = (left, right) =>
  [...zipWith(superimposeCell, left, right)];

const superimposeArray = (left, right) =>
  [...zipWith(superimposeRow, left, right)];

const canvas =
  [ ['⚪️', '⚪️', '⚪️', '⚪️'],
    ['⚪️', '⚪️', '⚪️', '⚪️'],
    ['⚪️', '⚪️', '⚪️', '⚫️'],
    ['⚪️', '⚪️', '⚪️', '⚫️']];

const glider =
  [ ['⚪️', '⚪️', '⚪️', '⚪️'],
    ['⚪️', '⚫️', '⚪️', '⚪️'],
    ['⚫️', '⚪️', '⚪️', '⚪️'],
    ['⚫️', '⚫️', '⚫️', '⚪️']];

superimposeArray(canvas, glider)
  //=>
    ([
      ['⚪️', '⚪️', '⚪️', '⚪️'],
      ['⚪️', '⚫️', '⚪️', '⚪️'],
      ['⚫️', '⚪️', '⚪️', '⚫️'],
      ['⚫️', '⚫️', '⚫️', '⚫️']
    ])

Seems simple enough. How about superimposing a quadtree on a quadtree?