bitterharvest’s diary

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

Haskellで学ぶ圏論・ウォームアップ編 最大公約数の構造

1.識別情報

携帯電話を購入するときや、旅行を申し込みに行くと、契約書には名前の他に、生年月日や性別を書かされる。これは、個人を特定するための情報だが、その構造を数学的に記述すると次のようになる。
f:id:bitterharvest:20150202114022p:plain


図では個人識別情報を\(identity\)と表している。これは住民基本台帳に登録されている番号と考えてもよい。生年月日を\(born\)で、性別を\(sex\)と表している。契約書に書いた内容は、生年月日と性別であるが、図ではこれらの積として\(born \times sex \)で記した( \( \times \)という記号は掛け算を表す演算記号である。積とも呼ばれるが、論理の世界に移すと積という用語は論理積として使われる。論理積が持つ意味は、「その二つの引数が両方とも成り立っているもの」という意味を持つ。ここで用いている\( \times \)もそのような意味で用いている。即ち、\(born\)と \( sex \)の両方がともに成り立っていることを表している)。

図に示したように、関数\(u,p_1,p_2,f_1,f_2\)を次のように定める。
\begin{eqnarray*}
u &:& identity \rightarrow born \times sex \\
p_1 &:& born \times sex \rightarrow born \\
p_2 &:& born \times sex \rightarrow sex \\
f_1 &:& identity \rightarrow born \\
f_2 &:& identity \rightarrow sex \\
\end{eqnarray*}

そこで、\(f_1\)と\(p_1\)、さらに\(f_2\)と\(p_2\)が与えられた時の\(u\)を考える。前の記事で示したように、\(u\)は\(f_1\)と\(p_1\)が与えられた時に選択的に決まる。また、\(f_2\)と\(p_2\)が与えられた時にも同じである。もし、選択肢が複数ではなく、それぞれ一つしかなく、しかも、それらが同じである時、即ち、
\begin{eqnarray*}
p_1 \circ u \ (born \times sex) & = & f_1 (born \times sex), \\
p_2 \circ u \ (born \times sex) & = & f_2 (born \times sex)
\end{eqnarray*}
の時、対象\(born \times sex\)は、対象\(born\)と\(sex\)(及び射\(p_1\)と\(p_2\))による積と呼ばれる。また、\(p_1\)と\(p_2\)はプロジェクションと呼ばれる。

一般に、対象\(X, B_1, B_2\)と射
\begin{eqnarray*}
f_1 & : & X \rightarrow B_1, \\
f_2 & : & X \rightarrow B_2, \\
p_1 & : & B_1 \times B_2 \rightarrow B_1, \\
p_2 & : & B_1 \times B_2 \rightarrow B_2, \\
u & : & X \rightarrow B_1 \times B_2
\end{eqnarray*}
が下図において可換図である時、
f:id:bitterharvest:20150203112114p:plain

即ち、
\begin{eqnarray*}
p_1 \circ u & = & f_1 \\
p_2 \circ u & = & f_2
\end{eqnarray*}
のとき、対象\(B_1 \times B_2\)は、対象\(B_1\)と\(B_2\)(および射\(p_1\)と\(p_2\))による積と呼ばれる(なお、もう少し一般的にするためには、対象\(B_1 \times B_2\)を対象\(P\)で置き換えるとよい)。\(p_1\)と\(p_2\)はプロジェクションと呼ばれる。この時、\(u\)は\(f_1\)と\(f_2\)から定まるので、\(u\)が出力する最初の項は\(f_1\)から最後の項は\(f_2\)から定まるので、\(u\)を\( < f_1, f_2 > \)と記述する。

個人識別の記述は具体例を加えると分かりやすくなると思う。例えば、テニスで活躍中の錦織圭の場合は次の図で表すことができる。
f:id:bitterharvest:20150203114518p:plain

