Published
Edited
Nov 17, 2020
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
prototype_of_finger_tree = {
return {
empty: {}, // empty tree
single: v1 => {}, // tree with single value
tree: (left, subtree, right) => {}, // Full tree

digit1: v1 => {}, // one value
digit2: (v1,v2) => {}, // two values
digit3: (v1,v2,v3) => {}, // three values
digit4: (v1,v2,v3,v4) => {}, // four values

node2: (v1, v2) => {}, // node with two values
node3: (v1, v2, v3) => {} // node with three values
}
}
Insert cell
Insert cell
FingerTree0 = {
return {
empty: ({toString: () => "<>"}),
single: a => ({toString: () => `single(${a})`}), // tree with single value
tree: (left, subtree, right) => ({toString: () => `tree(${left},${subtree},${right})`}), // Full tree

digit1: a => ({toString: () => `[${a}]`}), // 1 leaf
digit2: (a,b) => ({toString: () => `[${a},${b}]`}), // 2 leaves
digit3: (a,b,c) => ({toString: () => `[${a},${b},${c}]`}), // 3 leaves
digit4: (a,b,c,d) => ({toString: () => `[${a},${b},${c},${d}]`}), // 4 leaves

node2: (a,b) => ({toString: () => `node(${a},${b})`}), // two branches
node3: (a,b,c) => ({toString: () => `node(${a},${b},${c})`}) // three branches
}
}

Insert cell
{
const ft = FingerTree0;
return ft.tree(ft.digit2(11,12),ft.single(20), ft.digit1(30)) + '\n' +
ft.tree(ft.digit3('a', 'b', 'c'),
ft.tree(ft.digit1(ft.node2('d','e')),
ft.single(ft.node3('f','g','h')),
ft.digit2(ft.node2('i','j'),ft.node3('k','l','m'))),
ft.digit1('n'))
}
Insert cell
Insert cell

FingerTreeWithCons = {
var digit1, digit2, digit3, digit4, empty, single, tree;
const node2 = FingerTree0.node2;
const node3 = FingerTree0.node3;
single = a => ({
toString: () => `single(${a})`,
cons: b => tree(digit1(b), empty, digit1(a))
});

empty = {toString: () => "<>", cons: single};

tree = (left, subtree, right) => ({
toString: () => `tree(${left},${subtree},${right})`,
cons: a => left.cons(a)(subtree, right)
});

digit1 = a => ({
toString: () => `[${a}]`,
cons: b => (subtree, right) => tree(digit2(b,a), subtree, right)
});
digit2 = (a,b) => ({
toString: () => `[${a},${b}]`,
cons: c => (subtree, right) => tree(digit3(c,a,b), subtree, right)
});

digit3 = (a,b,c) => ({
toString: () => `[${a},${b},${c}]`,
cons: d => (subtree, right) => tree(digit4(d,a,b,c), subtree, right)
});

digit4 = (a,b,c,d) => ({
toString: () => `[${a},${b},${c},${d}]`,
cons: e => (subtree, right) => tree(digit2(e,a), subtree.cons(node3(b,c,d)), right)
});
return {
empty: empty,
single: single,
tree: tree,
digit1: digit1,
digit2: digit2,
digit3: digit3,
digit4: digit4,
node2: node2,
node3: node3,
}
}


Insert cell
Insert cell
{
const ft = FingerTreeWithCons;
function build(n) {
return n === 0 ? ft.empty : build(n-1).cons(n);
}

for (var i = 0; i < 12; i++) {
yield Promises.delay(2000, (i > 0? ('\nappending ' + i + ' to ' + build(i-1) + ' =>\n ') : '') + build(i))
}
}
Insert cell
Insert cell

