Edited at

圏論以前の準備運動―圏と関手―


目次


関手の定義

まずは定義を見てみましょう。

具体例を考えたとき、それが関手の定義を満たしているのか、

確認したくなったらここに戻ってくれば良い。

確認を重ねるうちに定義には慣れてくるはずだ。


圏と関手

圏 $\boldsymbol{C}$ と圏 $\boldsymbol{D}$ の対応 $F \colon \boldsymbol{C} \longrightarrow \boldsymbol{D}$ すなわち

対象の対応 $F \colon \mathrm{Obj}(\boldsymbol{C}) \longrightarrow \mathrm{Obj}(\boldsymbol{D})$ と

射の対応 $F \colon \mathrm{Mor}(\boldsymbol{C}) \longrightarrow \mathrm{Mor}(\boldsymbol{D})$ を考える。

対象 $a\in\mathrm{Obj}(\boldsymbol{C})$ に対し $F\ a \in\mathrm{Obj}(\boldsymbol{D})$ である。

射 $f\in\mathrm{Mor}(\boldsymbol{C})$ に対し $F\ f \in\mathrm{Mor}(\boldsymbol{D})$ であり、

$\mathrm{dom}(F\ f) = F\ \mathrm{dom}(f)$ かつ $\mathrm{cod}(F\ f) = F\ \mathrm{cod}(f)$ である。

次の2つの条件を満たすとき、$F$ は関手である。


  1. (恒等射の保存)$F\ \mathrm{id}_{a} = \mathrm{id}_{F\ a}$ が成り立つ。

  2. (合成の保存)$F\ (f \ggg g) = F\ f \ggg F\ g$ が成り立つ。

定義は以上だが、少し言い換えてもう一度繰り返すと、

$a=\mathrm{dom}(f),\; b=\mathrm{cod}(f)$ として $f \colon a \longrightarrow b$ と書くことにすれば、

$f \colon a \longrightarrow b$ のとき $F\ f \colon F\ a \longrightarrow F\ b$ であり、

このときに恒等射と合成が保存されると関手だ。

対象 $a$ と射 $f$ と言う型が異なりうるものを同じ記号で

$F\ a$ や $F\ f$ と書くことに最初は戸惑ったような気がする。


合成関手

関手 $F \colon \boldsymbol{C} \longrightarrow \boldsymbol{D}$ と関手 $G \colon \boldsymbol{D} \longrightarrow \boldsymbol{E}$ の

合成関手 $F \cdot G \colon \boldsymbol{C} \longrightarrow \boldsymbol{E}$ を

対象の対応 $(F \cdot G)\ a = G\ (F\ a)$ と

射の対応 $(F \cdot G)\ f = G\ (F\ f)$ で定義する。


恒等関手

恒等関手 $\mathrm{id}_{\boldsymbol{C}} \colon \boldsymbol{C} \longrightarrow \boldsymbol{C}$ を

対象の対応 $\mathrm{id}_{\boldsymbol{C}}\ a = a$ と

射の対応 $\mathrm{id}_{\boldsymbol{C}}\ f = f$ で定義する。

対象と射それぞれの対応を定義せねばならずややこしく感じる。


圏の圏

関手を圏から圏への射とみなすこともできる。

つまり、圏が対象で関手が射な圏 $\mathbf{Cat}$ を構成可能である。

合成射を合成関手で恒等射を恒等関手で定義すれば

$\mathbf{Cat}$ は圏の定義を満たすことが以下のように確認できる。

合成関手や恒等関手の定義を眺めていると、

対象の対応と射の対応が同じ形式をしていることに気づく。

