技術者／プログラマのためのモナドと圏論 第1回 行ってきた

またまた行ってきた。前回（論理・ラムダ・圏）、タイトルに「圏」とありながら、実際は圏の話がほとんどできなかったことを受けてはじまった、新シリーズ。細かいところや背景知識なんてわかるわけがない（数学ほとんどやってないし）ので、わかった範囲で書きとめておく。間違いまくってる可能性大。

全体的に
教科書的に進めようかと思っていたそうだが、檜山さんが体調不良で方針転換。形式的なものより、お絵かきメインで進めることになった。

というわけで、第1回の予定はこうでした。
  1. まえおき／まえせつ
  2. いろいろな図の描き方
  3. 圏の定義と実例
  4. 休憩
  5. 行列の圏で遊ぶ
  6. コレクション・データ
実際は、3の途中まで（休憩はやったよ！）で終了しました:-D

まえおき／まえせつ
シリーズ全体の目標としては…
  1. 圏の基本概念を学ぶ
  2. モナドの実例をたくさん知る
  3. モナド法則に慣れる
  4. モナドのクライスリ圏の作り方を知る
  5. モナドがモノイドであることを理解する
こんなとこで、4くらいまではいきたいそうだ。自分としては、ここまでいければ当面満足なので、しばらくは独学であがかなくてもよさそうなのが非常に嬉しい。

今日の目標は…
  1. 圏の定義と直感的なイメージの両方を知る
  2. お絵かき実習する
  3. 圏の実例をいじって体になじませる
  4. 横道にそれて面白そうな話題を紹介する
モナドの意義
今のところさっぱりわかっていないモナドの意義。計算の観点からは、
  • コレクション・データ構造に統一的見方を与える、らしい
  • 関数計算を拡張・一般化できる、らしい
  • 文や式の構文論を整理できる
どれもこれも現段階では具体例がわからないのでいまいちピンと来ないんだけど、1番目と2番目はHaskellやらの関数型言語をさわる際に、（気持ち・理解的な）役に立ちそう。特に、関数計算に部分関数、エラー・例外、状態・副作用などを導入する形で拡張するのに出てくる、というあたりはとても興味深い。楽しみだ。
圏論の観点からの意義は、知らない語ばっかりでいまいちよくわからなかった。好奇心の観点からは、色んなものがモナドでっせーみたいな話のようで、もしかしたら後で出てくる「色んなものを圏の枠組みで見ると同じように見え、同じような問題が同じように解ける」とかいう話と関係しているのかもしれない。が、よくわからない。

回路とか関数とかの書き方
[ ボックス図 ]
関数をブラックボックスとして記述。


[ オダンゴ図 ]
ボックス図の省略版。箱を書くのがめんどうくさいので生まれたらしい。ボックス図もそうだが、ブラックボックスの内部を書くこともできる。


[ ストリング図 ]
オダンゴが小さくなった感じ。

さて、以下の3つの関数で…
  • f(x, y) = 3x + y
  • g(z) = z + 1
  • h(x) = x * x + x
f(x, y) と g(z) のComposition（結合・合成）をオダンゴ図で書いてみる。

きたねええええええ！
…h(x) をオダンゴ図で書いてみる。

h が少し面白いのは、普通に書こうとすると、x が1つしかないので2乗などができずに困ってしまう点。xを複製するようなワイヤリングをすればいいのだけど、このようにに、引数も消尽され得るリソースだと考えると、コンピュータによる計算のリソースセンシティブな部分をうまく表現できるようだ。これは、論理の世界で考えると線形論理に対応しているらしい。なんか前回そんなことを言っていた。この複製（や交差）なんかのワイヤリングを計算と考えることもできる。
テキスト表記（Symbolic Calculationというらしい）だとわからなかったことが、絵算（Pictorial Calculationというらしい）だとわかる、というのも面白いところ。これらは一長一短があるので、状況によって使い分けるといい、とのこと。

引数・戻り値の数
引数は複数あるが、戻り値は常に1つでないといけないのか？
そんなことはない。実際、先ほどの f と g の合成関数の例では、ボックス（ダンゴ）の位置を少し変えれば（合成関数自体は同じでも）簡単に戻り値が複数あるような関数に変更できる。


が、人間は多値（特に戻り値）を扱うのはあまり得意ではないので、1つにしていることが多い。複数必要になった場合には、タプルで対応する。

f: A, B => C

これはAとBの2引数を取り、Cを返す関数だが、

f': A×B => C

このような、A×B型のタプルを引数として取る関数とまぁ同じと考えて良い。掛け算記号の×は、タプル型をあらわす。タプルは色んな表記法があり、（特にプログラミング言語では）()だったり[]だったり{}だったりする。プログラミング言語から中立であることを示しつつタプルを表記するため、<>をよく使うらしい。

f'(<x, y>) = f(x, y)
g'(x, y) = g(<x, y>)

これは、絵算で言うと、ワイヤーを束ね（て1本にす）ることに相当する。フラットケーブルとかそういうやつ。こんな感じ。

ダンゴ図で書くときは、右下にちっちゃく書いてるように、ゴムみたいなので束ねるように書いたりする。

