Skip to content

Instantly share code, notes, and snippets.

@DrBoolean
Created December 15, 2015 18:19
Show Gist options
  • Save DrBoolean/69082469fd8ff2fa94b5 to your computer and use it in GitHub Desktop.
Save DrBoolean/69082469fd8ff2fa94b5 to your computer and use it in GitHub Desktop.
F-algebra es2015
const daggy = require('daggy')
const {compose, curry, map, prop, identity, intersection, union} = require('ramda');
const inspect = (x) => { if(!x) return x; return x.inspect ? x.inspect() : x; }
// F-algebras
// Fix
// ============
// Fx is a simple wrapper that does almost nothing. It's much more useful in typed languages to check that we have a recursive f (Fix f)
// It's still useful for reasoning about recursion and defining fold/unfold in terms of hylo if we want. http://school.looprecur.com/?video=122716071
// Fx :: f (Fix f) -> Fix f
const Fx = daggy.tagged('x')
Fx.prototype.inspect = function(){ return `Fx(${inspect(this.x)})` }
// unFix :: Fix f -> f (Fix f)
const unFix = prop('x')
// List
// ============
// Here's List for simplicity, but F-algebras work with any recursive data structure.
// List has a fixed point of Nil so it will stop the recusion once it hits the "bottom" of the barrel.
const List = daggy.taggedSum({ Cons: ['head', 'tail'], Nil: [] })
const {Cons, Nil} = List
List.prototype.fold = function(f, g) { return this.cata({Cons: f, Nil: g }) }
List.prototype.inspect = function() {
return this.fold((h, t) => `Cons(${inspect(h)}, ${inspect(t)})`, () => 'Nil')
}
// note this map passes the tail, not the head to f
List.prototype.map = function(f) {
return this.fold((h, t) => Cons(h, f(t)), () => Nil)
}
// Recursion Schemes
// ============
// These recurse and take advantage that we'll hit a fixed point
// fold :: Functor f => (f a -> a) -> Fix f -> a
const fold = curry((alg, x) => compose(alg, map(fold(alg)), unFix)(x))
// unfold :: (a -> t a) -> a -> t
const unfold = curry((g, a) => compose(Fx, map(unfold(g)), g)(a))
// hylo :: Functor f => (f b -> b) -> (a -> f a) -> a -> b
const hylo = curry((f, g, x) => compose(fold(f), unfold(g))(x))
// Unfolds (anamorphisms)
// ====================
// Spin up a data structure from a seed value
const aToL = unfold(([h, ...t]) => h ? Cons(h, t) : Nil)
aToL([1,2,3,4,5])
//=> Fx(Cons(1, Fx(Cons(2, Fx(Cons(3, Fx(Cons(4, Fx(Cons(5, Fx(Nil)))))))))))
const range = (init, count) => unfold(x => (x >= count) ? Nil : Cons(x, x+1), init)
range(2, 10)
//=> Fx(Cons(2, Fx(Cons(3, Fx(Cons(4, Fx(Cons(5, Fx(Cons(6, Fx(Cons(7, Fx(Cons(8, Fx(Cons(9, Fx(Nil)))))))))))))))))
// Folds (catamorphisms)
// ===============
// All our favorite list functions can be defined here.
// They take a List with the tail being already "folded" so it's treated like the accumulator.
const sum = fold(x => x === Nil ? 0 : x.head + x.tail)
sum(aToL([6,3,2,1]))
//=> 12
const max = fold(x => x === Nil ? -Infinity : (x.head > x.tail) ? x.head : x.tail)
max(aToL([2,5,9,3,1]))
//=> 9
const map_ = (f, l) => fold(x => x === Nil ? Nil : Cons(f(x.head), x.tail), l)
map_(x => x+'!', aToL(["yippee", "dippee", "doo"]))
//=> Cons(yippee!, Cons(dippee!, Cons(doo!, Nil)))
const filter_ = (f, l) => fold(x => x === Nil ? Nil : f(x.head) ? Cons(x.head, x.tail) : x.tail, l)
filter_(x => x > 2, aToL([1,2,3,4,5]))
//=> Cons(3, Cons(4, Cons(5, Nil)))
// Hylomorphisms
// ===============
// unfold followed by a fold. It's defined in terms of those for learning, but we can fuse the two and remove the intermediate data structure.
const joinAlphabet = (x) => (x === Nil) ? "" : x.head + ',' + x.tail
const makeAlphabet = (b) => (b > 25) ? Nil : Cons(String.fromCharCode(b+65), b+1)
hylo(joinAlphabet, makeAlphabet, 0)
//=> "A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S,T,U,V,W,X,Y,Z,"
//========= Program Via F-Alg==========
// Instead of List, let's make a little dsl
const Expr = daggy.taggedSum({Lit: ['x'], Add: ['x', 'y'], Mul: ['x', 'y']})
const {Lit, Add, Mul} = Expr;
Expr.prototype.inspect = function() {
return this.cata({
Lit: (x) => `Lit(${inspect(x)})`,
Add: (x, y) => `Add(${inspect(x)}, ${inspect(y)})`,
Mul: (x, y) => `Mul(${inspect(x)}, ${inspect(y)})`
})
}
Expr.prototype.map = function(f) {
return this.cata({
Lit: (x) => this, // fixed
Add: (x, y) => Add(f(x), f(y)),
Mul: (x, y) => Mul(f(x), f(y))
})
}
// our int interpreter
const interpretInt = (a) => {
return a.cata({
Lit: (x) => x, // fixed
Add: (x, y) => x + y,
Mul: (x, y) => x * y
})
}
// our set interpreter
const interpretSet = (a) => {
return a.cata({
Lit: identity, // fixed
Add: intersection,
Mul: union
})
}
// little constructor fn's so we don't have to deal with inserting Fx. We used aToL unfold instead of this for List.
const add = (x, y) => Fx(Add(x, y))
const mul = (x, y) => Fx(Mul(x, y))
const lit = (x, y) => Fx(Lit(x))
const int_prog = mul(add(lit(2), lit(3)), lit(4))
const set_prog = mul(add(lit([2]), lit([2,3])), lit([2,4,5]))
fold(interpretInt, int_prog)
//=> 20
fold(interpretSet, set_prog)
//=> [2, 4, 5]
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment