このブログの更新は Twitterアカウント @m_hiyama で通知されます。
Follow @m_hiyama

メールでのご連絡は hiyama{at}chimaira{dot}org まで。

はじめてのメールはスパムと判定されることがあります。最初は、信頼されているドメインから差し障りのない文面を送っていただけると、スパムと判定されにくいと思います。

［参照用 記事］

完全実装付きでもう一度お送りします、しりとりの圏

雑記／備忘

昨日のセミナーで、圏の簡単な事例として「しりとりの圏」を出したのですが、ハッキリとしたイメージを持てなかった人も多かったようです。

“技術者／プログラマ”であれば、実際に動くコードを持ち出すのが手っ取り早いのかな、と思い、しりとりの圏をJavaScriptで実装してみました。ここでは、このJavaScriptコードにそって、あらためてしりとりの圏を解説します。セミナーの内容や知識をまったく前提にしていません。白紙からの説明です。ただし、以前の記事（2006年8月21日）は参照する必要があります。

以前の記事とJavaScriptソースコードを並べて表示したい人は、次のリンクをクリックしてください。別なウィンドウ／タブで2つの参考エントリーが開くはずです。

JavaScriptソースコードは、このエントリーの最後にも貼り付けてあります。Firebugで実験するときは、次のようなHTMLファイルをロードしてからFirebugコンソールを操作するといいでしょう。



<html>

  <head>

    <title>Hiragana Shiritori Cateogry</title>

    <script src="HSCat.js"></script>

  </head>

  <body>

    <h1>Hiragana Shiritori Cateogry</h1>

    <ol>

      <li><b>HSCat.isObject(x)</b> （ x は任意 ）</li>

      <li><b>HSCat.isMorphism(x)</b> （ x は任意 ）</li>

      <li><b>HSCat.dom(s)</b> （ s は射 ）</li>

      <li><b>HSCat.cod(s)</b> （ s は射 ）</li>

      <li><b>HSCat.compose(s, t)</b> （ s, t は射 ）</li>

      <li><b>HSCat.id(a)</b> （ a は対象 ）</li>

    </ol>

  </body>

</html>

内容：

  1. これからやることは
  2. 対象の集合
  3. 射の集合
  4. 射の域
  5. 射の余域
  6. 2つの射の結合
  7. 恒等
  8. かつて出した実例を今実行してみる
  9. まとめ
  10. JavaScriptのソースコード

これからやることは

圏論の次の概念をJavaScripプログラムで表現していきます。

  1. 対象（object）の集合
  2. 射（morphism）の集合
  3. 射の域（domain）
  4. 射の余域（codomain）
  5. 2つの射の結合（合成；composition）
  6. 恒等（identity）

具体例はもちろんしりとりの圏です。文字としてひらがなを使うので Hiragana Shiritori Category、略称は HSCat とします。

HSCatは、「はじめての圏論 その第1歩：しりとりの圏」で説明しているものです。ただし、対象の集合を、文字（character）の集合ではなくて整数の集合に変更しました。それは、次の2つの理由からです。

  1. JavaScriptでは文字型がないので、文字の代わりに、対応するUnicode文字番号を使うことにしました。
  2. 「文字と文字列が似てるので、対象と射を区別できなかったり、混乱が生じるのではないか」という意見がセミナー懇親会で出たので、「対象は整数」のほうがいいかも、と考えました。

対象の集合

対象の集合は、もと（2006年8月）の記事では、H={ぁ, あ, ぃ, い, ..., ん, ー} ですが、今回は H={12353, 12354, 12355, 12356, ..., 12435, 12540} となります*1。ここに並んだ整数は、ひらがな文字に対するUnicode文字番号（コードポイント）です。

16進表記 10進表記 備考
U+3041 から U+308F 12353 から 12431 'ぁ' から 'わ' までの79個
U+3092 12434 'を'
U+3093 12435 'ん'
U+30FC 12540 'ー'

番号からどんな文字かを想像するのは難しいので、JavaScriptのインタプリタから使うために次の関数を用意しました。



/*

 * 対話的に使うための便利関数

 */
// 文字の番号を返す

function ord(c) {

  return c.charCodeAt(0);

}
// 番号に対応する文字を返す

function chr(n) {

  return String.fromCharCode(n);

}

さて、JavaScriptデータが、圏HSCatの対象であるかどうかを判定するには次の HSCat.isObject を使います。関数定義内で使われている補助的関数（isHiraganaCharCodeなど）は、JavaScriptの全ソースコードを参照してください。[追記 date="2009-04-27"]整数かどうかを判定するには、typeof x === 'number' && Math.floor(x) === x とすれば良かったですね。でもまーいいや、今度からそうすることにしてママです。[/追記]



// この圏の対象かどうかを判定

HSCat.isObject = function(x) {

  return (

    (typeof x === 'number')

    &&

    isHiraganaCharCode(x)

  );

};

対話例：



>>> ord('た')

12383

>>> HSCat.isObject(12383)

true

>>> ord('a')

97

>>> HSCat.isObject(97)

false

>>> chr(21223) // 2122はアテズッポウ

"勧"

>>> HSCat.isObject(2122)

false

>>> HSCat.isObject("hello")

false

射の集合

JavaScriptデータが、圏HSCatの射であるかどうかを判定するには次の HSCat.isMorphism を使います。



// この圏の射かどうかを判定

HSCat.isMorphism = function(x) {

  return (

    (typeof x === 'string' || x instanceof String)

    &&

    isHiraganaNEString(x)

  );

};

対話例：



>>> HSCat.isMorphism("たぬき")

true

>>> HSCat.isMorphism("hello")

false

>>> HSCat.isMorphism(12383)

false

>>> HSCat.isMorphism("")

false

>>> HSCat.isMorphism("あ")

true

>>> HSCat.isMorphism("はれまけろ")

true

>>> HSCat.isMorphism("はれまけろ。")

false

射の域

圏HSCatの射sに対して、その域を求めるには次の HSCat.dom を使います。射でないデータを HSCat.dom に渡すとエラーになります。



// 射の域

HSCat.dom = function(s) {

  if (!HSCat.isMorphism(s)) throw "not a morphism";

  return first(s);

};

対話例：



>>> HSCat.dom("たぬき")

12383

>>> chr(12383)

"た"

>>> HSCat.dom("あ")

12354

>>> chr(12354)

"あ"

>>> HSCat.dom("")

not a morphism

>>> HSCat.dom(12354)

not a morphism

射の余域

圏HSCatの射sに対して、その余域を求めるには次の HSCat.cod を使います。射でないデータを HSCat.cod に渡すとエラーになります。



// 射の余域

HSCat. cod = function(s) {

  if (!HSCat.isMorphism(s)) throw "not a morphism";

  return last(s);

};

対話例：



>>> HSCat.cod("たぬき")

12365

>>> chr(12365)

"き"

>>> HSCat.cod("あ")

12354

>>> chr(12354)

"あ"

>>> HSCat.cod("")

not a morphism

>>> HSCat.cod(12365)

not a morphism

2つの射の結合

圏HSCatの2つの射s, tに対して、それらの結合を求めるには次の HSCat.compose を使います。射でないデータを HSCat.compose に渡すとエラーになります。s, tが共に射であっても、結合可能性の条件を満たしてないならエラーです。



// sとtが結合可能かどうかを判定

HSCat.composable = function(s, t) {

  return (

    HSCat.isMorphism(s)

    &&

    HSCat.isMorphism(t)

    &&

    HSCat.cod(s) === HSCat.dom(t) // 結合可能性の条件

  );

};
// sとtを結合（合成）

HSCat.compose = function(s, t) {

  if (!HSCat.composable(s, t)) throw "cannot compose";

  return sconc(s, t);

};

対話例



>>> HSCat.compose("たぬき", "きつね")

"たぬきつね"

>>> HSCat.compose("あ", "あか")

"あか"

>>> HSCat.compose("あか", "か")

"あか"

>>> HSCat.compose("あ", "あ")

"あ"

>>> HSCat.compose("たぬき", "ねこ")

cannot compose

>>> HSCat.compose("hello", "orange")

cannot compose

>>> HSCat.compose("ここ", "こども")

"ここども"

>>> HSCat.compose("こども", "もも")

"こどもも"

>>> HSCat.compose("とまと", "とんぼ")

"とまとんぼ"

>>> HSCat.compose("とまと", "とまと")

"とまとまと"

恒等

圏HSCatの対象a（ひらがな文字の番号）に対して、その恒等射を求めるには次の HSCat.id を使います。対象でないデータを HSCat.id に渡すとエラーになります。



// 恒等

