Published
Edited
Dec 21, 2019
Insert cell
Insert cell
Insert cell
Insert cell
dot`digraph { A -> B; B -> C; A -> D }`
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Dot = typeClass('Dot', {
toDot: () => {
throw new Error();
}
})
Insert cell
Insert cell
TreeT = newType('Tree', {
Node: (key, left, right) => ({ key, left, right }),
Empty: () => {}
})
Insert cell
Insert cell
getEdges = {
const { Node, Empty } = TreeT;

// given the key of a parent node and a child node, return the "A -> B" string
const getEdgeString = (key, child) =>
match({
[Node]: ({ key: childKey }) => `${key.show()} -> ${childKey.show()}`,
[Empty]: () => {}
})(child);

// given a tree, return an array of "A -> B" strings
const getEdges = match({
[Node]: ({ key, left, right }) => {
const leftEdge = getEdgeString(key, left);
const rightEdge = getEdgeString(key, right);

const edges = [];
if (leftEdge) {
edges.push(leftEdge);
}
if (rightEdge) {
edges.push(rightEdge);
}

return edges.concat(getEdges(left), getEdges(right));
},
[Empty]: () => []
});

return getEdges;
}
Insert cell
Insert cell
Insert cell
{
const { Tree } = TreeT;

const toDot = tree => `digraph { ${getEdges(tree).join('; ')} }`;

return Dot.newInstance(Tree, { toDot });
}
Insert cell
Insert cell
{
const { Node, Empty } = TreeT;

function leaf(key) {
return Node(key, Empty(), Empty());
}

const myTree = Node('A', Node('B', leaf('C'), Empty()), leaf('D'));

return dot`${myTree.toDot()}`;
}
Insert cell
Insert cell
Insert cell
Insert cell
FracT = newType('Frac', {
F: (numerator, denominator) => [numerator, denominator]
})
Insert cell
Insert cell
{
const { Frac, F } = FracT;

const show = match({
[F]: ([n, d]) => `"${n}/${d}"`
});

Show.newInstance(Frac, { show });

// TODO this is pretty ugly
const equals = (left, right) =>
match({
[F]: ([leftNumerator, leftDenominator]) => {
return match({
[F]: ([rightNumerator, rightDenominator]) =>
leftNumerator === rightNumerator &&
leftDenominator === rightDenominator
})(right);
}
})(left);

Eq.newInstance(Frac, Eq, { equals });
}
Insert cell
Insert cell
Insert cell
generateTree = {
const { Node, Empty } = TreeT;
const { F } = FracT;

// TODO this is pretty ugly
const mediant = (left, right) =>
match({
[F]: ([leftNumerator, leftDenominator]) => {
return match({
[F]: ([rightNumerator, rightDenominator]) =>
F(
leftNumerator + rightNumerator,
leftDenominator + rightDenominator
)
})(right);
}
})(left);

function generateArray(numLevels) {
const allFractions = [F(0, 1), F(1, 0)];
const levelOrder = [];

for (let i = 0; i < numLevels; i++) {
// j += 2 because we need to skip over the newly inserted fraction each time
for (let j = 0; j < allFractions.length - 1; j += 2) {
const [left, right] = [allFractions[j], allFractions[j + 1]];
const newFraction = mediant(left, right);

allFractions.splice(j + 1, 0, newFraction);
levelOrder.push(newFraction);
}
}

return levelOrder;
}

function buildFromArray(arr, i) {
if (typeof arr[i] === 'undefined') {
return Empty();
}

const left = buildFromArray(arr, 2 * i + 1);
const right = buildFromArray(arr, 2 * i + 2);

return Node(arr[i], left, right);
}

function generateTree(numLevels) {
const levelOrder = generateArray(numLevels);
return buildFromArray(levelOrder, 0);
}

return generateTree;
}
Insert cell
dot`${generateTree(numLevels).toDot()}`
Insert cell
Insert cell
viewof numLevels = html`<input type="range" min="2" max="6" step="1">`
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell

Purpose-built for displays of data

Observable is your go-to platform for exploring data and creating expressive data visualizations. Use reactive JavaScript notebooks for prototyping and a collaborative canvas for visual data exploration and dashboard creation.
Learn more