Folding in JS

Mutatis mutandis between Haskell and JS, the two approaches to fold a list/array are foldl, which does it from the "left", and foldr, which does it from the "right"¹.

const foldl = f => z => ([x, ...xs]) =>
    x === undefined ? z
    : foldl (f) (f(z)(x)) (xs)

const foldr = f => z => ([x, ...xs]) =>
    x === undefined ? z
    : f (x) (foldr(f)(z)(xs))

With these two functions defined, recursion over an array is abstracted, so there's no need to manually traverse it - all other operations can now be defined in terms of foldr or foldl (at least as an exercise in futility)².

In terms of fold

// helper function
const cons    = x => ([...xs]) => [x,...xs]
const append  = ([...xs]) => ([...ys]) => [...xs, ...ys]
const apply   = f => x => f(x)
const flip    = f => a => b => f(b)(a)
const add = a => b => a + b
const mul = a => b => a * b
const and = a => b => a && b
const or  = a => b => a || b
const K   = a => _ => a;
const B   = g => f => x => g(f(x))


// In Terms Of Fold

// foldr_id - leaves a list intact, showing that folding a list means replacing all cons with `f` and the empty list ctor `[]` with an initial value, `z`
const foldr_id = foldr (cons)        ([])

const reverse  = foldl (flip (cons)) ([])
const flatten  = foldr (append)      ([])

const compose  = foldr (apply)
const pipe     = foldl (flip(apply))

const head     = foldr (K)       (undefined)
const last     = foldl (flip(K)) (undefined)

const sum      = foldr (add)  (0)
const product  = foldr (mul)  (1)

const all      = foldr (and)  (true)
const some     = foldr (or)   (false)

const map    = f => foldr (B(cons)(f)) ([])
const filter = p => foldr (x => xs => p(x) ? cons(x)(xs) : xs) ([])



// Check

let m = [1,2,3]
let n = [5,6,7]
let t = [[1,2,3], [5,6,7]]
let p = [true, true, false]

console.log(
    '\n',
    'foldr_id:'         , foldr_id  (m) , '\n' ,

    'reverse :'         , reverse   (m) , '\n' ,
    'flatten :'         , flatten   (t) , '\n' ,

    'sum     :'         , sum       (m) , '\n' ,
    'product :'         , product   (m) , '\n' ,

    'all     :'         , all       (p) , '\n' ,
    'some    :'         , some      (p) , '\n' ,

    'head    :'         , head      (m) , '\n' ,
    'last    :'         , last      (m) , '\n' ,

    'map     :'         , map    (add(10)) (m) , '\n' ,
    'filter  :'         , filter (a=>a>1)  (m) , '\n' ,

    'compose :'         , compose (5) ([x=>x*3, x=>x+5]) , '\n' ,
    'pipe    :'         , pipe    (5) ([x=>x*3, x=>x+5]) , '\n' ,
)

---

1. The elements are accessed from the left in both cases. ↩

2. Haskell's lists are singly-linked lists, so prepending is the most efficient operation to add an element; but to append an element, the entire list needs to be traversed. Although JS arrays have many incarnations (depending whether they hold homogeneous or heterogeneous elements, whether they are sparse, etc.), appending should be the most efficient operation. ↩