HSCat.id = function(a) {

  if (!HSCat.isObject(a)) throw "not an object";

  return unit(a);

};

対話例：



>>> ord('た')

12383

>>> HSCat.id(12383)

"た"

>>> HSCat.compose(HSCat.id(12383), "たぬき")

"たぬき"

>>> HSCat.compose("たぬき", HSCat.id(ord("き")))

"たぬき"

>>> HSCat.compose(HSCat.id(HSCat.dom("たぬき")), "たぬき")

"たぬき"

>>> HSCat.compose("たぬき", HSCat.id(HSCat.cod("たぬき")))

"たぬき"

かつて出した実例を今実行してみる

「はじめての圏論 その第1歩：しりとりの圏」には、first, last, unitなどの関数を使った法則の記述や実例が出てきます。HSCat.js内に、first, last, unitが定義されているので、これらの実例を試すことができます。ただし、次の点に注意してください。

  1. 演算子「;」は定義できないので、s;t ではなくて sconc(s, t) と書きます（sconc = Shiritori CONCatenation）。
  2. unitは、文字ではなくて文字番号に対して定義されています。

次の例は「はじめての圏論 その第1歩：しりとりの圏」のものです。



first("きゅーり") = き

last("きゅーり") = り

HSCat.jsで実行すると次のようになります。



>>> first("きゅーり")

12365

>>> chr(12365)

"き"

>>> last("きゅーり")

12426

>>> chr(12426)

"り"

同じように、「はじめての圏論 その第1歩：しりとりの圏」の例をHSCat.jsで実行してみましょう。

first/lastとunitに関する法則の実例：



first(unitあ) = first("あ") = あ

last(unitあ) = last("あ") = あ



>>> ord('あ')

12354

>>> first(unit(12354))

12354

>>> first(unit(12354)) == 12354

true

>>> last(unit(12354))

12354

>>> last(unit(12354)) == 12354

true

first/lastと結合に関する法則の実例：



first("こぶた";"たぬき") = first("こぶたぬき") = first("こぶた") = こ

last("こぶた";"たぬき") = last("こぶたぬき") = last("たぬき") = き



>>> first(sconc("こぶた", "たぬき"))

12371

>>> first("こぶた")

12371

>>> first(sconc("こぶた", "たぬき")) == first("こぶた")

true

>>> last(sconc("こぶた", "たぬき"))

12365

>>> last("たぬき")

12365

>>> last(sconc("こぶた", "たぬき")) == last("たぬき")

true

結合法則の実例：



("たぬき";"きつね");"ねこ"  = "たぬきつね";"ねこ"  = "たぬきつねこ"

 "たぬき";("きつね";"ねこ") = "たぬき";"きつねこ" = "たぬきつねこ"



>>> sconc(sconc("たぬき", "きつね"), "ねこ")

"たぬきつねこ"

>>> sconc("たぬき", sconc("きつね", "ねこ"))

"たぬきつねこ"

>>> sconc(sconc("たぬき", "きつね"), "ねこ") == sconc("たぬき", sconc("きつね", "ねこ"))

true

単位法則の実例：



unitき;"きゅーり" = "き";"きゅーり" = "きゅーり"

"きゅーり";unitり = "きゅーり";"り" = "きゅーり"



>>> sconc(unit(ord('き')), "きゅーり")

"きゅーり"

>>> sconc(unit(ord('き')), "きゅーり") == "きゅーり"

true

>>> sconc("きゅーり", unit(ord('り')))

"きゅーり"

>>> sconc("きゅーり", unit(ord('り'))) == "きゅーり"

true

まとめ

圏論の概念を、言葉／式／プログラム断片でどう表現するか表にまとめておきます。次の点に注意してください。

  1. 圏Cの対象の集合を Obj(C)、または |C| と書きます。
  2. 圏Cの射の集合を Mor(C)、または圏全体を表す記号を流用（乱用）して C と書きます。
  3. 対象aの恒等は、id(a) よりは ida と書くのが普通です。
  4. 「圏C内で … が成立する」を「… in C」と（ここでは）書くことにします。