ストリング図とアロー図
今まで書いてきた、ボックス図・オダンゴ図は、どちらもストリング図という種類になるが、一般的に図（Diagram）というと、たいていはアロー図を指す。以下のような関数について考えてみる。
f: A => B

[ ストリング図 ]

関数が箱（または点）、引数や戻り値が矢印（アロー）になっている。

[ アロー図 ]

関数が矢印（アロー）、引数や戻り値が点になっている。
# なんか、圏っぽい。てか圏のセミナーでした。

この2つの違いは単に趣味的なものではなく、大きな差である、らしい。ちなみに、アロー図はペースティング（Pasting）図や球状（Globular）図とも言うらしいが、これは絵を2次～3次元に拡張した場合に円や球に見えるから、だそう。スライドには高次圏とか書いてあるし、とりあえず今はわからなさそうなので飛ばしてしまう。

矢印で何を表すのか
矢印は、色んな意味で使われるので注意が必要。違うことが同じ記号や同じ言葉で語られるため、混乱しやすい。これから出てくるものとしては…
  • 要素関の対応関係（集合の要素、元同士の対応関係）
  • 集合同士の対応関係（集合同士の対応関係、写像？）
  • 関手（どうやら圏と圏の対応のようなものらしい）
  • 自然変換（関手同士の対応のようなものに見えるが）
こんなものが、すべて矢印であらわされる。

圏、しりとり圏
はじめての圏論で書かれていた、しりとり圏をもとに圏を説明。以下、しりとり圏の構成要素の転記。
  1. 対象の集合: H -- ひらがな文字全体の集合
  2. 射の集合: HStr -- ひらがな文字列全体の集合
  3. 域 dom と余域 cod ： first, last : HStr => H（最初と最後の文字）
  4. 恒等 id : unit : H => HStr（1文字からなる文字列）
  5. 結合（composition） : しりとり結合 s;t は last(s) = first(t) のときだけ定義される
まずは、圏のなんとなーくのイメージをつかむ。といっても、今まで出てきた話の延長線上にある。というか、もちろんそういう風に話を持っていっているんだと思います :-D

対象というのは、アローダイアグラムでの点みたいなもの。射というのは、アローダイアグラムでの矢印のようなもの。域というのは、矢印の出発点側にくっついている点のようなもの。余域というのは、アローダイアグラムの終点側についている点のようなもの。

結合は、（つなげられる）矢印同士をつなげること。

# f;g は、fとgの結合です。

恒等は…ものすごくぶっちゃけていえば、ある点から出て同じ点に帰ってくる矢印みたいなもの。


で、同じ点に帰ってくる矢印なんだから、他の矢印と結合しても、元の矢印（がたどり着く点）は変わらないでしょう、というようなもの。

なんかこんなイメージ。これを、しりとりにあてはめると、こんな感じになる。

# 実際には、点や線はもっとたくさんある。
以下、圏の構成要素がしりとり（圏）において何に対応しているのか考える。

[ 対象 ]
対象は、ここで言えばひらがな1文字1文字のことにしてある。'あ' とか 'い' とかそういうやつ。なので、対象の集合は、ひらがな文字全体の集合になる。

[ 射 ]
射は、対象、つまりひらがな文字の間に引く矢印みたいなもので、今回は（ひらがな文字を並べた）文字列、ということにする。射の集合は、ひらがな文字列全体の集合。

[ 域と余域 ]
域は、文字列の先頭の文字とする。"きまいら"の域は、'き'。余域は、文字列の末尾の文字とする。"きまいら"の余域は、'ら'。

[ 結合 ]
結合は、射（つまり文字列）同士をくっつけることで、定義では「1つめの射の余域」と「2つめの射の域」が同じでなくては結合できない。これを今までの定義で言い換えると、「1つめの文字列の末尾の文字」と、「2つめの文字列の最初の文字」が同じでなければ結合できない、となる。つまり、しりとりできる文字列しか結合できない。今回の結合では、（しりとり可能な）文字列同士を結合し、重複した文字を（1つ）取り除くこと、とする。

"きまいら";"らいおん" => "きまいらいおん"

こんな感じ。なんかしりとりっぽくなってきた。

[ 恒等 ]
恒等は、射と結合しても変わらない射なので、これまで決めてきたことから考えると、長さ1の文字列になる。"あ"とか"い"とか。例としては…

"きまいら";"ら" => "きまいら"
"き";"きまいら" => "きまいら"

こんな感じ。少し前のざっくりした説明だと、同じ点に帰ってくる矢印みたいなもん、って書いてたんだけど、同じ点に帰ってくる射（文字列）でも、"きつつき" なんかは恒等にはならない。これは、他の射と結合した場合に違う射になってしまい、定義を満たさないから。たぶん。
# 射が同じってのは、定義しなくても大丈夫なんだろうか？文字列が同じって考えていいんだよなぁ…？

恒等自体は射（矢印）なので、"あ"とか"い"とかは、文字ではなく文字列なのに注意。

