Skip to content

Instantly share code, notes, and snippets.

@CreaturePhil
Last active October 19, 2018 17:03
Show Gist options
  • Save CreaturePhil/b7aeda44cbd9a395ab37 to your computer and use it in GitHub Desktop.
Save CreaturePhil/b7aeda44cbd9a395ab37 to your computer and use it in GitHub Desktop.
A Million Ways to Fold in JS Notes
// 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
@ivenmarquardt
Copy link

ivenmarquardt commented Mar 2, 2018

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

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment