Skip to content

Instantly share code, notes, and snippets.

@meChrisReed
Forked from CreaturePhil/recur.js
Last active June 16, 2017 19:08
Show Gist options
  • Save meChrisReed/c16ec2882270dce5925efac773cdf145 to your computer and use it in GitHub Desktop.
Save meChrisReed/c16ec2882270dce5925efac773cdf145 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, ...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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment