１．集合の圏
ここまで集合に関する圏について論じてきたが、それらをいったん整理してみる。
圏の定義は次のようになっていた。
(1) 対象
圏は対象を有する。対象は、通常は大文字を用いて、\(A,B,C,..\)と表す。
(2) 射
圏は対象（複数の場合も可）から対象（こちらも複数の場合可）へ移す射を有する。射は、通常小文字を用いて、\(f,g,h,..\)と表す。
(3) ドメインとコドメイン
射の出発（入力）側の対象をドメインといい、到着（出力）側の対象をコドメインという。
(4) 恒等射
射は恒等射\(id\)を有する。恒等射は自分から自分へ移す射である。
(5) 合成
任意の二つの射に対して、合成\(\circ\)が可能である。二つの射を\(f,g\)とした時、その合成は\(g \circ f\)と表す。この時、\(f\)のコドメインと\(g\)のドメインは同一である。
二つの条件は次の通りである。
(1) 恒等射では単位律が成り立つ。即ち、恒等射はある射のドメインで適応したとしても、その射のコドメインで適応したとしても、変化を与えない。\(f: A \rightarrow B\)を任意の射とし、対象\(A\)での恒等射を\(id_A\)とし、対象\(B\)での恒等射を\(id_B\)としたとき、\(f \circ id_A = f = id_B \circ f\)である。
(2) 射では結合律が成り立つ。即ち、合成できる三つの射\(f,g,h\)において、\((h \circ g) \circ f = h \circ (g \circ f)\)である。
圏においては、対象と射が最も重要である。これまでに説明してきたのは、集合の集まりだけで構成されている圏（単純集合の圏）と、自分自身への写像endomapを有する集合の集まりで構成されている圏（endomap集合の圏）と、グラフで構成されている圏（グラフの圏）である。これらの圏に対して、対象と射がどのようになっているかを表に表すと以下のようになる（あまり説明はしていないが位相空間で構成された圏（位相空間の圏）についても参考までに並べた）。
| 圏 | 対象 | 射 |
|---|---|---|
| 単純集合 | \(A_1,A_2, A_3,...\),\(B_1,B_2, B_3,..\) | \(f:A_{1_i} \rightarrow B_{1_i},A_{2_i} \rightarrow B_{2_i}\),... |
| endomap集合 | \(A_1,A_2, A_3,...\),\(B_1,B_2, B_3,..\) | \(f:A_{1_i} \rightarrow B_{1_i},A_{2_i} \rightarrow B_{2_i}\),..., \(g_i:A_i \rightarrow A_i\), \(h_i:B_i \rightarrow B_i\), |
| グラフ | \(X\),\(P\),\(Y\),\(Q\) | \(f_A:X \rightarrow Y\),\(f_N:P \rightarrow Q\), \(s:X \rightarrow P\), \(t:X \rightarrow P\), \(s':Y \rightarrow Q\), \(t':P \rightarrow Q\) |
| 位相空間 | 開集合\(A\),\(B\) | 連続写像\(f:A \rightarrow B\) |
２．集合に関係する圏をHaskellの型クラスで実現
集合に関係する圏をHaskellの型クラスで実現で実現することを考える。ここで扱うのは単純集合圏、endomap集合圏、グラフ圏である。単純集合圏は構造を持たない圏であるが、これに構造を持たせたのが、endomap集合圏とグラフ圏である。従って、endomap集合圏あるいはグラフ圏を単純化したものが単純集合圏である。このため、単純集合圏は概念的にendomap集合圏とグラフ圏を含んでいると考えてよい。
そこで、Haskellで実現するときは、単純集合圏を型クラスとして用意し、endomap集合圏とグラフ圏はそれぞれ単純集合圏のサブクラスと考える。
また、集合は都合のよいことに型データとして用意されている。即ち、ライブラリData.Setをインポートすれば、集合Setが使えるようになる。
２．１ 単純集合圏
最初に単純な圏SimpleCategoryというクラスを次のように用意した。
import Data.Set class SimpleCategory t where morphism :: (a -> b) -> t a -> t b identity :: t a -> t a
上記のプログラムで、tのところでデータ型を指定する。たとえば、集合に関する圏としたければ、Setとする。次に、単純な圏では、射\(f\)を用意しなければならないが、それを与えるのが、morphismである。この関数は、射\(f\)とドメインとなる集合を入力とする。
また、圏では必ず恒等射を備えておく必要があるが、これを与えるのが、identityである。
この型クラスをインスタンス化して単純集合圏を作成すると次のようになる。
instance SimpleCategory Set where morphism = mapMonotonic identity = mapMonotonic id
上記のプログラムで、データ型はSetとした。また、morphismはデータ型Setの中で用意されている関数mapMonotonicとした。mapMonotonicは入力された集合の各要素に対して、与えられた関数を施し、その結果を集合として出力する。mapMonotonicの型シグネチャは次のようになっている。
*Sets> :t mapMonotonic mapMonotonic :: (a -> b) -> Set a -> Set b
それでは、型クラスSimpleCategoryのインスタンスとして定義された単純集合圏を利用した例を示す。
最初の例は下図に示すものである。
これを実現すると以下のようになる。
-- Example 1 setA = fromList ['a'..'c'] setB = fromList ['u'..'z'] f x | x == 'a' = 'u' | x == 'b' = 'v' | x == 'c' = 'v' | otherwise = error "not an elment of the set." test1 = identity setA test2 = morphism f setA test3 = identity setB
集合\(A,B\)はsetA,setBで実装してある。これらを作成するとき、fromListを用いたが、fromListはSetに用意された関数で、これはリストから集合を作成する。
実行結果は以下のとおりである。test1とtest3は恒等射であり、test2は射\(f\)により\(A\)から\(B\)に写像したものである。
*Sets> test1 fromList "abc" *Sets> test2 fromList "uvv" *Sets> test3 fromList "uvwxyz"
２番目の例は下図に示すものである。
これを実現すると以下のようになる。
-- Example 2 setA' = fromList [1..10] setB' = fromList [1..100] f' x = x * x test1' = identity setA' test2' = morphism f' setA' test3' = identity setB'
集合\(A,B\)はsetA',setB'で実装してある。
実行結果は以下のとおりである。test1'とtest3'は恒等射であり、test2'は射\(f\)により\(A\)から\(B\)に写像したものである。
*Sets> test1' fromList [1,2,3,4,5,6,7,8,9,10] *Sets> test2' fromList [1,4,9,16,25,36,49,64,81,100] *Sets> test3' fromList [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99,100]
３番目の例は前回の記事でも用いた名前と住所の関係である。これは下図のようになっている。
これを実現すると以下のようになる。
-- Example 3 name = fromList ["John","Betty","Tom","Mike","Peter","Jacky","Rose"] address = fromList ["Berkeley","Stanford","San Jose","Los Angeles"] residence x | x == "John" = "Berkeley" | x == "Betty" = "Berkeley" | x == "Tom" = "Stanford" | x == "Mike" = "San Jose" | x == "Peter" = "Los Angeles" | x == "Jacky" = "Los Angele" | x == "Rose" = "Los Angele" | otherwise = error "not a member" test1'' = identity name test2'' = morphism residence name test3'' = identity address
実行結果は以下のとおりである。test1''とtest3''は恒等射であり、test2''は射\(residence\)により\(name\)から\(address\)に写像したものである。
*Sets> test1'' fromList ["Betty","Jacky","John","Mike","Peter","Rose","Tom"] *Sets> test2'' fromList ["Berkeley","Los Angele","Berkeley","San Jose","Los Angeles","Los Angele","Stanford"] *Sets> test3'' fromList ["Berkeley","Los Angeles","San Jose","Stanford"]
２．２ endomap集合圏
endomap集合圏を単純集合圏のサブクラスとして次のように実装する。
class (SimpleCategory t) => (EndomapCategory t) where endomap :: (a -> a) -> t a -> t a
追加したのは、集合内の写像であるendomapの型シグネチャだけである。このサブクラスからendomap集合圏は次のように実現される。
instance EndomapCategory Set where endomap = mapMonotonic
ここでは、関数endomapを実現するが、これには先に示したmapMonotonicを用いる。
それでは、このインスタンスを用いて、以下の例を考える。
なお、endomap集合圏では、\(g \circ \alpha = \beta \circ g\)が成り立っていることが必要である。
プログラムを書くと、次のようになる。
-- Example 4 setC = fromList [1..5] setD = fromList ['a'..'d'] alpha x | x == 1 = 2 | x == 2 = 3 | x == 3 = 1 | x == 4 = 5 | x == 5 = 4 | otherwise = error "not an elment of the set." beta x | x == 'a' = 'b' | x == 'b' = 'c' | x == 'c' = 'a' | x == 'd' = 'd' | otherwise = error "not an elment of the set." g x | x == 1 = 'c' | x == 2 = 'a' | x == 3 = 'b' | x == 4 = 'd' | x == 5 = 'd' | otherwise = error "not an elment of the set." testA = endomap alpha setC testB = morphism g $ endomap alpha setC testC = endomap beta $ morphism g setC testD = endomap beta setD
集合\(C,D\)はsetC,setDで実装してある。
実行結果は以下のとおりである。testAとtestDは恒等射であり、testBは射\(\alpha\)の後に射\(g\)を施した。また、testCは射\(g\)の後に射\(\\beta\)を施した。両者が等しいことに注意してほしい。
*Sets> testA fromList [2,3,1,5,4] *Sets> testB fromList "abcdd" *Sets> testC fromList "abcdd" *Sets> testD fromList "bcad"
２．３ グラフ圏
グラフ圏を単純集合圏のサブクラスとして次のように実装する。
class (SimpleCategory t) => (GraphCategory t) where source :: (a -> b) -> t a -> t b target :: (a -> b) -> t a -> t b
追加したのは、矢印の出発点を示す射souceと到着点を示すtargetの型シグネチャである。このサブクラスからグラフ圏は次のように実現できる。
instance GraphCategory Set where source = mapMonotonic target = mapMonotonic
関数souceとtargetを実装したが、ここでは先に示したmapMonotonicを用いた。
それでは、このインスタンスを用いて、以下の例を考える。
なお、グラフ圏では、\(h_D \circ s = s' \circ h_A\)と\(h_D \circ t = t' \circ h_A\)が成り立っていることが必要である（詳しくは前の記事を参照）。
それでは、プログラムを書いてみると、次のようになる。
-- Example 5 setX = fromList ['a'..'d'] setP = fromList ['w'..'z'] setY = fromList ['m'..'n'] setQ = fromList ['p'..'q'] ha x | x == 'a' = 'm' | x == 'b' = 'n' | x == 'c' = 'n' | x == 'd' = 'm' | otherwise = error "not an elment of the set." hd x | x == 'w' = 'q' | x == 'x' = 'p' | x == 'y' = 'q' | x == 'z' = 'q' | otherwise = error "not an elment of the set." s x | x == 'a' = 'x' | x == 'b' = 'y' | x == 'c' = 'z' | x == 'd' = 'x' | otherwise = error "not an elment of the set." t x | x == 'a' = 'y' | x == 'b' = 'z' | x == 'c' = 'z' | x == 'd' = 'w' | otherwise = error "not an elment of the set." s' x | x == 'm' = 'p' | x == 'n' = 'q' | otherwise = error "not an elment of the set." t' x | x == 'm' = 'q' | x == 'n' = 'q' | otherwise = error "not an elment of the set." testP = identity setX testQ = identity setP testP' = identity setY testQ' = identity setQ testR = source s setX testS = target t setX testR' = source s' setY testS' = target t' setY testT = source s' $ morphism ha setX testU = target t' $ morphism ha setX testT' = morphism hd $ source s setX testU' = morphism hd $ target t setX
実行結果は以下のとおりである。
*Sets> testB fromList "abcdd" *Sets> testC fromList "abcdd" *Sets> testD fromList "bcad" *Sets> testP fromList "abcd" *Sets> testQ fromList "wxyz" *Sets> testP' fromList "mn" *Sets> testQ' fromList "pq" *Sets> testR fromList "xyzx" *Sets> testS fromList "yzzw" *Sets> testR' fromList "pq" *Sets> testS' fromList "qq" *Sets> testT fromList "pqqp" *Sets> testU fromList "qqqq" *Sets> testT' fromList "pqqp" *Sets> testU' fromList "qqqq"
\(h_D \circ s = s' \circ h_A\)と\(h_D \circ t = t' \circ h_A\)を検証している部分はtestT,testT'（ドメイン側）とtestU,testU'（コドメイン側）である。
