Archive for February, 2016

February 20, 2016

Categories in ES6

Preliminaries

Assuming contracts from jscategory sourcecode.

log = console.log.bind(console);
logtry = (f) => {
  try { log(f()) } catch (e) { log(e); }
};
undef = typeOf('undefined');
inheritsFrom = (clazz) => (c) => {
  func(c);
  instanceOf(clazz)(c.prototype);
  return c;
};

Categories

Category = class Category {
  constructor() {
    let t = new.target;
    if (t === Category) {
      throw new TypeError('Abstract');
    }
    // Objects, morphisms, source, target, identity, composition
    func(t.obj);
    func(t.mor);
    t.src = hom(t.mor, t.obj)(t.src);
    t.tgt = hom(t.mor, t.obj)(t.tgt);
    t.id = hom(t.obj, t.mor)(t.id);
    t.com = hom(pbn([t.src, t.tgt]), t.mor)(t.com);
  }
};

finnum = (n) => {
  num(n);
  if (!isFinite(n)) {
    throw new TypeError('Expected a finite number');
  }
  return n;
};

// Poset of finite numbers and ≤
LTE = class LTE extends Category {
  static obj(n) { return finnum(n); }
  static mor(pair) {
    prodn([finnum, finnum])(pair);
    if (pair[0] > pair[1]) {
      throw new TypeError(pair[0] + ' > ' + pair[1]);
    }
    return pair;
  }
  static src([s, t]) { return s; }
  static tgt([s, t]) { return t; }
  static id(n) { this.obj(n); return [n, n]; }
  static com([g, f]) {
    return [f[0], g[1]];
  }
};
new LTE();

logtry(()=>LTE.obj(5)); // 5
logtry(()=>LTE.obj(1 / 0)); // Expected a finite number

logtry(()=>LTE.mor([1, 2])); // [1, 2]
logtry(()=>LTE.mor([1, 2, 3])); // Expected two arguments
logtry(()=>LTE.mor(['a', 1])); // Expected a number
logtry(()=>LTE.mor([1, 0])); // 1 > 0

logtry(()=>LTE.src([0, 1])); // 0
logtry(()=>LTE.tgt([0, 1])); // 1

logtry(()=>LTE.id(0)); // [0, 0]
logtry(()=>LTE.id('a')); // Expected a number.

logtry(()=>LTE.com([[2, 3], [1, 2]])); // [1, 3]
logtry(()=>LTE.com([[3, 4], [1, 2]])); // Failed to match pullback constraint.

// Monoids are one-object categories
StrCat = class StrCat extends Category {
  static obj(x) { return undef(x); }
  static mor(s) { return str(s); }
  static src(s) { }
  static tgt(s) { }
  static id() { return ''; }
  static com([g, f]) { return g + f; }
};
new StrCat();

logtry(()=>StrCat.com(['hi ', 'there'])); // 'hi there'
logtry(()=>StrCat.com([3, ' little pigs'])); // Expected a string

NatPlus = class NatPlus extends Category {
  static obj(x) { return undef(x); }
  static mor(s) { return nat32(s); }
  static src(s) { }
  static tgt(s) { }
  static id() { return 0; }
  static com([g, f]) { return g + f; }
};
new NatPlus();

positive = (n) => {
  nat32(n);
  if (n < 1) {
    throw ('Expected a positive natural');
  }
  return n;
};

// In the category of matrices over ℝ, 
// objects are positive natural numbers and
// morphisms m -> n are (n x m)-dimensional matrices
Matrix = class Matrix extends Category {
  static obj(n) { return positive(n); }
  static mor(matrix) {
    arrOf(arrOf(num))(matrix);
    if (matrix.length == 0 || matrix[0].length == 0) {
      throw new TypeError('Malformed matrix');
    }
    for (let row = 1; row < matrix.length; ++row) {
      if (matrix[row].length != matrix[0].length) {
        throw new TypeError('Malformed matrix');
      }
    }
    return matrix;  
  }
  // Columns
  static src(m) { return m[0].length; }
  // Rows
  static tgt(m) { return m.length; }
  // Identity matrix
  static id(n) {
    let a = [];
	for (let row = 0; row < n; ++row) {
	  a.push(Array(...Array(n)).map((_, i) => +(i == row)));
	}
	return a;
  }
  // Matrix multiplication
  static com([g, f]) {
    if (g[0].length != f.length) {
      throw new TypeError('Not composable');
    }
    let a = [];
    for (let i = 0; i < g.length; ++i) {
      a[i] = [];
      for (let k = 0; k < f[0].length; ++k) {
        a[i][k] = 0;
        for (let j = 0; j < f.length; ++j) {
          a[i][k] += g[i][j] * f[j][k];
        }
      }
    }
    return a;
  }
};
new Matrix();

logtry(()=>Matrix.id(3)); // [[1,0,0],[0,1,0],[0,0,1]]
logtry(()=>Matrix.com([[[1,2],[3,4]], [[5,6,7],[8,9,10]]])); // [[21,24,27],[47,54,61]]

Contract = class Contract extends Category {
  // Objects are contracts.
  static obj(c) { return func(c); }
  // Morphisms are guarded functions between them.
  static mor(f) {
    if ((''+f).match(/\/\* guarded \*\/$/)) {
      return func(f);
    }
    throw new TypeError('Expected a guarded function');
  }
  // We can't actually check src or tgt of a
  // guarded function, so just return the broadest
  // contract
  static src(f) { return any; }
  static tgt(f) { return any; }
  // Identity is the identity function!
  static id(c) { return c; }
  // Composition is composition!
  static com([g, f]) { return (x)=>g(f(x)); }
};
new Contract();

Functors

Functor = class Functor {
  constructor() {
    let t=new.target;
    if (t === Functor) {
      throw new TypeError('Abstract');
    }
    inheritsFrom(Category)(t.src);
    inheritsFrom(Category)(t.tgt);
    t.mapobj = hom(t.src.obj, t.tgt.obj)(t.mapobj);
    t.mapmor = hom(t.src.mor, t.tgt.mor)(t.mapmor);
  }
  static map(x) {
    try {
      return this.mapobj(x);
    } catch (_) {
      return this.mapmor(x);
    }
  }
};

IdFunc = (cat) => {
  let result = class Identity extends Functor {
    static get src() { return cat; }
    static get tgt() { return cat; }
    static mapobj(c) { return c; }
    static mapmor(f) { return f; }
  };
  new result();
  return result;
};
IdStrCat = IdFunc(StrCat);

// IdStrCat is the identity functor on StrCat.
// It acts on objects and morphisms of StrCat.
logtry(()=>IdStrCat.map()); // undefined
logtry(()=>IdStrCat.map('foo')); // foo

StrLen = class StrLen extends Functor {
  static get src() { return StrCat; }
  static get tgt() { return NatPlus; }
  static mapobj() { }
  static mapmor(s) { return s.length; }
};
new StrLen();
logtry(()=>StrLen.map()); // undefined
logtry(()=>StrLen.map('foo')); // 3

// Category of Categories and Functors
Cat = class Cat extends Category {
  static obj(c) { return inheritsFrom(Category)(c); }
  static mor(f) { return inheritsFrom(Functor)(f); }
  static src(f) { return f.src; }
  static tgt(f) { return f.tgt; }
  static id(c) { return IdFunc(c); }
  static com([g, f]) {
    let Composite = class Composite extends Functor {
      static get src() { return f.src; }
      static get tgt() { return g.tgt; }
      static mapobj(c) { return g.mapobj(f.mapobj(c)); }
      static mapmor(h) { return g.mapmor(f.mapmor(h)); }
    };
    new Composite();
    return Composite;
  }
};
new Cat();

