ハッシュマップの二項演算とその法則性 - 檜山正幸のキマイラ飼育記 (はてなBlog)

先ほどの記事「JavaScriptでユーザー定義の二項演算子」の動機になったことを説明します。

JavaScriptのオブジェクトをハッシュマップ（連想配列、辞書）とみなして、そのあいだに二項演算を考えます。結局、Objectのメソッドにしましたが、以下のconnectとmergeがその二項演算です。その他に、論理式を作るときに必要になる述語（predicate）や関係（relation）も定義しています。

/** 集合の包含関係 */
function s_included(a1, a2) {
  return a1.every(function(item) {return (a2.indexOf(item) > -1);});
}

/** 集合の共通部分 */
function s_intersection(a1, a2) {
  // 重複は除外されない
  return a1.filter(function(item) {return (a2.indexOf(item) > -1);});
}

/** 2つのオブジェクトの、キー集合が包含関係にある */
Object.prototype.included = function(obj) {
  return s_included(Object.keys(this), Object.keys(obj));
};

/** 2つのオブジェクトの、キー集合の共通部分が空である */
Object.prototype.disjoint = function(obj) {
  var ks1 = Object.keys(this);
  var ks2 = Object.keys(obj);
  return (s_intersection(ks1, ks2).length === 0);
};

/** 2つのオブジェクトを、順序依存でマージする */
Object.prototype.connect = function(obj) {
  var self = this;
  var ks1 = Object.keys(self);
  var ks2 = Object.keys(obj);
  var r = {};
  // this を優先するので、ks1 の処理が後
  ks2.forEach(function(k){r[k] = obj[k];});
  ks1.forEach(function(k){r[k] = self[k];});
  return r;
};

/** 2つのオブジェクトを、順序に依存しないでマージする */
Object.prototype.merge = function(obj) {
  if (!this.disjoint(obj)) {
    throw new Error("Can not merge");
  }
  return this.connect(obj);
};

/** オブジェクトの等値判定
 *  http://stackoverflow.com/questions/201183/how-do-you-determine-equality-for-two-javascript-objects
 */
function EQ(obj1, obj2) {
  for (var i in obj1) {
    if (obj1.hasOwnProperty(i)) {
      if (!obj2.hasOwnProperty(i)) return false;
      if (obj1[i] != obj2[i]) return false;
    }
  }
  for (var j in obj2) {
    if (obj2.hasOwnProperty(j)) {
      if (!obj1.hasOwnProperty(j)) return false;
      if (obj1[j] != obj2[j]) return false;
    }
  }
  return true;
}

connectとmergeに関する計算法則を述べるには、中置演算子記法が便利です。次のように記号を定めましょう。

JavaScript	法則の記述用の記号
connect	>>
merge	++
{}	0
EQ	=
disjoint	⊥
included	⊆
&&	∧
三項式 ? :	含意 ⇒

connectは、非可換なベキ等モノイド演算になります。mergeは可換モノイド演算となりますが、全域では定義されません。定義される範囲内では、connectとmergeは一致して、単位元は共通です。包含関係（⊆）と無共通部分性（⊥、直交性）は、キー集合に関する性質です。

connect（>>）の計算法則を列挙すると：

(x >> y) >> z = x >> (y >> z)
0 >> x = x
x >> 0 = x
x >> x = x
x⊆y ⇒ y >> x = y

merge（++）の計算法則は、厳密なイコールでは記述できません。「定義されるなら等しい」を意味する記号を〜とすると：

(x ++ y) ++ z 〜 x ++ (y ++ z)
0 ++ x = x
x ++ 0 = x
x ++ y 〜 y ++ x

x ++ y が定義される条件は x⊥y です。(x ++ y) ++ z や x ++ (y ++ z) の定義可能条件は面倒くさいので、簡略化した形で書いてみると：

x⊥y ∧ y⊥z ∧ z⊥x ⇒ (x ++ y) ++ z = x ++ (y ++ z)
x⊥y ⇒ x ++ y = y ++ x

定義される範囲内でconnectとmergeが一致することは：

x⊥y ⇒ x >> y = y ++ x

以上の法則をJavaScriptで書いてみると次のようです。

/** connectの結合律 */
function connect_assoc(x, y, z) {
  return EQ(
    ((x) .connect (y)) .connect (z),
    (x) .connect ((y) .connect (z))
  );
}

/** connectの左単位律 */
function connect_lunit(x) {
  return EQ(
    ({}) .connect (x),
    x
  );
}

/** connectの右単位律 */
function connect_runit(x) {
  return EQ(
    (x) .connect ({}),
    x
  );
}

/** connectのベキ等律 */
function connect_idempo(x) {
  return EQ(
    (x) .connect (x),
    x
  );
}

/** connectの隠蔽される法則 */
function connect_hide(x, y) {
  return (
    (x) .included (y) ?
      EQ(
        (y) .connect (x),
        y
      )
      :
      trure
  );
}

/** mergeの結合律 */
function merge_assoc(x, y, z) {
  return (
    (x) .disjoint (y) && (y) .disjoint (z) && (z) .disjoint (x) ?
      EQ(
        ((x) .merge (y)) .merge (z),
        (x) .merge ((y) .merge (z))
      )
      :
      true
  );
}

/** mergeの左単位律 */
function merge_lunit(x) {
  return EQ(
    ({}) .merge (x),
    x
  );
}

/** mergeの右単位律 */
function merge_runit(x) {
  return EQ(
    (x) .merge ({}),
    x
  );

}

/** mergeの可換律 */
function merge_commu(x,  y) {
  return (
    (x) .disjoint (y) ?
      EQ(
        (x) .merge (y),
        (y) .merge (x)
      )
      :
      true
  );
}

/** connectとmergeの関係 */
function connect_and_merge(x,  y) {
  return (
    (x) .disjoint (y) ?
      EQ(
        (x) .connect (y),
        (x) .merge (y)
      )
      :
      true
  );
}

これらの等式／条件付き等式に出現する変数（x, y, z）は、実際には ∀x,y のような全称限量子で束縛されています。全称限量子は、多くのインスタンス（無限個）に対する主張になっています。無限個は無理でも、なるべく多くのインスタンスに対して表明（命題）を確認するのがプログラムのテストです。

今回取り上げた二項演算connect（>>）、merge（++）は、既存のハッシュマップから新しいハッシュマップを作り出す代数的操作です。よく知られた計算法則に従うので、扱いやすい演算になっています。こういう扱いやすい演算は、たいてい利用価値があるものです。