FingerTreeWithSnoc = {
var digit1, digit2, digit3, digit4, empty, single, tree;
const node2 = FingerTree0.node2;
const node3 = FingerTree0.node3;

tree = (left, subtree, right) => ({
st: subtree,
toString: () => `tree(${left},${subtree},${right})`,
snoc: a => (right.snoc)(a)(left, subtree)
});
single = a => ({
toString: () => `single(${a})`,
snoc: b => (tree(digit1(a), empty, digit1(b)))
});
empty = {toString: () => "<>", snoc: single};

digit1 = a => ({
toString: () => `[${a}]`,
snoc: b => (left, subtree) => tree(left, subtree, digit2(a,b))
});
digit2 = (a,b) => ({
toString: () => `[${a},${b}]`,
snoc: c => (left, subtree) => tree(left, subtree, digit3(a,b,c))
});

digit3 = (a,b,c) => ({
toString: () => `[${a},${b},${c}]`,
snoc: d => (left, subtree) => tree(left, subtree, digit4(a,b,c,d))
});

digit4 = (a,b,c,d) => ({
toString: () => `[${a},${b},${c},${d}]`,
snoc: e => (left, subtree) => tree(left, subtree.snoc(node3(a,b,c)), digit2(d,e))
});
return {
empty: empty,
single: single,
tree: tree,
digit1: digit1,
digit2: digit2,
digit3: digit3,
digit4: digit4,
node2: FingerTree0.node2,
node3: FingerTree0.node3,
}
}
Insert cell
Insert cell
{
const ft = FingerTreeWithSnoc;
const build = n => n === 0 ? ft.empty : build(n-1).snoc(n);

var samples = "\n";
for (var i = 0; i < 18; i++) {
samples += (i > 0? ('snoc ' + i + ': ') : '') + build(i) + "\n";
}
return samples;
}
Insert cell
Insert cell
FingerTreeWithFoldl = {
const foldl = (op, z) => v => (v.foldl === undefined) ? op(z,v) : v.foldl(op, z);
var digit1, digit2, digit3, digit4, node2, node3, empty, single, tree;
tree = (left, subtree, right) => ({
st: subtree,
toString: () => `tree(${left},${subtree},${right})`,
cons: a => (left.cons)(a)(subtree, right),
snoc: a => (right.snoc)(a)(left, subtree),
foldl: function(op,z) {
let folder = foldl(op, z)
let leftSum = folder(left)
let rightSum = folder(right)
let midSum = folder(subtree)
return op(op(op(z, leftSum), midSum), rightSum) // expecting associativity of the monoid
}
});
single = a => ({
toString: () => `single(${a})`,
cons: b => (tree(digit1(b), empty, digit1(a))),
snoc: b => (tree(digit1(a), empty, digit1(b))),
foldl: (op,z) => foldl(op,z)(a)
});
empty = {
toString: () => "<>",
cons: single,
snoc: single,
foldl: (op,z) => z
};

digit1 = a => ({
toString: () => `[${a}]`,
cons: b => (subtree, right) => tree(digit2(b,a), subtree, right),
snoc: b => (left, subtree) => tree(left, subtree, digit2(a,b)),
foldl: (op,z) => foldl(op,z)(a)
});
digit2 = (a,b) => ({
toString: () => `[${a},${b}]`,
cons: c => (subtree, right) => tree(digit3(c,a,b), subtree, right),
snoc: c => (left, subtree) => tree(left, subtree, digit3(a,b,c)),
foldl: (op,z) => op(foldl(op,z)(a),foldl(op,z)(b))
});

digit3 = (a,b,c) => ({
toString: () => `[${a},${b},${c}]`,
cons: d => (subtree, right) => tree(digit4(d,a,b,c), subtree, right),
snoc: d => (left, subtree) => tree(left, subtree, digit4(a,b,c,d)),
foldl: (op,z) => op(op(foldl(op,z)(a),foldl(op,z)(b)),foldl(op,z)(c))
});

digit4 = (a,b,c,d) => ({
toString: () => `[${a},${b},${c},${d}]`,
cons: e => (subtree, right) => tree(digit2(e,a), subtree.cons(node3(b,c,d)), right),
snoc: e => (left, subtree) => tree(left, subtree.snoc(node3(a,b,c)), digit2(d,e)),
foldl: (op,z) => op(op(op(foldl(op,z)(a),foldl(op,z)(b)),foldl(op,z)(c)),foldl(op,z)(d))
});

node2 = (a,b) => ({
toString: () => `node(${a},${b})`,
foldl: (op,z) => op(op(z,foldl(op,z)(a)),foldl(op,z)(b))
});
node3 = (a,b,c) => ({
toString: () => `node(${a},${b},${c})`,
foldl: (op,z) => op(op(op(z,foldl(op,z)(a)),foldl(op,z)(b)),foldl(op,z)(c))
})

return {
empty: empty,
single: single,
tree: tree,
digit1: digit1,
digit2: digit2,
digit3: digit3,
digit4: digit4,
node2: node2,
node3: node3,
}
}
Insert cell
{
const ft = FingerTreeWithFoldl;
const chars = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ';
const build = n => n === 0 ? ft.empty : build(n-1).snoc(chars.charAt(n-1));

const sample = build(26);

const sum = sample.foldl((x, y) => (x + ' ' + y).trim(), '');
return sample + '\n\n' + sum;
}
Insert cell
Insert cell
FingerTreeWithSize = {
const foldl = (op, z) => v => (v.foldl === undefined) ? op(z,v) : v.foldl(op, z);
const size = v => (v.size === undefined) ? 1 : v.size;
var digit1, digit2, digit3, digit4, node2, node3, empty, single, tree;
tree = (left, subtree, right) => ({
st: subtree,
toString: () => `tree(${left},${subtree},${right})`,
cons: a => (left.cons)(a)(subtree, right),
snoc: a => (right.snoc)(a)(left, subtree),
foldl: (op,z) => op(op(op(z, foldl(op,z)(left)), foldl(op,z)(subtree)), foldl(op,z)(right)),
size: size(left) + size(subtree) + size(right)
});
single = a => ({
toString: () => `single(${a})`,
cons: b => (tree(digit1(b), empty, digit1(a))),
snoc: b => (tree(digit1(a), empty, digit1(b))),
foldl: (op,z) => foldl(op,z)(a),
size: size(a)
});
empty = {
toString: () => "<>",
cons: single,
snoc: single,
foldl: (op,z) => z,
size: 0
};

digit1 = a => ({
toString: () => `[${a}]`,
cons: b => (subtree, right) => tree(digit2(b,a), subtree, right),
snoc: b => (left, subtree) => tree(left, subtree, digit2(a,b)),
foldl: (op,z) => foldl(op,z)(a),
size: size(a)
});
digit2 = (a,b) => ({
toString: () => `[${a},${b}]`,
cons: c => (subtree, right) => tree(digit3(c,a,b), subtree, right),
snoc: c => (left, subtree) => tree(left, subtree, digit3(a,b,c)),
foldl: (op,z) => op(foldl(op,z)(a),foldl(op,z)(b)),
size: size(a) + size(b)
});

digit3 = (a,b,c) => ({
toString: () => `[${a},${b},${c}]`,
cons: d => (subtree, right) => tree(digit4(d,a,b,c), subtree, right),
snoc: d => (left, subtree) => tree(left, subtree, digit4(a,b,c,d)),
foldl: (op,z) => op(op(foldl(op,z)(a),foldl(op,z)(b)),foldl(op,z)(c)),
size: size(a) + size(b) + size(c)
});

digit4 = (a,b,c,d) => ({
toString: () => `[${a},${b},${c},${d}]`,
cons: e => (subtree, right) => tree(digit2(e,a), subtree.cons(node3(b,c,d)), right),
snoc: e => (left, subtree) => tree(left, subtree.snoc(node3(a,b,c)), digit2(d,e)),
foldl: (op,z) => op(op(op(foldl(op,z)(a),foldl(op,z)(b)),foldl(op,z)(c)),foldl(op,z)(d)),
size: size(a) + size(b) + size(c) + size(d)
});

node2 = (a,b) => ({
toString: () => `node(${a},${b})`,
foldl: (op,z) => op(op(z,foldl(op,z)(a)),foldl(op,z)(b)),
size: size(a) + size(b)
});
node3 = (a,b,c) => ({
toString: () => `node(${a},${b},${c})`,
foldl: (op,z) => op(op(op(z,foldl(op,z)(a)),foldl(op,z)(b)),foldl(op,z)(c)),
size: size(a) + size(b) + size(c)
})

return {
empty: empty,
single: single,
tree: tree,
digit1: digit1,
digit2: digit2,
digit3: digit3,
digit4: digit4,
node2: node2,
node3: node3,
}
}
Insert cell
Insert cell
{
const ft = FingerTreeWithSize;
const chars = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ';
const build = n => n === 0 ? ft.empty : build(n-1).cons(chars.charAt(n-1));

const sample = build(26);
return sample + '\n\n' + sample.size;
}
Insert cell
Insert cell
FingerTreeIndexed = {
const foldl = (op, z) => v => (v.foldl === undefined) ? op(z,v) : v.foldl(op, z);
const size = v => (v.size === undefined) ? 1 : v.size;
const at = a => i => i < 0 || i >= size(a) ? undefined : (a.at != undefined) ? a.at(i) : i === 0 ? a : undefined;
const at2 = (a,b) => i => i < size(a) ? at(a)(i) : at(b)(i - size(a));
const at3 = (a,b,c) => i => i < size(a) ? at(a)(i) : at2(b,c)(i - size(a));
const at4 = (a,b,c,d) => i => i < size(a) ? at(a)(i) : at3(b,c,d)(i - size(a));
var digit1, digit2, digit3, digit4, node2, node3, empty, single, tree;
tree = (left, subtree, right) => ({
st: subtree,
toString: () => `tree(${left},${subtree},${right})`,
cons: a => (left.cons)(a)(subtree, right),
snoc: a => (right.snoc)(a)(left, subtree),
foldl: (op,z) => op(op(op(z, foldl(op,z)(left)), foldl(op,z)(subtree)), foldl(op,z)(right)),
size: left.size + subtree.size + right.size,
at: at3(left, subtree, right)
});
single = a => ({
toString: () => `single(${a})`,
cons: b => (tree(digit1(b), empty, digit1(a))),
snoc: b => (tree(digit1(a), empty, digit1(b))),
foldl: (op,z) => foldl(op,z)(a),
size: size(a),
at: at(a)
});
empty = {
toString: () => "<>",
cons: single,
snoc: single,
foldl: (op,z) => z,
size: 0,
at: i => undefined
};

digit1 = a => ({
toString: () => `[${a}]`,
cons: b => (subtree, right) => tree(digit2(b,a), subtree, right),
snoc: b => (left, subtree) => tree(left, subtree, digit2(a,b)),
foldl: (op,z) => foldl(op,z)(a),
size: size(a),
at: at(a)
});
digit2 = (a,b) => ({
toString: () => `[${a},${b}]`,
cons: c => (subtree, right) => tree(digit3(c,a,b), subtree, right),
snoc: c => (left, subtree) => tree(left, subtree, digit3(a,b,c)),
foldl: (op,z) => op(foldl(op,z)(a),foldl(op,z)(b)),
size: size(a) + size(b),
at: at2(a,b)
});

digit3 = (a,b,c) => ({
toString: () => `[${a},${b},${c}]`,
cons: d => (subtree, right) => tree(digit4(d,a,b,c), subtree, right),
snoc: d => (left, subtree) => tree(left, subtree, digit4(a,b,c,d)),
foldl: (op,z) => op(op(foldl(op,z)(a),foldl(op,z)(b)),foldl(op,z)(c)),
size: size(a) + size(b) + size(c),
at: at3(a,b,c)
});

digit4 = (a,b,c,d) => ({
toString: () => `[${a},${b},${c},${d}]`,
cons: e => (subtree, right) => tree(digit2(e,a), subtree.cons(node3(b,c,d)), right),
snoc: e => (left, subtree) => tree(left, subtree.snoc(node3(a,b,c)), digit2(d,e)),
foldl: (op,z) => op(op(op(foldl(op,z)(a),foldl(op,z)(b)),foldl(op,z)(c)),foldl(op,z)(d)),
size: size(a) + size(b) + size(c) + size(d),
at: at4(a,b,c,d)
});

node2 = (a,b) => ({
toString: () => `node(${a},${b})`,
foldl: (op,z) => op(op(z,foldl(op,z)(a)),foldl(op,z)(b)),
size: size(a) + size(b),
at: at2(a,b)
});
node3 = (a,b,c) => ({
toString: () => `node(${a},${b},${c})`,
foldl: (op,z) => op(op(op(z,foldl(op,z)(a)),foldl(op,z)(b)),foldl(op,z)(c)),
size: size(a) + size(b) + size(c),
at: at3(a,b,c)
})

return {
empty: empty,
single: single,
tree: tree,
digit1: digit1,
digit2: digit2,
digit3: digit3,
digit4: digit4,
node2: node2,
node3: node3,
}
}
Insert cell
{
const ft = FingerTreeIndexed;
const chars = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ';
const build = n => n === 0 ? ft.empty : build(n-1).snoc(chars.charAt(n-1));

const sample = build(26);
var out = "\n";
for (var i = 0; i < 26; i++) {
out += sample.at(i) + ' ';
}
out += '\n';
for (var i = 25; i >= 0; i--) {
out += sample.at(i) + ' ';
}
return out+'\n';
}
Insert cell
Insert cell
FingerTreeWithMeasure = measure => {
const measureOf = v => (v.measure === undefined) ? measure(v) : v.measure;
const at = a => v => v < 0 || v >= measureOf(a) ? undefined : (a.at != undefined) ? a.at(v) : a;
const at2 = (a,b) => v => v < measureOf(a) ? at(a)(v) : at(b)(v - measureOf(a));
const at3 = (a,b,c) => v => v < measureOf(a) ? at(a)(v) : at2(b,c)(v - measureOf(a));
const at4 = (a,b,c,d) => v => v < measureOf(a) ? at(a)(v) : at3(b,c,d)(v - measureOf(a));
var digit1, digit2, digit3, digit4, node2, node3, empty, single, tree;
tree = (left, subtree, right) => ({
lf: left,
rf: right,
st: subtree,
toString: () => `tree(${left},${subtree},${right})`,
snoc: a => (right.snoc)(a)(left, subtree),
measure: left.measure + subtree.measure + right.measure,
at: at3(left, subtree, right)
});
single = a => ({
toString: () => `single(${a})`,
snoc: b => (tree(digit1(a), empty, digit1(b))),
measure: measureOf(a),
at: at(a)
});
empty = {
toString: () => "<>",
snoc: single,
measure: 0,
at: value => undefined
};

digit1 = a => ({
toString: () => `[${a}]`,
snoc: b => (left, subtree) => tree(left, subtree, digit2(a,b)),
measure: measureOf(a),
at: at(a)
});
digit2 = (a,b) => ({
toString: () => `[${a},${b}]`,
snoc: c => (left, subtree) => tree(left, subtree, digit3(a,b,c)),
measure: measureOf(a) + measureOf(b),
at: at2(a,b)
});

digit3 = (a,b,c) => ({
toString: () => `[${a},${b},${c}]`,
snoc: d => (left, subtree) => tree(left, subtree, digit4(a,b,c,d)),
measure: measureOf(a) + measureOf(b) + measureOf(c),
at: at3(a,b,c)
});

digit4 = (a,b,c,d) => ({
toString: () => `[${a},${b},${c},${d}]`,
snoc: e => (left, subtree) => tree(left, subtree.snoc(node3(a,b,c)), digit2(d,e)),
measure: measureOf(a) + measureOf(b) + measureOf(c) + measureOf(d),
at: at4(a,b,c,d)
});

node2 = (a,b) => ({
toString: () => `node(${a},${b})`,
measure: measureOf(a) + measureOf(b),
at: at2(a,b)
});
node3 = (a,b,c) => ({
toString: () => `node(${a},${b},${c})`,
measure: measureOf(a) + measureOf(b) + measureOf(c),
at: at3(a,b,c)
})

return {
empty: empty,
single: single,
tree: tree,
digit1: digit1,
digit2: digit2,
digit3: digit3,
digit4: digit4,
node2: node2,
node3: node3,
}
}
Insert cell
{
const measure = value => value.length;
const ft = FingerTreeWithMeasure(measure);

const build = n => n === 0 ? ft.empty : build(n-1).snoc('' + String.fromCharCode(n + 64));

const sample = build(26);

var out = ''
for (var i = 0; i < 26; i++) {
out += sample.at(i) + ' ';
}

return md`### char by index:\n\`${out}\``;
}
Insert cell
{
const ft = FingerTreeWithMeasure(value => value.length);
const words = ['Once', 'upon', 'a', 'midnight', 'dreary', 'while', 'I', 'pondered', 'weak', 'and', 'weary'];

const build = words => {
const add = (n => (n === 0 ? ft.empty : add(n-1).snoc(words[n-1]))); // could use Y-combinator
return add(words.length)
}

const sample = build(words);
var j = 0;
var rel = 0;
var ruler0 = '';
var ruler1 = '';
for (var i = 0; i < sample.measure; i++) {
if (rel == words[j].length) {
j += 1;
rel = 0;
ruler0 += ' '
ruler1 += '&nbsp;'
}
ruler1 += i%10 == 0 ? i/10 : '&nbsp;';
rel += 1;
ruler0 += '' + (i % 10);
}
return html`<h3>word by position</h3><br>
<code>${words.map((w,i) => w + ' ')}<br/>
${ruler0}<br/>${ruler1}<br/><br/>
sample.at(10) = "${sample.at(10)}"<br/>
sample.at(41) = "${sample.at(41)}"<br/>
sample.at(28) = "${sample.at(28)}"</code>`
}
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
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