logtry(()=>Cat.com([StrLen, IdStrCat]).map('foo')); // 3

ArrOf = class ArrOf extends Functor {
  static get src() { return Contract; }
  static get tgt() { return Contract; }
  static mapobj(c) { return arrOf(c); }
  static mapmor(f) { return arrOf(f); }
};
new ArrOf();
logtry(()=>ArrOf.map(int32)([1, 2, 3])); // [1, 2, 3]
logtry(()=>ArrOf.map(int32)(['a'])); // Expected a 32-bit integer
logtry(()=>ArrOf.map((x)=>x.length)(['hi', 'there'])); // [2, 5]

Natural Transformations

NatTrans = class NatTrans {
  constructor() {
    let t=new.target;
    if (t === NatTrans) {
      throw new TypeError('Abstract');
    }
    inheritsFrom(Functor)(t.src);
    inheritsFrom(Functor)(t.tgt);
    // nat trans between functors F, G: C -> D
    let F = t.src;
    let G = t.tgt;
    if (F.src !== G.src || F.tgt !== G.tgt) {
      throw new TypeError('Expected parallel functors');
    }
    // assigns to every object in C a morphism in D
    // such that square commutes.
    let C = F.src;
    let D = F.tgt;
    t.map = hom(C.obj, D.mor)(t.map);
  }
};

// Given categories C, D, returns the functor category hom(C,D)
Hom = hom(
    inheritsFrom(Category),
    inheritsFrom(Category),
    inheritsFrom(Category))((C, D) => {
  let result = class Hom extends Category {
    static obj(f) {
      inheritsFrom(Functor)(f);
      if (f.src !== C || f.tgt !== D) {
        throw new TypeError('Wrong functor source or target');
      }
      return f;
    }
    static mor(nt) {
      inheritsFrom(NatTrans)(nt);
      let F = nt.src;
      if (F.src !== C || F.tgt !== D) {
        throw new TypeError('Wrong functor source or target');
      }
      return nt;
    }
    static src(nt) { return nt.src; }
    static tgt(nt) { return nt.tgt; }
    static id(f) {
      let result = class IdNat extends NatTrans {
        static get src() { return f; }
        static get tgt() { return f; }
        static map(c) { return D.id(f.mapobj(c)); } 
      };
      new result();
      return result;
    }
    static com([g, f]) {
      let result = class Composite extends NatTrans {
        static get src() { return f.src; }
        static get tgt() { return g.tgt; }
        static map(c) { return D.com([g.map(c), f.map(c)]); }
      }
      new result();
      return result;
    }
  };
  new result();
  return result;
});

// Category of functors from StrCat to NatPlus
Str2Nat = Hom(StrCat, NatPlus);
// StrLen is an object in Str2Nat
logtry(()=>Str2Nat.obj(StrLen)); // StrLen
// IdStrCat goes from StrCat to itself, not to NatPlus
logtry(()=>Str2Nat.obj(IdStrCat)); // Wrong functor source or target
// Identity natural transformation on StrLen functor
IdStrLen = Str2Nat.id(StrLen);
// IdStrLen is a morphism in Str2Nat from StrLen to itself
logtry(()=>Str2Nat.mor(IdStrLen).src); // StrLen

// Category of endofunctors on Contract
End = Hom(Contract, Contract);
Flatten = class Flatten extends NatTrans {
  static get src() { return Cat.com([ArrOf, ArrOf]); }
  static get tgt() { return ArrOf; }
  // c gets used by type checker
  static map(c) {
    return hom(arrOf(arrOf(c)), arrOf(c))(
      (aax) => aax.reduce((prev, cur)=>prev.concat(cur)));
  }
};
new Flatten();
logtry(()=>End.obj(ArrOf)); // ArrOf
logtry(()=>End.obj(Cat.com([ArrOf, ArrOf]))); // Composite
logtry(()=>End.mor(Flatten)); // Flatten
logtry(()=>Flatten.map(int32)([[1,2],[],[3,4,5]])); // [1,2,3,4,5]
Advertisements
February 17, 2016

