Recursive Data Structures

Read this page. In the previous unit of our course we studied recursive algorithms. Recursion is a concept that also applies to data. Here we look at recursive data structures - lists, trees, and sets. A list is a structure that consists of elements linked together. If an element is linked to more than one element, the structure is a tree. If each element is linked to two (sub) elements, it is called a binary tree. Trees can be implemented using lists, as shown in the resource for this unit. Several examples of the wide applicability of lists are presented. A link points to all the remaining links, i.e. the rest of the list or the rest of the tree; thus, a link points to a list or to a tree - this is data recursion.

The efficiency of the programming process includes both running time and size of data. This page discusses the latter for recursive lists and trees.

Lastly, why read the last section on sets? Sets are another recursive data structure and the last section 2.7.6, indicates their connection with trees, namely, a set data type can be implemented in several different ways using a list or a tree data type. Thus, the programming process includes implementation decisions, in addition, to design or algorithm decisions. Each of these types of decisions is constrained by the features of the programming language used. The decision choices, such as which data structure to use, will impact efficiency and effectiveness of the program's satisfaction of the program's requirements.

Note: You will notice an unusual use of C++ here. What the author is doing is showing how to pass a fixed-value data-structure as a calling argument.

3. Recursion, see recursion

In From Higher-Order Functions to Libraries And Frameworks, we had a look at multirec, a  recursive combinator.

function mapWith (fn) {
  return function * (iterable) {
    for (const element of iterable) {
      yield fn(element);
    }
  };
}

function multirec({ indivisible, value, divide, combine }) {
  return function myself (input) {
    if (indivisible(input)) {
      return value(input);
    } else {
      const parts = divide(input);
      const solutions = mapWith(myself)(parts);

      return combine(solutions);
    }
  }
}

With multirec, we can write functions that perform computation using divide-and-conquer algorithms. multirec handles the structure of divide-and-conquer, we just have to write four smaller functions that implement the parts specific to the problem we are solving.

In computer science, divide and conquer (D&C) is an algorithm design paradigm based on multi-branched recursion. A divide and conquer algorithm works by recursively breaking down a problem into two or more sub-problems of the same or related type, until these become simple enough to be solved directly. The solutions to the sub-problems are then combined to give a solution to the original problem.

We'll implement rotating a square using multirec. Let's begin with a naïve representation for squares, a two-dimensional array. For example, we would represent the square: 

⚪️⚪️⚪️⚪️
⚪️⚪️⚪️⚪️
⚪️⚪️⚪️⚫️
⚪️⚪️⚪️⚫️

With this array:

[['⚪️', '⚪️', '⚪️', '⚪️'],
  ['⚪️', '⚪️', '⚪️', '⚪️'],
  ['⚪️', '⚪️', '⚪️', '⚫️'],
  ['⚪️', '⚪️', '⚪️', '⚫️']]

To use multirec, we need four pieces:

  1. An indivisible predicate function. It should report whether an array is too small to be divided up. It's simplicity itself: (square) => square.length === 1.
  2. A value function that determines what to do with a value that is indivisible. For rotation, we simply return what we are given: (something) => something
  3. A divide function that breaks a divisible problem into smaller pieces. Our function will break a square into four regions. We'll see how that works below.
  4. A combine function that puts the result of rotating the smaller pieces back together. Our function will take four region squares and put them back together into a big square.

As noted, indivisible and value are trivial. We'll call our functions  hasLengthOne, and, itself: 

const hasLengthOne = (square) => square.length === 1;
const itself = (something) => something;

divide involves no more than breaking arrays into halves, and then those halves again. We'll write a divideSquareIntoRegions function for this:

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];
};

Our combine function, rotateAndCombineArrays, makes use of a little help from some functions we saw in an essay about generators:

function split (iterable) {
  const iterator = iterable[Symbol.iterator]();
  const { done, value: first } = iterator.next();

  if (done) {
    return { rest: [] };
  } else {
    return { first, rest: iterator };
  }
};

function * join (first, rest) {
  yield first;
  yield * rest;
};

function * zipWith (fn, ...iterables) {
  const asSplits = iterables.map(split);

  if (asSplits.every((asSplit) => asSplit.hasOwnProperty('first'))) {
    const firsts = asSplits.map((asSplit) => asSplit.first);
    const rests = asSplits.map((asSplit) => asSplit.rest);

    yield * join(fn(...firsts), zipWith(fn, ...rests));
  }
}

const concat = (...arrays) => arrays.reduce((acc, a) => acc.concat(a));

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);
};

Armed with hasLengthOne, itself, divideSquareIntoRegions, and rotateAndCombineArrays, we can use  multirec to write rotate:

const rotate = multirec({
  indivisible : hasLengthOne,
  value : itself,
  divide: divideSquareIntoRegions,
  combine: rotateAndCombineArrays
});

rotate(
   [['⚪️', '⚪️', '⚪️', '⚪️'],
    ['⚪️', '⚪️', '⚪️', '⚪️'],
    ['⚪️', '⚪️', '⚪️', '⚫️'],
    ['⚪️', '⚪️', '⚪️', '⚫️']]
  )
  //=>
    ([
      ['⚪️', '⚪️', '⚪️', '⚪️'],
      ['⚪️', '⚪️', '⚪️', '⚪️'],
      ['⚪️', '⚪️', '⚪️', '⚪️'],
      ['⚫️', '⚫️', '⚪️', '⚪️']
    ])

Voila!