Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
// Some functional utilities
const map = f => arr => arr.map(f);
const id = x => x;
const concat = xs => [].concat(...xs);
const fold = (f, init) => xs => xs.reduce(f, init);
const sum = fold((x, y) => x + y, 0);
// Nested-list algebras
function alg(leaf, branch) {
return nested => nested instanceof Array
? branch(nested)
: leaf(nested);
}
// The nested-list catamorphism... obviously
const cata = f => y => f(alg(id, map(cata(f)))(y));
// We can map a function over a nested list
const map_nested = f => cata(alg(f, id));
// ... and take the sum of a nested list!
const nested_list_sum = cata(alg(id, sum));
// ... and flatten a nested list too!
const flatten = cata(alg(x => [x], concat));
// We can even define more interesing functions,
// like computing the depth of nesting.
const maximum = fold((x,y) => Math.max(x,y), 0);
const depth = cata(alg(_ => 0, xs => maximum(xs) + 1));
///////////
// TESTS //
///////////
// Let's define our test data
const testData = [ [ 1, 2, [ 3 ] ], 4 ];
// TEST: Map on nested list
console.log('test1: map on nested list',
map_nested(x => x * 2)(testData));
// >> [ [ 2, 4, [ 6 ] ], 8 ];
// TEST: Nested list sum
console.log('test2: nested list sum',
nested_list_sum(testData))
// >> 10
// TEST: Flatten nested list
console.log('test2: flatten',
flatten(testData))
// >> [ 1, 2, 3, 4 ]
// TEST: Mandatory empty list test
console.log('test3: flatten empty',
flatten([]));
// >> [ ]
// TEST: We consider non-list values to be "arbitrarily nested" lists
// with a nesting of 0
console.log('test4: flatten non-list',
flatten(10));
// [ 10 ]
console.log('test5: depth non-list',
depth(10));
// 0
// TEST: We'll make sure it works on nested empty lists
console.log('test6: flatten deep with empty',
flatten([[[[], [], [10], [[[]]], [], [1] ]]]));
// [ 10, 1 ]
// TEST: Depth of a list
console.log('test4: depth of list',
depth(testData));
// >> 3
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.