読者です 読者をやめる 読者になる 読者になる

bitterharvest’s diary

A Bitter Harvestは小説の題名。作者は豪州のPeter Yeldham。苦闘の末に勝ちえた偏見からの解放は命との引換になったという悲しい物語

Haskellで学ぶ圏論・ウォームアップ編 集合の圏のまとめ

1.集合の圏

ここまで集合に関する圏について論じてきたが、それらをいったん整理してみる。

圏の定義は次のようになっていた。

(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\)

2.集合に関係する圏をHaskellの型クラスで実現

集合に関係する圏をHaskellの型クラスで実現で実現することを考える。ここで扱うのは単純集合圏、endomap集合圏、グラフ圏である。単純集合圏は構造を持たない圏であるが、これに構造を持たせたのが、endomap集合圏とグラフ圏である。従って、endomap集合圏あるいはグラフ圏を単純化したものが単純集合圏である。このため、単純集合圏は概念的にendomap集合圏とグラフ圏を含んでいると考えてよい。

そこで、Haskellで実現するときは、単純集合圏を型クラスとして用意し、endomap集合圏とグラフ圏はそれぞれ単純集合圏のサブクラスと考える。

また、集合は都合のよいことに型データとして用意されている。即ち、ライブラリData.Setをインポートすれば、集合Setが使えるようになる。

2.1 単純集合圏

最初に単純な圏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のインスタンスとして定義された単純集合圏を利用した例を示す。

最初の例は下図に示すものである。
f:id:bitterharvest:20150303103333p:plain
これを実現すると以下のようになる。

-- 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"

2番目の例は下図に示すものである。
f:id:bitterharvest:20150303104323p:plain
これを実現すると以下のようになる。

-- 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]

3番目の例は前回の記事でも用いた名前と住所の関係である。これは下図のようになっている。
f:id:bitterharvest:20150303105347p:plain
これを実現すると以下のようになる。

-- 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"]

2.2 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を用いる。

それでは、このインスタンスを用いて、以下の例を考える。
f:id:bitterharvest:20150303112932p:plain
なお、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"

2.3 グラフ圏

グラフ圏を単純集合圏のサブクラスとして次のように実装する。

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を用いた。

それでは、このインスタンスを用いて、以下の例を考える。
f:id:bitterharvest:20150303115126p:plain

なお、グラフ圏では、\(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'(ターゲット側)である。

2.4 位相空間

位相空間についても、次の論文に示されるような方法で、データ型を用意することが可能である。このデータ型を用いることで、集合と同じように扱うことが可能となる。