A Million Ways to Fold in JS Notes

recur.js

// from http://forwardjs.com/university/a-million-ways-to-fold-in-js

'use strict'

const first = (xs) => xs[0]
const rest = (xs) => xs.slice(1)
const concat = (xs1, xs2) => xs1.concat(xs2)

// recursion
const sum = (xs) => {
	if (xs.length === 0) return 0
	return first(xs) + sum(rest(xs))
}

console.log(sum([1, 2]))
//=> 3

// reduce - fold - catamorphism
const reduce = (f, acc, xs) => {
	if (xs.length === 0) return acc
	return reduce(f, f(acc, first(xs)), rest(xs))
}

const reverse = (xs) => reduce((acc, x) => [x].concat(acc), [], xs)

console.log(reverse([7, 6, 5]))
//=> [5, 6, 7]

// corecursion - anamorphism
const unfold = (f, seed) => {
	const go = (f, seed, acc) => {
		const res = f(seed)
		return res ? go(f, res[1], acc.concat([res[0]])) : acc;
	}
	return go(f, seed, [])
}

const alphabet = unfold(x => {
	if (x < 26) return [String.fromCharCode(x+65), x+1]
}, 0)

console.log(alphabet)
//=> ['A', 'B', 'C' ... 'Z']

// transducers - the mappers/filterers are tranducers
const mapper = (f, cnct) => ((acc, x) => cnct(acc, f(x)))

console.log(reduce(mapper(x => x + 1, concat), [], [1, 2, 3]))
//=> [2, 3, 4]

const filterer = (f, cnct) => ((acc, x) => f(x) ? cnct(acc, x) : acc)

console.log(reduce(filterer(x => x > 1, concat), [], [1, 2, 3]))
//=> [2, 3]

const copy = (xs) => reduce(concat, [], xs)

console.log(reduce(filterer(x => x > 1,
	mapper(x => x + 1, concat)),
	[], [1, 2, 3]))
//=> [3, 4]

// we got iteration and transformation but no accumulation

// monoids
const xs = []
const ys = []

// left identity
concat([], xs) == xs

// right identity
concat(xs, []) == xs

// associativity
concat(concat(xs, ys), xs) == concat(xs, concat(ys, xs))

// array is already a monoid with concat and empty

// Sum type
const _Sum = function(x) { this.val = x }
const Sum = (x) => (new _Sum(x))

_Sum.prototype.concat = function(y) { return Sum(this.val + y.val) }
_Sum.prototype.empty = () => Sum(0)

var mconcat = function(xs) {
  var m = xs[0];
  return xs.reduce(function(acc, x){ return acc.concat(x) }, m.empty());
}

console.log(mconcat([Sum(1), Sum(2), Sum(3), Sum(4)]))
//=> Sum(10)

// useful functions are now just types

// const foldMap = (f, xs) => compose(fold, map(f))(xs)
// const tree = Node(Node(Leaf(2), 1, Leaf(3), 2, Leaf(4)))
// sum(tree)
//=> 12
// product(tree)
//=> 38
// max(tree)
//=> 4
//=> 12

// we got iteration and accumulation but transformation

// [Sum(a)] -> Sum(1)
// F(a) -> a is called an algebra
// takes it out of its type

// F-algebras

const cata = (f, xs) => {
	console.log('h', xs);
	if (!Array.isArray(xs)) return xs
	return f(xs.map(ys => cata(f, ys)))
}
// fixed point is whatever it returns itself

// sum2 is an algebra
const Nil = undefined
const sum2 = (x) => (x === Nil) ? 0 : x[0] + x[x.length-1];

console.log(cata(sum2, [2, 3, 4]))
// ^ this is bork suppose to be 9 but it is 6

// suppose to be
// const lst = Cons(2, Cons(3, Cons(4, Nil)))
// cata(sum, lst)
// Nil
// Cons(4, 0)
// Cons(3, 4)
// Cons(2, 7)
//=> 9

// a -> F(a) is a coalgebra

It's a bit frustrating to get an implementation of the List catamorphism without a working example. Voilà:

const map = f => xs =>
  xs.map(x => f(x));

const cata = f => xs =>
  Array.isArray(xs)
    ? f(map(ys => cata(f) (ys)) (xs))
    : xs;

const sum = ([m, n]) =>
  m === undefined
    ? 0
    : m + n;

cata(sum) ([1, [2, [3, [4, [5, []]]]]]); // 15