{{ message }}

Instantly share code, notes, and snippets.

# kpuputti/fold.js

Last active Oct 29, 2020
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; 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 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 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.