圏の法則
ここで、圏の法則をば。下つき文字の書き方がわからないので unit はプログラミング言語っぽく書いちまいます。今作ったしりとりの圏が、この法則を満たしていることを確認する。
  1. first(unit(x)) = last(unit(x)) = x (x∈H)
  2. first(s;t) = first(s), last(s;t) = last(t)
  3. (s;t);u = s;(t;u)
  4. x = first(s), y = last(s) なら、unit(x);s = s;unit(y) = s
[ 1つめ ]
  • 対象xの恒等（射）の域は、対象xに等しい。
  • 対象xの恒等（射）の余域は、対象xに等しい。
と言っている。しりとりで文字をあてはめてみると…
  • 文字: 'あ'
  • 対応する1文字の文字列: "あ"
  • 文字列 "あ" の域: 'あ'
というわけで、きちんと法則を満たしている。当たり前か。末尾も同じ。

[ 2つめ ]
  • 射sと射tを結合した射の域は、射sの域に等しい
  • 射sと射tを結合した射の余域は、射tの余域に等しい
これもしりとりで文字をあてはめてみると…
  • 射s: "きまいら"
  • 射t: "らいおん"
  • 射sとtの結合: "きまいらいおん"
  • 射sとtの結合の域: 'き'
  • 射sの域: 'き'
  • 射sとtの結合の余域: 'ん'
  • 射tの余域: 'ん'
というわけで、成り立っている。

[ 3つめ ]
  • 射sと射tを結合し、それに射uを結合したものは、射sに射tと射uの結合を結合したものと同じ
全然わかりやすくなってないな…。しりとり。
  • 射s: "でんき"
  • 射t: "きまいら"
  • 射u: "らいおん"
  • (s;t);u: ("でんき";"きまいら");"らいおん = "でんきまいら";"らいおん" = "でんきまいらいおん"
  • s(t;u): "でんき";("きまいら";"らいおん") = "でんき";"きまいらいおん" = "でんきまいらいおん"
成り立っている。なんかむなしくなってきた。

[ 4つめ ]
  • 射sの域がxであり、余域がyであるならば…
  • xの恒等（射）unit(x) と 射sの結合は、射sに等しい
  • 射sとyの恒等（射）unit(y) の結合は、射sに等しい
しりとりで。
  • 射s: "きまいら"
  • 射sの域 x: 'き'
  • 射sの余域 y: 'ら'
  • xの恒等 : "き"
  • yの恒等 : "ら"
  • xの恒等と射sの結合 : "き";"きまいら" = "きまいら"
  • 射sとyの恒等の結合 : "きまいら";"ら" = "きまいら"
OK。しりとり圏はちゃんとした圏。らしい。

unitで混乱
セミナーの最後に、unitに関して質問があり、微妙に混乱した。内容は…
構成要素には、unit が「対象」から「射」への写像（って言ってたかなぁ…）だとされているけど、絵で見ると恒等というのは「対象」から「対象」への射になっているので、別のものですよね？というもの。
これはたぶん…
  • unit: unit(x) で「対象xに関する恒等（射）」をあらわすもの、つまり対象から射への写像
  • unit(x) : ある対象xに関する恒等（射）、unitに具体的に対象が与えられたもの
というものがごっちゃになって混乱した、という話だと思った。あってるのだろうか。

Map Finite Ordinals
２つめの圏の例。こんな対象を考えてみる。
  • [0] = {}
  • [1] = {1}
  • [2] = {1, 2}
  • [3] = {1, 2, 3}
  • [4] = {1, 2, 3, 4}
  • …
射の具体的な内容は、要素間の対応関係（の組み合わせ）になる。ここで、対象間の矢印と要素間の矢印は違うものをあらわしていることに注意。

具体的に域が[2], 余域が[3]であるような射について考えてみると、射の数は9つになる。これは、実際に書いてみればわかる（が省略！）。[1]も加えて射の数を考えてみると…

こんな感じ。一般化すると、[n] から [m]への射の数は、mのn乗になる。

# この先はハイスピードでとばしまくり。

部分圏
MapFOの中でも、こんなものは部分圏になる。
  • InjFO 単射の圏
  • IsoFO 同型射の圏
  • IncFO 包含写像の圏
IncFOよくわからなかった。

関手
スライド0.2秒くらい、説明ゼロでした :-D
例を見ると、HSiri => KSiri が関手になっているので、圏を「対象」として見たとき、つまり圏の圏を考えたときの射が関手、ということなんだと思う。けど、具体的なイメージが…。

同じに見える色んな問題
スライドに書いてある色んな問題たちが同じようにみなせるらしい。が、どれとどれが同じなのか、はたまた全部同じなのか、よくわからなかった。

時間切れ、終了。なんか飲み会行ってテンションあがったので頑張って書いてみた。他の出席者の方のように、「あー、なるほど、あれがあれね！」とか「じゃああれはこうですか？」みたいなつっこんだ話は全然できず、道のりの長さが感じられたんだけど、それはそれでよかった。わかってること勉強しにいってもしょうがないしね。もう少し初級者向け（幻想？）の圏論読書会も立ち上がるかもしれない雰囲気。

コメント

コメントを投稿