Javaプログラマーのための圏論（３．大小様々な圏）

大小様々な圏

対象がない圏

　最も自明な圏は一つの対象も持たない圏で、射も持たない圏である。状況によって重要になるかもしれない。例えば全ての圏の圏を考えるとき。空集合に意味がある状況であれば、空な圏も意味があるだろう。

単純グラフ

　対象を矢印で結ぶことで圏を作ることが出来る。任意の有効グラフからスタートして、単純に矢印を次々と追加することで圏にすることができる。最初に恒等射を各ノードに追加する。次に、ある矢印の終点と別の矢印の始点が一致するような２つの矢印に対して、合成になるように新しい矢印を追加する。新しい矢印を追加する度に、別の矢印（恒等射を除く）との合成を考えなればならない。通常無限にたくさんの矢印まで続くが、仕方がない。
　圏を作るこの過程に別の見方をすると、グラフの各ノードは対象であり、合成可能なグラフの辺のすべての可能なチェーンは射として見ることができる（恒等射は長さが零のチェーンの特殊なケースとみることもできる）。
　このような圏は与えられたグラフによって生成された自由圏と呼ばれる。

順序

　今度は全く別の例を取り上げよう。対象の関係が射である圏である。その関係は以下である。各対象は自分自身以下である。$a \leqq b$ かつ $b \leqq c$ ならば、 $a \leqq c$ となり、合成が成り立つ。結合律も成り立つ。このような関係を持つ集合を前順序と呼び、前順序は圏である。
　$a \leqq b$ かつ $b \leqq a$ ならば、 $a = b$ が成り立つような、より強い関係を与えることもできる。このような関係を持つ集合は半順序と呼ばれる。
　任意の対象$a, b$に対して、$a \leqq b$または$b \leqq a$のいずれかが成り立つ条件を仮定すると、全順序を与えることができる。
　前順序は圏であり、対象$a$から対象$b$へのへの射を高々一つ持つ。このような圏を「薄い」という。前順序は薄い圏である。
　圏$C$の対象$a$から対象$b$への射の集合は射集合(hom-set)と呼ばれ、$C(a,b)$(または、$Hom_C(a,b)$)と記す。前順序の各射集合は空またはシングルトンである。それは射集合$C(a,a)$、即ち$a$から$a$への射の集合は、シングルトンであり、前順序の恒等射のみ含む。前順序は循環を含む場合もあるが、半順序は循環はありえない。

集合としてのモノイド

　モノイドは驚くほど単純だが、強力な概念である。基本的な算術の背景にある概念である。加算と乗算はモノイドを形成する。モノイドはプログラミングにおいてユビキタスである。文字列、リスト、畳み込み可能なデータ構造、並列プログラミングでのfuture、関数型リアクティブプログラミングでのeventなどである。
　モノイドは二項演算を持つ集合として定義される。この演算は、結合律が成り立ち、単位元と言う特殊な要素を持つ。
　例えば、零を持つ自然数は加算の下でモノイドを形成する。結合律は次のような意味になる。
$$ (a+b)+c=a+(b+c) $$ （数字を加算する際に括弧を外してもよいと言い換えることもできる） 　単位元（中立元とも言う）は零である。なぜなら、 $$ 0+a=a $$ かつ $$ a+0=a $$ だからである。 2番目の式は加算が交換可能（$a+b=b+a$）なため、冗長であるが、交換可能性はモノイドの一部ではない。例えば、文字列の連結は交換可能ではないが、モノイドを形成する。文字列連結に対する単位元は空文字であり、文字列のどちら側から連結しても変わらない。
　Java（Java8以降）でモノイドを定義することができる。単位元をmempty、二項演算をmappendを持つ。

class Monoid<M> {
  M mempty;
  Function<M,Function<M,M>> mappend;
  Monoid(M mempty, Function<M,Function<M,M>> mappend) {
    this.mempty = mempty;
    this.mappend = mappend;
  }
}