概念を言葉で表現すると 式で表現すると プログラム断片で表現すると
aは圏HSCatの対象である a∈Obj(HSCat) HSCat.isObject(a)
sは圏HSCatの射である s∈Mor(HSCat) HSCat.isMorphism(s)
射sの域は対象aである dom(s) = a in HSCat HSCat.dom(s) == a
射sの余域は対象bである cod(s) = b in HSCat HSCat.cod(s) == b
射sは対象aから対象bへの射である s:a→b in HSCat HSCat.dom(s) == a && HSCat.cod(s) == b
射sと射tは結合可能である cod(s) = dom(t) in HSCat HSCat.cod(s) == HSCat.dom(t)
射uは、射sと射tの結合（合成）である u = s;t in HSCat u == HSCat.compose(s, t)
射iは、対象aに対する恒等射である i = ida in HSCat i == HSCat.id(a)

納得がいくまで実験してみてください。とにかく、
目や手を動かしてやってみないとハジマリません。ジッと考えていても、どうせ分かりません。

JavaScriptのソースコード



/* HSCat.js -- Hiragana Shiritori Category */
/*

 * 一般的な文字列処理関数

 */
// 文字列の連接

function concat(s, t) { // s, t は文字列と仮定

  return String.prototype.concat.call(s, t);

}
// 文字列の最初の文字（ただし文字番号が返る）

function first(s) { // s は文字列と仮定

  return s.charCodeAt(0);

}
// 文字列の最後の文字（ただし文字番号が返る）

function last(s) { // s は文字列と仮定

  return s.charCodeAt(s.length - 1);

}
// 文字列の最初の文字を除いたもの

function butfirst(s){ // s は文字列と仮定

  return s.substring(1);

}
// 特定の1文字からなる文字列（引数は文字番号）

function unit(c) { // c は整数と仮定

  return String.fromCharCode(c);

}
// ひらがな文字かどうかを判定（引数は文字番号）

function isHiraganaCharCode(c) { // c は整数と仮定

  return (

    (0x3041 <= c && c <= 0x308F) // 'ぁ' から 'わ'

    ||

    c === 0x3092 // 'を'

    ||

    c === 0x3093 // 'ん'

    ||

    c === 0x30FC // 'ー'

  );

}
// 非空（Non Empty）なひらがな文字列かどうかを判定

function isHiraganaNEString(s) { // s は文字列と仮定

  if (s.length === 0) return false;

  for (var i = 0; i < s.length; i++) {

    if (!isHiraganaCharCode(s.charCodeAt(i))) return false;

  }

  return true;

}
// しりとり方式の文字列連接 （sconc = Shiritori CONCat）

function sconc(s, t) { // s, t は文字列と仮定

  return concat(s, butfirst(t));

}
/*

 * 対話的に使うための便利関数

 */
// 文字の番号を返す

function ord(c) {

  return c.charCodeAt(0);

}
// 番号に対応する文字を返す

function chr(n) {

  return String.fromCharCode(n);

}
/* ================================================== */
/*

 * ひらがなのしりとり圏（HSCat）の実装

 */
// 名前空間を提供するオブジェクト

var HSCat = {

};
// この圏の対象かどうかを判定

HSCat.isObject = function(x) {

  return (

    (typeof x === 'number')

    &&

    isHiraganaCharCode(x)

  );

};
// この圏の射かどうかを判定

HSCat.isMorphism = function(x) {

  return (

    (typeof x === 'string' || x instanceof String)

    &&

    isHiraganaNEString(x)

  );

};
// 射の域

HSCat.dom = function(s) {

  if (!HSCat.isMorphism(s)) throw "not a morphism";

  return first(s);

};
// 射の余域

HSCat. cod = function(s) {

  if (!HSCat.isMorphism(s)) throw "not a morphism";

  return last(s);

};
// sとtが結合可能かどうかを判定

HSCat.composable = function(s, t) {

  return (

    HSCat.isMorphism(s)

    &&

    HSCat.isMorphism(t)

    &&

    HSCat.cod(s) === HSCat.dom(t) // 結合可能性の条件

  );

};
// sとtを結合（合成）

HSCat.compose = function(s, t) {

  if (!HSCat.composable(s, t)) throw "cannot compose";

  return sconc(s, t);

};
// 恒等

HSCat.id = function(a) {

  if (!HSCat.isObject(a)) throw "not an object";

  return unit(a);

};

*1:H={ぁ, あ, ぃ, い, ..., ん, ー} で無闇と欲情してしまった人がいたようですが、H={12353, 12354, 12355, 12356, ..., 12435, 12540} だとエロスを感じるのは難しいでしょう。