nested-lists-functions.js

// 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