２つの引数の関数に対して、Function<M,Function<M,M>>と言うシグネチャは最初は奇異に見えるかもしれないが、カリー化について触れた後では納得してもらえるだろう。
　memptyとmappendの実装を与えることでStringについてモノイドを宣言することができる。

var m = new Monoid<String>("", s1 -> s2 -> s1 + s2);

s1 -> s2 -> s1 + s2の複数の矢印を持つシグネチャは2通りに解釈できる。一つ目は複数の引数を持ち、最も右の値を返す関数、二つ目は最初の引数（最も左の引数）に対して関数を返すような関数の２通りである。後者の解釈は括弧を追加することによって強調することができる。s1 -> (s2 -> s1 + s2))(矢印は右結合なので、括弧は冗長である。)
　(Java7以前の)Javaでモノイドを定義すると次のように定義することもできる。

interface Monoid<M> {
  M mempty();
  M mappend(M m1, M m2);
}

Monoidのインスタンスは文字列で定義すれば以下のようになる。

class MonoidString implements Monoid<String> {
  String mempty() {
    return "";
  }

  String mappend(String s1, String s2) {
    return s1 + s2;
  }
}

圏としてのモノイド

　集合の要素に対するモノイドの定義は圏と似ている。しかし、圏論では、集合やその要素から離れ、その代わり対象と射について議論する。二項演算の適用を集合のものを移動することとして少し視点を変えて考える。
　例えば、自然数に5を加算する操作がある。これは0を5に、1を6に、2を7に写す。自然数の集合上に定義された関数である。任意の数mに対してnを加算する関数が存在する。nの加算器である。
　加算器の合成はどうなるのか？5を加算する関数と7を加算する関数の合成は12を加算する関数である。よって、加算器の合成は加算のルールと同等である。関数の合成は加算で置き換えることが出来る。
　単位元、零の加算器もまた存在する。零を加算しても動かない、だから自然数の集合においてそれは恒等射である。
　整数から加算器へ写すことは、mappendをm->(m->m)とみなすことに対応している。mappendは、モノイドの要素をその集合に作用する関数へ写しているとみなせる。
　一度自然数の集合から離れて、単一の対象、すなわち、加算器の射の束の塊として考える。モノイドは単一の対象の圏である。モノイドは合成律に従う射の集合を持つ単一の対象の圏とみなすことが出来る。文字列連結は右連結、左連結が選択できる。２つのモデルの合成テーブルはお互い対称の関係にある。"foo"の後に"bar"を連結することと、"foo"の前に"bar"を連結することが対応する。
　圏論的モノイド、単一対象の圏は二項演算を持つ唯一の集合として定義できる。一つの対象の圏からある集合を取り出すことができることがわかる。この集合は射、先の例では加算器の集合である。言い換えると、圏$ M $の単一対象$ m $の射集合$M(m,m)$ である。この集合での二項演算を定義することができ、２つの集合要素のモノイド積が要素に対応する射の合成に対応する。$M(m,m)$ の２つの要素$f$と$g$に対して、これらの積は合成$f \circ g$に対応する。合成は必ず存在する。これらの射の始域と終域は同じ対象だからである。また、結合律も成り立つ。恒等射はこの積の単位元である。故に圏論的モノイドから集合的モノイドへ元に戻すことができる。実際、これらは一つであり、同じものである。少しだけ数学の話を掘り下げると、射は集合を形成するとは限らない。圏の世界は集合より広いものを扱う。任意の二つ対象間の射が集合を形成するような圏は局所的に小さい（locally small）と呼ばれる。通常はこのような微妙なものは無視すればよい。
　圏論での興味深い現象の多くは射集合の要素が合成律を満たす射であり、且つ集合の点のどちらでもあると言う事実に依っている。ここでは、$ M $の射の合成は$M(m,m)$ のモノイド積に変換される。