そこで、\(f'_i=f_i \circ h, p'_i=p_i \circ h, u'=u \circ h \)、なお、\(i=1,2\)とすると、次の図を得ることができる。
f:id:bitterharvest:20150203115451p:plain

2.最大公約数(\(GCD\))

12と18の約数は1,2,3,6である。その中で最大の約数が最大公約数なので、12と18の最大公約数は6である。対象\(B_1\)を12とし、対象\(B_2\)を18とし、\(B_1 \times B_2\)を\( GCD (12, 18) = 6 \)とし、\(X\)を約数とすれば、例えば3、下図の青線で示す可換図が得られる。また、射\(f_1,f_2,u\)もそれぞれ図に示すようになる。さらに、約数2についても赤線で示す可換図が得られる。
f:id:bitterharvest:20150204082326p:plain

この可換図から、\(B_1\)と\(B_2\)が共通に有している性質の中で最大のもの、ここでは約数という性質の中で最大のもの、を\(B_1 \times B_2\)は表しているということが分かる。

それでは、二つの自然数a,bが与えられた時、その約数を求めるプログラムをHaskellで書いてみる。

module GCD where
divider :: Int -> Int-> [Int]
divider a b = [c | c <- [1..(min a b)], mod a c == 0, mod b c == 0]

これを実行すると

*GCD> divider 12 18
[1,2,3,6]

となる。

3.積集合

離散系が続いたので、連続系での対象の積について考える。対象\(B_1\)と\(B_2\)は下図で示すようにそれぞれ青色と黄色の領域(集合)とする。この二つの領域が重なっている部分があるとすると、重なっている中で最大の領域をとったものが\(B_1\)と\(B_2\)の積集合\(B_1\cap B_2\)である。\(X\)は\(B_1\)の部分集合であるとともに、かつ、\(B_2\)の部分集合でもある領域とする。この時、積集合は下図の可換図で表すことができる。なお、下図ですべての関数は包含写像\( \hookrightarrow \)である(包含写像の定義は\(\hookrightarrow:A \rightarrow B, A \subset B \)とした時、\(t \in A\)は\(\hookrightarrow(t) = t \in B\)であるが、元の場所に収まると理解しておけばよい)。
f:id:bitterharvest:20150204085654p:plain

今、\(B_1\cap B_2\)と位相同型な領域を\(Y\)とする。この時、逆関数を有する(あるいは一対一対応を与える)関数\(g: Y \rightarrow\ B_1\cap B_2\)が存在する。そこで、\(Y\)内に\(X\)に対応する\(Z\)を用意する。この時、\(Z\)と\(X\)を与える関数は\(h = g_{Z | Y}: Z \rightarrow X\)をなる。勿論、\(h\)は逆関数を有する(一対一対応を与える)。これらの関係は下図の可換図になる。
f:id:bitterharvest:20150204093107p:plain

そこで、\(X\)のところに\(Z\)を持ってきたときの可換図は次のようになる。
f:id:bitterharvest:20150204095025p:plain
上の図から、対象\(X\)はそれと位相同型なもので置き換えることができるということが分かり、積集合の概念が一般化される。

4.Haskellでの対象の積の定義

対象の積を定義した下図を利用して
f:id:bitterharvest:20150203112114p:plain
積のデータ型Product b1 b2を、関数p1,p2,uとともに作成すると次のようになる。

module Product where

data Product b1 b2 = Product b1 b2 deriving (Eq, Show, Read)
p1 (Product b1 b2) = b1
p2 (Product b1 b2) = b2
u f1 f2 x = Product (f1 x) (f2 x) 

これを最大公約数のときの例で確認してみる。図は次のようになっていた。
f:id:bitterharvest:20150204082326p:plain
そこで、12と18の積を作成し、関数p1,p2,uを次のように利用する。

Prelude> :load "Product.hs"
[1 of 1] Compiling Product          ( Product.hs, interpreted )
Ok, modules loaded: Product.
*Product> let p = Product 12 18
*Product> p1 p
12
*Product> p2 p
18
*Product> u (*4) (*6) 3
Product 12 18
*Product> p1 (u (*4) (*6) 3)
12
*Product> p2 (u (*4) (*6) 3)
18

テニス選手の場合には次のようになる。モジュールの中にテニス選手のデータも加え次のようにする。

module Product where

data Product b1 b2 = Product b1 b2 deriving (Eq, Show, Read)
p1 (Product b1 b2) = b1
p2 (Product b1 b2) = b2
u f1 f2 x = Product (f1 x) (f2 x) 

n = Product 1989 "male"
d = Product 1970 "female"

f1' :: String -> Num
f1' "Nishikori_Kei" = 1989
f1' "Date_Kimiko" = 1970
f1' _ = error "Input a name."

f2' :: String -> String
f2' "Nishikori_Kei" = "male"
f2' "Date_Kimiko" = "female"
f2' _ = error "Input a name."

これを実行すると次のようになる。期待した結果が得られる。

Prelude> :load "Product.hs"
[1 of 1] Compiling Product          ( Product.hs, interpreted )
Ok, modules loaded: Product.
*Product> u f1' f2' "Nishikori_Kei"
Product 1989 "male"
*Product> p1 (u f1' f2' "Nishikori_Kei")
1989
*Product> p2 (u f1' f2' "Nishikori_Kei")
"male"
*Product> u f1' f2' "Date_Kimiko"
Product 1970 "female"
*Product> p1 (u f1' f2' "Date_Kimiko")
1970
*Product> p2 (u f1' f2' "Date_Kimiko")
"female"