Categories in Javascript

cats.js

var util = require("util");

/** Source: http://blog.thatscaptaintoyou.com/haskells-foldr-in-javascript/ **/
function foldr(fn, ult, xs) {
  if (xs.length == 0) return ult;
  if (xs.length == 1) return fn(xs[0], ult);
  else return fn(xs.splice(0, 1)[0], foldr(fn, ult, xs));
}

var cats = {};
cats.noimpl = function() { throw new Error("Not implemented."); };

/* Category */
cats.Category = function() { };
cats.Category.prototype.dot = cats.noimpl;

/* Functor */
cats.Functor = function() { };
cats.Functor.prototype.fmap = cats.noimpl;

/* Applicative */
cats.Applicative = function() { };
util.inherits(cats.Applicative, cats.Functor);
cats.Applicative.prototype.pure = cats.noimpl;
cats.Applicative.prototype.ap = cats.noimpl;
//cats.Applicative.prototype.apl = liftA2(const(id));
//cats.Applicative.prototype.apr = liftA2(const);

/* Monad */
cats.Monad = function() { };
util.inherits(cats.Monad, cats.Applicative);
cats.Monad.prototype.then_ = function(k) {
  return this.then(function() { return k; });
}
cats.Monad.prototype.then = cats.noimpl;
cats.Monad.liftM = function(f, m) {
  return m.then(function(x1) {
    return m.constructor.unit(f(x1));
  });
};

var dot = function(f, g) {
  return function(x) {
    return f(g(x));
  };
};

var shift = function(d) {
  for (var k in d) {
    return [k, d[k]];
  }
};

var Op = function(x, m, as) {
  this.x = x;
  this.m = m;
  this.as = as;
};

Op.parse = function(args) {
  if (args[0].constructor === Object) {
    var item = shift(args[0]);
    return new Op(item[0], item[1], args.slice(1));
  }
  return new Op(null, args[0], args.slice(1));
};

/* "Do-notation" */
cats.Monad.do = function() {
  var zs = [[].slice.call(arguments)];
  return function() {
    if (arguments.length === 0) {
      return (function(zs) {
        var q = "";
        for (var i = 0; i < zs.length; i++) {
          var body = zs[i].as.length > 0 ?
            "zs[" + i + "].m(" + zs[i].as + ")" :
            "zs[" + i + "].m";
          if (q) {
            q = zs[i].x ?
              body + ".then(function(" + zs[i].x + "){ return " + q + " })" :
              body + ".then(function(){ return " + q + " })";
          } else {
            q = body;
          }
        }
        return eval("(" + q + ")");
      })(zs.map(Op.parse));
    }
    zs.unshift([].slice.call(arguments));
    return arguments.callee;
  };
};

/* Identity */
var Id = function(x) {
  if (!(this instanceof Id)) return new Id(x);
  cats.Monad.call(this);
  this._ = x;
};

util.inherits(Id, cats.Monad);

Id.prototype.then = function(g) {
  return g(this._);
};
Id.prototype.inspect = function() {
  return "(Id " + (this._.inspect ? this._.inspect() : this._) + ")";
};

Id.unit = Id;

var t0 = Id(1).then(function(x) {
  return Id(2).then(function(y) {
  return Id(3).then(function(z) {
  return Id([x, y, z]);
  }); }); });

var t0_ = cats.Monad.do
  ({ x: Id(1) })
  ({ y: Id(2) })
  ({ z: Id(3) })
  (Id, "[x, y, z]")();

console.log(t0);
console.log(t0_);

var Cont = function(k) {
  if (!(this instanceof Cont)) return new Cont(k);
  this.k = k;
};

util.inherits(Cont, cats.Monad);

Cont.unit = function(a) {
  return Cont(function(k) {
    k(a);
  });
};

Cont.prototype.then = function(g) {
  var self = this;
  return Cont(function(next) {
    self.k(function(r) {
      g(r).run(next);
    });
  });
};

Cont.prototype.run = function(next) {
  this.k(next || function() {});
};

Cont.callCC = function(f) {
  return Cont(function(k) {
    f(function(a) {
      return Cont(function() { k(a); });
    }).run(k);
  });
};

var t1 = cats.Monad.do
  (Cont.unit(1))();

t1.run(console.log);

var t1_ = cats.Monad.do
  ({ k: Cont.callCC(function(k) {
    return cats.Monad.do
      (k("hi there"))
      (k("yayayaya"))
      (Cont.unit(1))();
  }) })();

t1_.run(console.log);

var pause = Cont(function(k) {
  setTimeout(k, 1000);
});

var print = function(s) {
  return Cont(function(k) {
    console.log(s);
    k();
  });
};

var t1__ = cats.Monad.do
  (pause)
  (print("hi"))();

t1__.run(console.log);

var Maybe = function() {};
util.inherits(Maybe, cats.Monad);

var Just = function(a) {
  if (!(this instanceof Just)) return new Just(a);
  this._ = a;
};
util.inherits(Just, Maybe);
Just.prototype.fmap = function(f) {
  this._ = f(this._);
  return this;
};
Just.prototype.inspect = function() {
  return "(Just " + (this._.inspect ? this._.inspect() : this._) + ")";
};

var Nothing = function() {
  if (!(this instanceof Nothing)) return new Nothing();
};
util.inherits(Nothing, Maybe);
Nothing.prototype.fmap = function() {
  return this;
};
Nothing.prototype.inspect = function() {
  return "(Nothing)";
};

