Functional acrobatics using folds in JavaScript.

fold.js

/*eslint-env es6 */

// Inspired by the paper "A tutorial on the universality and
// expressiveness of fold" by Graham Hutton (available at
// http://www.cs.nott.ac.uk/~gmh/fold.pdf), implementing some generic
// list handling functions in JavaScript in terms of `fold`.

// Personally I had an enlightnening moment when I realised the
// beautiful interplay of cons lists and foldr during the FP101x
// Haskell course. JavaScript's syntax doesn't make this very apparent
// at first, but it's still there if you analyze the `map` and
// `filter` implementations below.

// Essential constructs
const cons = (x, xs) => [x].concat(xs);
const car = xs => xs[0];
const cdr = xs => xs.slice(1);
const foldr = (f, v, xs) => xs.reduceRight(f, v);
const foldl = (f, v, xs) => xs.reduce(f, v);
const partial = (f, ...xs) => f.bind(null, ...xs);
const id = x => x;

// Helpers
const add = (x, y) => x + y;
const even = x => x % 2 === 0;
const and = (x, y) => x && y;
const or = (x, y) => x || y;
const times = (x, y) => x * y;
const double = x => 2 * x;
const isEmpty = xs => xs.length === 0;
const range = n => Array.from({length: n}, (v, i) => i);

// Folds, point-free style!
const sum = partial(foldr, add, 0);
const all = partial(foldr, and, true);
const any = partial(foldr, or, false);
const product = partial(foldr, times, 1);

// Folding like a boss!
const length = xs => foldr((acc, _) => 1 + acc , 0, xs);
const reverse = xs => foldl((acc, curr) => cons(curr, acc), [], xs);
const map = (f, xs) => foldr((acc, curr) => cons(f(curr), acc), [], xs);
const filter = (f, xs) => foldr((acc, curr) => f(curr) ? cons(curr, acc) : acc, [], xs);

// Ok, let's test these in practice.

console.log('cons(0, [1, 2, 3]) =', cons(0, [1, 2, 3]));
// => cons(0, [1, 2, 3]) = [ 0, 1, 2, 3 ]

console.log('car([1, 2, 3]) =', car([1, 2, 3]));
// => car([1, 2, 3]) = 1

console.log('cdr([1, 2, 3]) =', cdr([1, 2, 3]));
// => cdr([1, 2, 3]) = [ 2, 3 ]

console.log('car(cdr([1, 2, 3])) =', car(cdr([1, 2, 3])));
// => car(cdr([1, 2, 3])) = 2

console.log('range(10) =', range(10));
// => range(10) = [ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 ]

console.log('sum(range(10)) =', sum(range(10)));
// => sum(range(10)) = 45

console.log('all([true, true, true]) =', all([true, true, true]));
// => all([true, true, true]) = true

console.log('all([true, true, false]) =', all([true, true, false]));
// => all([true, true, false]) = false

console.log('any([true, true, true]) =', any([true, true, true]));
// => any([true, true, true]) = true

console.log('any([false, false, true]) =', any([false, false, true]));
// => any([false, false, true]) = true

console.log('length(range(0)) =', length(range(0)));
// => length(range(0)) = 0

console.log('length(range(16)) =', length(range(16)));
// => length(range(16)) = 16

console.log('reverse(range(10)) =', reverse(range(10)));
// => reverse(range(10)) = [ 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 ]

console.log('car(cdr(reverse(range(10)))) =', car(cdr(reverse(range(10)))));
// => car(cdr(reverse(range(10)))) = 8

console.log('cons(10, reverse(range(10))) =', cons(10, reverse(range(10))));
// => cons(10, reverse(range(10))) = [ 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 ]

console.log('map(double, range(5)) =', map(double, range(5)));
// => map(double, range(5)) = [ 0, 2, 4, 6, 8 ]

console.log('filter(even, range(10)) =', filter(even, range(10)));
// => filter(even, range(10)) = [ 0, 2, 4, 6, 8 ]

console.log('map(double, filter(even, reverse(range(10)))) =', map(double, filter(even, reverse(range(10)))));
// => map(double, filter(even, reverse(range(10)))) = [ 16, 12, 8, 4, 0 ]