Skip to content

Instantly share code, notes, and snippets.

@kpuputti

kpuputti/fold.js

Last active Oct 29, 2020
Embed
What would you like to do?
Functional acrobatics using folds in JavaScript.
/*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.apply(f, [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 ]
@nickshanks

This comment has been minimized.

Copy link

@nickshanks nickshanks commented Aug 9, 2018

FWIW, readers can avoid calling bind.apply() if you define your multi-argument functions (cons, foldr, foldl et al.) using multiple fat arrows, e.g.:
const foldl = f => v => xs => xs.reduce(f, v); — i.e. curry them rather than partially apply.
Then you can also use point-free style on your folds too:
const length = () => foldr((acc, _) => 1 + acc)(0);

It's your call then as to whether f(a)(b)… looks better or worse than partial(f, a, b, …).

Point-free style is of more use in more strongly typed languages, where you want your functions to be polymorphic, to avoid mentioning "xs" and having to specify a type for it.

@kpuputti

This comment has been minimized.

Copy link
Owner Author

@kpuputti kpuputti commented Sep 19, 2018

Thanks for the comment! I do like the curried style, seems more readable.

I guess point-free style might even be debatable in a language with static types, but I'm not experienced enough with e.g. Haskell to have a strong opinion on that. But definitely in a dynamic language like JavaScript I would consider it too magical and surprising.

Please note that this Gist is very much an unoptimized proof-of-concept and I wouldn't even suggest using these patterns in JavaScript. Super fun to play around with these, though.

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.