有向グラフから作るパスの圏

コードになにか問題があれば、ここに追記します。

/* PathCat.js */

/*
 * グラフ（有向グラフ）のインターフェース
 *
 * isVertex(x) -- xはグラフの頂点である
 * isEdge(x) -- xはグラフの辺である
 * eqVertex(a, b) -- 頂点aと頂点bは等しい
 * eqEdge(e, f) -- 辺eと辺fは等しい
 * src(e) -- 辺eの根本の頂点
 * trg(e) -- 辺eの行き先の頂点
 * vertex(...) -- 頂点のコンストラクタ
 * edge(...) -- 辺のコンストラクタ // 今回、PathCat側では使わない
 */

/*
 * 圏のインターフェース
 *
 * isObjct(x) -- xは圏の対象である
 * isMorphism(x) -- xは圏の射である
 * eqObj(a, b) -- 対象aと対象bは等しい
 * eqMor(f, g) -- 射fと射gは等しい
 * dom(f) -- 射fの域
 * cod(f) -- 射fの余域
 * id(a) -- 対象aの恒等射
 * composable(f, g) -- 射fと射gは結合（合成）可能である
 * compose(f, g) -- 射fと射gの結合
 * obj(...) -- 対象のコンストラクタ
 * mor(...) -- 射のコンストラクタ
 */

/* 一般的にも使えそうな関数（大域関数） */

function isArray(x) {
  return (
    typeof x === 'object' && x instanceof Array
  );
}

/* ここから圏（構成）の定義 */

// グラフから圏を作るコンストラク
function PathCat(graph) {
  this.graph = graph;
}

PathCat.prototype.isObject = function(x) {
  return this.graph.isVertex(x);
};

PathCat.prototype.isMorphism = function (x) {
  if (!isArray(x) || x.length < 2) {
    return false;
  }
  var n = x.length - 2; // リスト内の辺の個数
  var g = this.graph;
  if (!(
    // 両端は頂点
    g.isVertex(x[0]) && g.isVertex(x[n + 1])
  )) return false;
  if (n == 0) {
    return x[0] === x[1];
  }
  // n > 0 のケース
  var srcVertex = x[0];
  for (var i = 1; i <= n; i++) {
    if (!(
      g.eqVertex(srcVertex, g.src(x[i]))
    )) return false;
    srcVertex = g.trg(x[i]);
  }
  if (!(
    g.eqVertex(g.trg(x[n]), x[n + 1])
  )) return false;
  return true;
};

PathCat.prototype.eqObj = function(x, y) {
  return this.graph.eqVertex(x, y);
};

PathCat.prototype.eqMor = function(x, y) {
  if (!this.isMorphism(x) || !this.isMorphism(y))
    throw "not a morphism";
  var n = x.length - 2; // リスト内の辺の個数
  var g = this.graph;
  if (!(
    g.eqVertex(x[0], y[0]) && g.eqVertex(x[n + 1], y[n + 1])
  )) return false;
  for (var i = 1; i <= n; i++) {
    if (!g.eqEdge(x[i], y[i])) return false;
  }
  return true;
};

PathCat.prototype.dom = function(f) {
  if (!this.isMorphism(f)) throw "not a morphism";
  return f[0];
};

PathCat.prototype.cod = function(f) {
  if (!this.isMorphism(f)) throw "not a morphism";
  return f[f.length - 1];
};

PathCat.prototype.id = function(a) {
  if (!this.isObject(a)) throw "not an object";
  return [a, a];
};

PathCat.prototype.composable = function(f, g) {
  return (
    this.eqObj(this.cod(f), this.dom(g))
  );
};

PathCat.prototype.compose = function(f, g) {
  if (!this.composable(f, g))
    throw "cannot compose";
  // ここで、f, gにpopやshiftを使ってはいけない！
  // もとのf, gを破壊してしまう
  var a = new Array();
  var n = f.length - 1;
  for (var i = 0; i < n; i++) {
    a[i] = f[i];
  }
  n--; // ここでnが減っている、注意
  for (var j = 1; j < g.length; j++) {
    a[n + j] = g[j];
  }
  return a;
};

PathCat.prototype.obj = function(/*varargs*/) {
  return this.graph.vertex.apply(null, arguments);
};

PathCat.prototype.mor = function(/*varargs*/) {
  var a = Array.apply(null, arguments);
  if (!this.isMorphism(a)) throw "invalid argument";
  return a;
};