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

// recursion
const sum = xs => xs.length === 0 ?
      0 : first(xs) + sum(rest(xs))

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

// reduce - fold - catamorphism
const reduce = (f, acc, xs) => xs.length === 0 ?
      	acc : 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]

// point combinator
const y = le => (f => f(f))(f => le(x => f(f)(x)))

// TODO: Convert to some sort of point combinator?
// I see that there is more gonging on than just a y combinator
// Will likely have to look at some math
// 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 => x < 26 && [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
	this.concat = y => Sum(x + y.val)
	this.empty = Sum(0)
}
const Sum = x => new _Sum(x)

var mconcat = xs => xs.reduce((acc, x) => acc.concat(x), xs[0].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