F-algebra es2015

falg.js

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]