Recursive Data Structures
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:
- 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
. - 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
- 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. - 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!