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.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 ]