cats.Arrow = function() { };
util.inherits(cats.Arrow, cats.Applicative);
var fmap = function(s, f) {
  return function(x) {
    var item = s(x);
    return [f(item[0]), fmap(item[1], f)];
  };
};

var repeat = function(a) {
  return function as() {
    return [a, as];
  };
};

var intsFrom = function(n) {
  return function() {
    return [n, intsFrom(n + 1)]
  };
};

var scan = function(f, i) {
  return (function(a) {
    return function(b) {
      var a_ = f(a, b);
      return [a_, scan(f, a_)];
    };
  })(i);
};

var accumSum = scan(function(x, y) { return x + y; }, 0);


/** Adapted from https://github.com/leonidas/codeblog/blob/master/2012/2012-01-08-streams-coroutines.md **/
var Coroutine = function(s) {
  if (!(this instanceof Coroutine)) return new Coroutine(s);
  this.s = s;
};
util.inherits(Coroutine, cats.Arrow);
Coroutine.prototype.fmap = function(f) {
  return Coroutine(fmap(this.s, f));
};
Coroutine.prototype.dot = function(g) {
  return Coroutine((function next(f, g) {
    return function(i) {
      var xs = g(i), ys = f(xs[0]);
      return [ys[0], next(ys[1], xs[1])];
    };
  })(this.s, g.s));
};
Coroutine.arr = function(f) {
  return Coroutine(function next(i) {
    return [f(i), next];
  });
};
Coroutine.prototype.first = function() {
  return Coroutine((function next(s) {
    return function(xy) {
      var xs = s(xy[0]);
      return [[xs[0], xy[1]], next(xs[1])];
    };
  })(this.s));
}
Coroutine.prototype.evalList = function(xs) {
  var res = [], item;
  for (var i = 0; i < xs.length; i++) {
    var item = this.s(xs[i]);
    this.s = item[1];
    res.push(item[0]);
  };
  return res;
};

console.log(Coroutine(intsFrom(1)).evalList(new Array(5).join(null)));
console.log(Coroutine(intsFrom(1)).fmap(function(x) { return x * 3; }).evalList([null, null]));
console.log(Coroutine(intsFrom(10)).dot(Coroutine(intsFrom(12))).evalList(new Array(3).join(null)));

var sumFrom = Coroutine(accumSum).dot(Coroutine(intsFrom(0)));
console.log(sumFrom.first().evalList([[1,2], [3,4], [5,6]]));

var t2 = Just(1);
var t2_ = Nothing();
console.log("t2:", t2.fmap(function(x) { return x + 1; }));
console.log("t2_:", t2_.fmap(function(x) { return x + 1; }));

var MaybeT = function(m) {
  var maybeT = function(a) {
    if (!(this instanceof maybeT)) return new maybeT(a);
    this.a = a;
  };
  util.inherits(maybeT, cats.Monad);
  maybeT.prototype.then = function(f) {
    var self = this;
    this.a = this.a.then(function(v) {
      if (v instanceof Nothing) return m.unit(v);
      if (v instanceof Just) return f(v._).a;
    });
    return this;
  }
  maybeT.prototype.inspect = function() {
    return "(MaybeT " + (this.a.inspect ? this.a.inspect() : this.a) + ")";
  };
  maybeT.unit = function(a) {
    return maybeT(m.unit(Just(a)));
  };
  maybeT.lift = function(m1) {
    return maybeT(cats.Monad.liftM(Just, m1));
  };
  maybeT.guard = function(b) {
    return b ? maybeT.unit() : maybeT.mzero();
  };
  maybeT.mzero = function() {
    return maybeT(m.unit(Nothing()));
  };
  maybeT.mplus = function(x, y) {
    return maybeT(x.a.then(function(v) {
      if (v instanceof Nothing) return y.a;
      if (v instanceof Just) return m.unit(v);
    }));
  };
  maybeT.msum = foldr.bind(null, maybeT.mplus, maybeT.mzero());
  return maybeT;
};

var MaybeId = MaybeT(Id);
var m0 = MaybeId.unit(1).then(function(x) {
  return MaybeId.lift(Id.unit(3)).then(function(y) {
    return MaybeId.unit(x + y)
  });
});

var m0_ = cats.Monad.do
  ({ x: MaybeId.unit(1) })
  ({ y: MaybeId.lift(Id.unit(3)) })
  (MaybeId.unit, "x + y")();

console.log(m0);
console.log(m0_);

var getLine = Cont(function(k) {
  process.stdin.resume();
  process.stdin.once("data", function(x) {
    process.stdin.pause();
    k(x.toString().slice(0, -1))
  });
});

var isValid = function(pwd) {
  return pwd.length > 8;
};

var getPassword = cats.Monad.do
  (print("Enter a password:"))
  (getLine)();

var MaybeCont = MaybeT(Cont);

var getValidPassword = cats.Monad.do
  ({ s: MaybeCont.lift(getPassword) })
  (dot(MaybeCont.guard, isValid), "s")
  (MaybeCont.unit, "s")();

MaybeCont.msum([getValidPassword, getValidPassword]).a.run(console.log);

//var t3 = cats.Monad.do
//  ({ x: getValidPassword })
//  (MaybeCont.unit, "x")();
//
//t3.a.run(function(validPwd) {
//  console.log("Your new password is:", validPwd);
//});