そこで $F\ a$ や $F\ f$ をまとめて $F\ -$ とあらわす。


  1. (結合律)

    射(すなわち関手) $F, G, H \in \mathrm{Mor}(\mathbf{Cat})$ に対して

    $(F \cdot (G \cdot H))\ - = (G \cdot H)\ (F\ -) = H\ (G\ (F\ -))$ と

    $((F \cdot G) \cdot H)\ - = H\ ((F \cdot G)\ -) = H\ (G\ (F\ -))$ から

    $F \cdot (G \cdot H) = (F \cdot G) \cdot H$ が成り立つ。


  2. (単位律)

    射(すなわち関手) $\mathrm{id}_{\boldsymbol{C}}, F, \mathrm{id}_{\boldsymbol{D}} \in \mathrm{Mor}(\mathbf{Cat})$ に対して

    $(\mathrm{id}_{\boldsymbol{C}} \cdot F)\ - = F\ (\mathrm{id}_{\boldsymbol{C}}\ -) = F\ -$ と

    $(F \cdot \mathrm{id}_{\boldsymbol{D}})\ - = \mathrm{id}_{\boldsymbol{D}}\ (F\ -) = F\ -$ から

    $\mathrm{id}_{\boldsymbol{C}} \cdot F = F \cdot \mathrm{id}_{\boldsymbol{D}} = F$ が成り立つ。


対象の対応と射の対応を考えねばならない関手であったが、

圏から圏への射だと思えば単純に感じられるような気もする。


関手の具体例

定義ばかりじゃ何も見えてこないので、

具体例を通して定義の理解を深める。

関手が定義できると何が嬉しいのかは置いておいて、

以下の例が関手なことを定義と照らし合わせ考えよう。


Maybe 関手

対象が型で射が関数な圏を $\mathbf{H}$ と呼ぶことにする。

対象(すなわち型) $\mathrm{Char}, \mathrm{Int}, \mathrm{Bool} \in \mathrm{Obj}(\mathbf{H})$ であり

射(すなわち関数) $\mathrm{id}_{\mathrm{Char}}, \mathrm{id}_{\mathrm{Int}}, \mathrm{id}_{\mathrm{Bool}}, \mathrm{f}, \mathrm{g}, \mathrm{h} \in \mathrm{Mor}(\mathbf{H})$ である。

この圏 $\mathbf{H}$ からの関手 $\mathrm{Maybe}$ を考える。


Maybe は Functor の instance に標準でなっている。


Maybe

data Maybe a = Nothing | Just a

instance Functor Maybe where
fmap _ Nothing = Nothing
fmap f (Just a) = Just (f a)


型構築子 Maybe の種を見て見ると

Maybe :: * -> *

また、高階関数 fmap の型を見てみると

fmap :: (a -> b) -> Maybe a -> Maybe b

ここで (->) は右結合であるから

fmap :: (a -> b) -> (Maybe a -> Maybe b)

対象(すなわち型) $a \in \mathrm{Obj}(\mathbf{H})$ と射(すなわち関数) $f \in \mathrm{Mor}(\mathbf{H})$ に対し

型構築子 Maybe で対象の対応 $\mathrm{Maybe}\ a =$ Maybe a

高階関数 fmap で射の対応 $\mathrm{Maybe}\ f =$ fmap f が定義される。


絵で描くとこんな感じになる。

データ構築子 Just ではなく型構築子 Maybe が

対象(すなわち型)の対応をあらわしていることに注意が必要だろう。


例によって、丸で囲まれた対象内部の構造を潰して点 $\bullet$ とみなすと

こう見ると型構築子 Maybe が対象の対応をあらわすのは明らかだ。


さらに、四角で囲まれた圏内部の構造を潰して点 $\scriptscriptstyle\blacksquare$ とみなすと

圏の圏になる。


List 関手

Maybe 関手の場合と同様に、

$\mathbf{H}$ からの関手 $\mathrm{List}$ を考える。


List は Functor の instance に標準でなっている。


List

data [] a = [] | a : [a]

instance Functor [] where
fmap _ [] = []
fmap f (x:xs) = f x : fmap f xs


Maybe 関手の場合と同様に、

対象(すなわち型) $a \in \mathrm{Obj}(\mathbf{H})$ と射(すなわち関数) $f \in \mathrm{Mor}(\mathbf{H})$ に対し

型構築子 [ ] で対象の対応 $\mathrm{List}\ a =$ [a]

高階関数 fmap で射の対応 $\mathrm{List}\ f =$ fmap f が定義される。


絵で描くとこんな感じになる。

型構築子 [ ] が対象(すなわち型)の対応をあらわしている。


例によって、丸で囲まれた対象内部の構造を潰して点 $\bullet$ とみなすと

そろそろ対象内部の構造に興味を持たなくても大丈夫な気がする。


さらに、四角で囲まれた圏内部の構造を潰して点 $\scriptscriptstyle\blacksquare$ とみなすと

圏の圏になる。


自己関手

Haskell の全ての型を対象、Haskell の全ての関数を射

とした圏 $\mathbf{Hask}$ を考えれば、Maybe 関手List 関手

圏 $\mathbf{Hask}$ から 圏 $\mathbf{Hask}$ への関手と言うことができる。

圏 $\mathbf{H}$ は圏 $\mathbf{Hask}$ の部分圏すなわち $\mathbf{H} \subset \mathbf{Hask}$ である。

自分自身に戻ってくるような関手を自己関手と言う。

対象1つで射が整数値の圏に似た絵でモノイドと関係しそう。

自己関手、、、、、、モノイド、、どこかで見たような1


Hom 関手

関手の定義をある程度は理解したところで、

もう少し難しげな例として Hom 関手を考えてみたい。

米田の補題2と関係があるらしいのできっと興味深い。


Hom 集合

圏 $\boldsymbol{C}$ の対象 $a, b \in \mathrm{Obj}(\boldsymbol{C})$ に対して

始域 $a$ で終域 $b$ な射の集合を $\mathrm{Hom}_{\boldsymbol{C}}(a, b)$ と呼ぶ。

射 $f\in\mathrm{Mor}(\boldsymbol{C})$ のうち $f \colon a \longrightarrow b$ な射の集合だ。

集合の内包的記法を用いて次のように書ける。

$\mathrm{Hom}_{\boldsymbol{C}}(a, b) = \{f \in \mathrm{Mor}(\boldsymbol{C}) \mid \mathrm{dom}(f) = a \land \mathrm{cod}(f) = b\}$

Hom 集合は部分集合すなわち $\mathrm{Hom}_{\boldsymbol{C}}(a, b) \subset \mathrm{Mor}(\boldsymbol{C})$ である。


集合の圏

集合を対象、写像を射とした圏を $\mathbf{Set}$ とする。

Hom 集合も対象となり、$\mathrm{Hom}_{\boldsymbol{C}}(a, b) \in \mathrm{Obj}(\mathbf{Set})$ である。

対象が型で射が関数な圏で見たように、

型を値の集合、関数を写像だと考えれば

集合の圏を何となくイメージできると思う。

集合の要素ではなくて、集合が対象なので注意。

少なくとも自分は最初これが分からなかった。

集合の要素を対象にし、恒等射のみを考えると、

これも圏になるのでややこしく感じたのだと思う。


反変関手

圏 $\boldsymbol{C}$ と圏 $\mathbf{Set}$ の対応 $F \colon \boldsymbol{C} \longrightarrow \mathbf{Set}$ すなわち

対象の対応 $F \colon \mathrm{Obj}(\boldsymbol{C}) \longrightarrow \mathrm{Obj}(\mathbf{Set})$ と

射の対応 $F \colon \mathrm{Mor}(\boldsymbol{C}) \longrightarrow \mathrm{Mor}(\mathbf{Set})$ を考えてみよう。

Hom 集合間の写像 $\varphi_{f} \colon \mathrm{Hom}_{\boldsymbol{C}}(a, b) \longrightarrow \mathrm{Hom}_{\boldsymbol{C}}(a', b)$ を

$\varphi_{f} \colon h \longmapsto f \ggg h$ で定義すると、これは射 $\varphi_{f} \in \mathrm{Mor}(\mathbf{Set})$ である。

対象の対応 $F\ a = \mathrm{Hom}_{\boldsymbol{C}}(a, b)$ と

射の対応 $F\ f = \varphi_{f}$ をそれぞれ定義する。

($F\ f \colon h \longmapsto f \ggg h$ とも書ける。)

この関手 $F$ を Hom 関手と呼び $\mathrm{Hom}_{\boldsymbol{C}}(-, b)$ と書く。

記号 $-$ は対象か射のいずれかをあらわすとして、

高階関数 $\mathrm{Hom}_{\boldsymbol{C}} \colon \mathrm{Obj}(\boldsymbol{C}) \longrightarrow \mathrm{Obj}(\boldsymbol{C}) \longrightarrow \mathrm{Obj}(\mathbf{Set})$

高階関数 $\mathrm{Hom}_{\boldsymbol{C}} \colon \mathrm{Mor}(\boldsymbol{C}) \longrightarrow \mathrm{Obj}(\boldsymbol{C}) \longrightarrow \mathrm{Mor}(\mathbf{Set})$

に部分適用を行う感覚で良いのではないだろうか。

同様に、高階関数 $(\ggg) \colon \mathrm{Mor}(\boldsymbol{C}) \longrightarrow \mathrm{Mor}(\boldsymbol{C}) \longrightarrow \mathrm{Mor}(\boldsymbol{C})$

に部分適用を行う感覚で $\varphi_{f} = f\ggg-$ とも書く。

Hom 関手 $\mathrm{Hom}_{\boldsymbol{C}}(-, b)$ は

$a\in\mathrm{Obj}(\boldsymbol{C})$ を $\mathrm{Hom}_{\boldsymbol{C}}(a, b)\in\mathrm{Obj}(\mathbf{Set})$ に対応させ

$f\in\mathrm{Mor}(\boldsymbol{C})$ を $f\ggg- = \mathrm{Hom}_{\boldsymbol{C}}(f, b)\in\mathrm{Mor}(\mathbf{Set})$ に対応させる。


絵で描くとこんな感じになる。

圏 $\boldsymbol{C}$ と圏 $\mathbf{Set}$ で射が逆の向きになっている。

このような関手を反変関手というらしい。


共変関手

反変関手の場合と同様に、

Hom 関手 $\mathrm{Hom}_{\boldsymbol{C}}(a, -)$ は

$b\in\mathrm{Obj}(\boldsymbol{C})$ を $\mathrm{Hom}_{\boldsymbol{C}}(a, b)\in\mathrm{Obj}(\mathbf{Set})$ に対応させ

$g\in\mathrm{Mor}(\boldsymbol{C})$ を $- \ggg g = \mathrm{Hom}_{\boldsymbol{C}}(a, g)\in\mathrm{Mor}(\mathbf{Set})$ に対応させる。


関数が Functor の instance になるという理解で良いはず。


Hom

import Control.Category ((>>>))

data Hom a b = Hom (a -> b)

instance Functor (Hom a) where
fmap g (Hom h) = Hom (h >>> g)



絵で描くとこんな感じになる。

圏 $\boldsymbol{C}$ と圏 $\mathbf{Set}$ で射が同じ向きになっている。

このような関手を共変関手というらしい。


反対圏

圏 $\boldsymbol{C}$ の反対圏 $\boldsymbol{C}^{\mathrm{op}}$ を図のように定める。

圏 $\boldsymbol{C}^{\mathrm{op}}$ から圏 $\mathbf{Set}$ への関手 $\mathrm{Hom}_{\boldsymbol{C}}(-, b) \colon \boldsymbol{C}^{\mathrm{op}} \longrightarrow\mathbf{Set}$

を考えることで反変関手を共変関手とみなすことができる。

確かに射が同じ向きになるのは分かるけど、

対象や射に付いてる $\scriptstyle \mathrm{op}$ を気にせずにすむ理屈

が良く分かっていないのでいつか理解したい3


双関手

圏の圏では圏が対象となるため、

圏の直積と余直積を考えることができるだろう。

圏 $\boldsymbol{C}$ と圏 $\boldsymbol{D}$ の直積 $\boldsymbol{C}\times\boldsymbol{D}$ は

対象 $(c,d)\in\mathrm{Obj}(\boldsymbol{C})\times\mathrm{Obj}(\boldsymbol{D})=\mathrm{Obj}(\boldsymbol{C}\times\boldsymbol{D})$ と

射 $(f,g)\in\mathrm{Hom}_{\boldsymbol{C}}(c,c')\times\mathrm{Hom}_{\boldsymbol{D}}(d,d')=\mathrm{Hom}_{\boldsymbol{C}\times\boldsymbol{D}}((c,d), (c',d'))$

で定められる。$\mathrm{Hom}_{\boldsymbol{C}\times\boldsymbol{D}}((c,d), (c',d')) \subset \mathrm{Mor}(\boldsymbol{C}\times\boldsymbol{D})$ である。


絵で描くとこんな感じになる。

射の合成は次のように成分ごとに射を合成する。

$(f,\mathrm{id}_{b}) \ggg (\mathrm{id}_{a},g) = (f \ggg\mathrm{id}_{a},\mathrm{id}_{b} \ggg g) = (f,g)$


圏 $\boldsymbol{C}\times\boldsymbol{C}$ と圏 $\mathbf{Set}$ の対応 $F \colon \boldsymbol{C}\times\boldsymbol{C} \longrightarrow \mathbf{Set}$ すなわち

対象の対応 $F \colon \mathrm{Obj}(\boldsymbol{C}\times\boldsymbol{C}) \longrightarrow \mathrm{Obj}(\mathbf{Set})$ と

射の対応 $F \colon \mathrm{Mor}(\boldsymbol{C}\times\boldsymbol{C}) \longrightarrow \mathrm{Mor}(\mathbf{Set})$ を考えてみよう。

$\mathrm{Hom}_{\boldsymbol{C}}(-, b)$ と $\mathrm{Hom}_{\boldsymbol{C}}(a, -)$ とを合わせた感じで、

$(a,b)\in\mathrm{Obj}(\boldsymbol{C}\times\boldsymbol{C})$ を $\mathrm{Hom}_{\boldsymbol{C}}(a, b)\in\mathrm{Obj}(\mathbf{Set})$ に対応させ

$(f,g)\in\mathrm{Mor}(\boldsymbol{C}\times\boldsymbol{C})$ を $f \ggg - \ggg g = \mathrm{Hom}_{\boldsymbol{C}}(f, g) \in\mathrm{Mor}(\mathbf{Set})$

に対応させる関手 $\mathrm{Hom}_{\boldsymbol{C}}(-, -)$ を定義する。


絵で描くとこんな感じになる。

圏 $\boldsymbol{C}\times\boldsymbol{C}$ と圏 $\mathbf{Set}$ で縦方向の射が逆の向きになっている。


圏 $\boldsymbol{C}^{\mathrm{op}}\times\boldsymbol{C}$ から圏 $\mathbf{Set}$ への関手 $\mathrm{Hom}_{\boldsymbol{C}}(-,-) \colon \boldsymbol{C}^{\mathrm{op}}\times\boldsymbol{C} \longrightarrow\mathbf{Set}$

を考えることで双関手4とみなすことができる。

圏 $\boldsymbol{C}^{\mathrm{op}}\times\boldsymbol{C}$ と圏 $\mathbf{Set}$ で射が同じ向きになっている。

圏 $\boldsymbol{C}$ の対象 $a\in\mathrm{Mor}(\boldsymbol{C})$ ごとに存在する

関手 $\mathrm{Hom}_{\boldsymbol{C}}(a, -)$ による対応が色点線で囲まれている。

これらの関手と関手との間にも何か対応がありそうだ。


まとめ

Functor は箱5のイメージが強い場合には

fmap の引数の順序に悩んでしまうけれども、

関手と思えばこの順序が気持ちよく感じる。

Functor は圏 $\mathbf{Hask}$ から圏 $\mathbf{Hask}$ への関手6

つまり射が関数な場合にしか使えないので、

Category から Category への関手を定義7して

instance を作ってみると楽しいかもしれない。