Promise monad in ES6

ES6 is introducing classes to JavaScript. You can turn on the new features in Chrome by enabling chrome://flags/#enable-javascript-harmony or in v8 with v8 –harmony.

Functor = class Functor {
  constructor() {
    if (new.target === Functor) {
      throw new TypeError(
          'Cannot construct Functor instances directly');
    }
    if (typeof(this.map) !== 'function' ||
        typeof(new.target.map) !== 'function') {
      throw new TypeError('Must provide static and member map.')
    }
  }
};

// Base monad class
Monad = class Monad extends Functor {
  constructor() {
    super();
    if (new.target === Monad) {
      throw new TypeError(
          'Cannot construct Monad instances directly');
    }
    if (typeof(this.lift) !== 'function' ||
        typeof(new.target.lift) !== 'function') {
      throw new TypeError('Must provide static and member lift.')
    }
    if (typeof(this.flatten) !== 'function' ||
        typeof(new.target.flatten) !== 'function') {
      throw new TypeError('Must provide static and member flatten.')
    }
  }
  flatMap(f) {
    return this.map(f).flatten();
  }
  static flatMap(f) {
    return (mx) => mx.flatMap(f);
  }
};

// Promise monad
P = class P extends Monad {
  // Constructor expects a promise to wrap.
  constructor(p) {
    super();
    if (p && typeof(p.then) === 'function') {
      this.p = p;
    } else {
      throw new TypeError(
        'Expected an object with a "then" method.');
    }
  }
  static map(f) {
    return (px) => px.map(f);
  }
  map(f) {
    return new P(this.p.then(f));
  }
  static lift(v) {
    return new this(new Promise((resolve) => resolve(v)));
  }
  lift() { return this.constructor.lift(this); }
  static flatten(ppv) {
    return new this(new Promise((resolve) => {
      return ppv.map((pv) => pv.map(resolve))
    }));
  }
  flatten() { return this.constructor.flatten(this); }
};

// XHR + Promise
XHRP = (url) => new P(new Promise((resolve) => {
  var xhr = new XMLHttpRequest();
  xhr.onreadystatechange = () => {
    if (xhr.readyState == XMLHttpRequest.DONE) {
      if (xhr.status == 200) {
        resolve(xhr.responseText);
      }
    }
  };
  xhr.open('GET', url, true);
  xhr.send();
}));

// Search Google for your ip address
XHRP('http://jsonip.com').flatMap((json) =>
  XHRP('http://google.com/search?' + JSON.parse(json).ip).map((results) =>
    console.log(results)));

// New experimental GlobalFetch already returns promise
if (GlobalFetch) {
  GFP = (url) => new P(GlobalFetch.fetch(url));

  // Search Google for your ip address
  GFP('http://jsonip.com').flatMap((json) =>
    GFP('http://google.com/search?' + JSON.parse(json).ip).map((results) =>
      console.log(results)));
}

// setTimeout + Promise
DelayP = (value, delay) => new P(new Promise((resolve) =>
    setTimeout(() => resolve(value), delay)));

DelayP(1, 1000).flatMap((v) =>
  // Runs at t=1 sec, v = 1
  DelayP(2+v, 2000).flatMap((w) =>
    // Runs at t=3 sec, w = 3
    DelayP(3+v+w, 3000).map((x) =>
      // Runs at t=6 sec, x = 7
      // Logs 15
      console.log(4+v+w+x))));

DelayP(1, 1000)
    // Runs at t=1 sec, v=1
    .map((v) => 2+v)
    // Runs at t=1 sec, w=3
    .map((w) => 3+w)
    // Runs at t=1 sec, x=6
    // Logs 10
    .map((x) => console.log(4+x));