１．積の定義
前の記事で、最大公約数や積集合を用いて、圏論での積について説明した。積は、いろいろな圏に共通する性質で、普遍的な性質である。ここでは、圏論での用語を用いて、圏論での積についてまとめる。
圏論での積は次のように定義されている。
積の定義：
対象\(B_1\), \(B_2\)の積とは、対象\(P\)、射\(p_1: P \rightarrow B_1\), \(p_2: P \rightarrow B_2\)からなり、次の条件を満足するものである。任意の対象\(X\)と任意の射\(f_1: X \rightarrow B_1\), \(f_2: X \rightarrow B_2\)が与えられた時、以下の図式が可換となるような\(u: X \rightarrow P\)が唯一つ存在する。このとき、\(P\)は \(B_1 \times B_2\)と表す。
可換図式は以下のとおりである。
２．Haskellでの実装
そこで、圏の積をHaskellで表すために、この型クラスを用意する。プログラムは次のようになる。
module Product where class Product t where p1 :: t a a -> a p2 :: t a a -> a
型クラスの名前はProductとし、圏の積の定義で出てきた射\(p_1\)と射\(p_2\)を用意する。また、積の演算\(\times\)は扱っている圏によって異なるので、ここでは定義せず、サブクラスで定義する。また、積\(B_1 \times B_2\)を構成する\(B_1 \),\(B_2\)の対は、型変数tで表す。これはインスタンスを作成するときに指定する。射\(p_1\)はプログラムではp1となっていて、これは、\(B_1 \),\(B_2\)の対を入力し（対の型変数はt、対の構成要素の型変数はそれぞれaである）、対象\(B_1\)（型変数がa）を出力とする関数である。射\(p_1\)も同様である。
次に対象\(B_1\), \(B_2\)が整数である時のサブクラスIntegralProductを次のように用意した。
class (Product t) => (IntegralProduct t) where product' :: (Integral a) => t a a -> a
積の演算\(\times\)はproduct'で表した。また、\(B_1\), \(B_2\)は整数となるように、aをIntegralと制約した。
３．最大公約数
実際に、この型クラスを用いて、最大公約数を求める。例を下図に示す。
この図で、\(B_1\), \(B_2\)はそれぞれ、360と4620である。素数分解するとそれぞれ\(2 \times 2 \times 3 \times 5 \times 2 \times 3\)と\(2 \times 2 \times 3 \times 5 \times 7 \times 11\)である。共通の約数は、(2,2,3,5)となり、最大公約数は60となる。また、約数は(2,2,3,5)の中から任意の組合せを選び、それらの積となる（なお、上の図で、赤い矢印は約数の小さい方から大きい方へと約数を辿っている）。
従って、上記では、対象は\(B_1={360}\),\(B_2={4620}\), \(P={60}\), \(X=\{30,20,15,12,10,6,5,4,3,2,1\}\)である。射は\(p_1\), \(p_2\), \(u\), \(f_1\), \(f_2\)である。これらの射は次のようになっている。
\begin{eqnarray*}
p_1 & = & (\times \ b_1 / GCD(b_1,b_2)), \\
p_2 & = & (\times \ b_2 / GCD(b_1,b_2)), \\
f_1 & = & (\times \ b_1 / x_i), \\
f_2 & = & (\times \ b_2 / x_i), \\
u & = & (\times \ GCD(b_1,b_2) / x_i), \ x_i \in X
\end{eqnarray*}
これから\(u\)は次の式を満足することが分かる。
\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\)をタプルを用いて\( (B_1,B_2) \)と表わす。従って、積は、このタプルにproduct'を施すことで得られる。
親クラスのproductをインスタンス化すると次のようになる。
instance Product (,) where p1 = fst p2 = snd
\(p_1\)はタプルの最初の要素を取り出し、\(p_2\)は二番目の要素を取り出す。
子クラスのIntegralProductをインスタンス化すると次のようになる。
instance IntegralProduct (,) where product' = \x -> gcd (p1 x) (p2 x)
上記のプログラムで、積として\(gcd\)を用いた。
実行してみる。\( (B_1,B_2) \)をx0= (2 * 2 * 3 * 5 * 2 * 3, 2 * 2 * 3 * 5 * 7 * 11) とし、\(B_1\), \(B_2\), \(P\)であるb1,b2,pを求めると以下のようになる。
Prelude> :load "ProductCategory.hs" [1 of 1] Compiling ProductCategory ( ProductCategory.hs, interpreted ) Ok, modules loaded: ProductCategory. *ProductCategory> let x0 = (2 * 2 * 3 * 5 * 2 * 3, 2 * 2 * 3 * 5 * 7 * 11) *ProductCategory> let b1 = p1 x0 *ProductCategory> let b2 = p2 x0 *ProductCategory> let p = product' x0 *ProductCategory> b1 360 *ProductCategory> b2 4620 *ProductCategory> p 60
また、\(f_1 = p_1 \circ u\),\(f_2 = p_2 \circ u\)を確認するために、それぞれの約数に対して調べてみる。プログラム全体は、以下の様である。
module Product where class Product t where p1 :: t a a -> a p2 :: t a a -> a class (Product t) => (IntegralProduct t) where product' :: (Integral a) => t a a -> a instance Product (,) where p1 = fst p2 = snd instance IntegralProduct (,) where product' = \x -> gcd (p1 x) (p2 x) x0 = (2 * 2 * 3 * 5 * 2 * 3, 2 * 2 * 3 * 5 * 7 * 11) x1 = (1 * 2 * 3 * 5 * 2 * 3, 1 * 2 * 3 * 5 * 7 * 11) x2 = (2 * 2 * 1 * 5 * 2 * 3, 2 * 2 * 1 * 5 * 7 * 11) x3 = (1 * 1 * 3 * 5 * 2 * 3, 1 * 1 * 3 * 5 * 7 * 11) x4 = (2 * 2 * 3 * 1 * 2 * 3, 2 * 2 * 3 * 1 * 7 * 11) x5 = (1 * 2 * 1 * 5 * 2 * 3, 1 * 2 * 1 * 5 * 7 * 11) x6 = (1 * 2 * 3 * 1 * 2 * 3, 1 * 2 * 3 * 1 * 7 * 11) x7 = (1 * 1 * 1 * 5 * 2 * 3, 1 * 1 * 1 * 5 * 7 * 11) x8 = (2 * 2 * 1 * 1 * 2 * 3, 2 * 2 * 1 * 1 * 7 * 11) x9 = (1 * 1 * 3 * 1 * 2 * 3, 1 * 1 * 3 * 1 * 7 * 11) x10 = (1 * 2 * 1 * 1 * 2 * 3, 1 * 2 * 1 * 1 * 7 * 11) x11 = (1 * 1 * 1 * 1 * 2 * 3, 1 * 1 * 1 * 1 * 7 * 11) x0' = product' x0 x1' = product' x1 x2' = product' x2 x3' = product' x3 x4' = product' x4 x5' = product' x5 x6' = product' x6 x7' = product' x7 x8' = product' x8 x9' = product' x9 x10' = product' x10 x11' = product' x11 u1 = div p x1' u2 = div p x2' u3 = div p x3' u4 = div p x4' u5 = div p x5' u6 = div p x6' u7 = div p x7' u8 = div p x8' u9 = div p x9' u10 = div p x10' u11 = div p x11' -- p1 . u == f1 s1 = 6 * u1 == div b1 x1' s2 = 6 * u2 == div b1 x2' s3 = 6 * u3 == div b1 x3' s4 = 6 * u4 == div b1 x4' s5 = 6 * u5 == div b1 x5' s6 = 6 * u6 == div b1 x6' s7 = 6 * u7 == div b1 x7' s8 = 6 * u8 == div b1 x8' s9 = 6 * u9 == div b1 x9' s10 = 6 * u10 == div b1 x10' s11 = 6 * u11 == div b1 x11' -- p2 . u == f2 t1 = 7 * 11 * u1 == div b2 x1' t2 = 7 * 11 * u2 == div b2 x2' t3 = 7 * 11 * u3 == div b2 x3' t4 = 7 * 11 * u4 == div b2 x4' t5 = 7 * 11 * u5 == div b2 x5' t6 = 7 * 11 * u6 == div b2 x6' t7 = 7 * 11 * u7 == div b2 x7' t8 = 7 * 11 * u8 == div b2 x8' t9 = 7 * 11 * u9 == div b2 x9' t10 = 7 * 11 * u10 == div b2 x10' t11 = 7 * 11 * u11 == div b2 x11'
上のプログラムで、X={x1',x2',..,x11'}であり、s1からs11は\(f_1 = p_1 \circ u\)を確認するため、t1からt11は\(f_2 = p_2 \circ u\)を確認するためである。実行結果の一部を出力すると次のようになる。
*ProductCategory> x3 (90,1155) *ProductCategory> x3' 15 *ProductCategory> s3 True *ProductCategory> t3 True
４．積集合
最大公約数の代わりに積集合を考える。最大公約数では対象は整数であったが、積集合では対象は集合となる。そこで、圏の積のために作成した型クラスProductの子クラスとして、対象を集合にしたSetProductを定義する。プログラムは以下のようになる（なお、このプログラムには、Data.Setをインポートする必要がある）。
class (Product t) => (SetProduct t) where product'' :: (Ord a) => t (Set a) (Set a) -> (Set a)
上記のプログラムで、圏の積が集合に対して定義される。それでは、先ほどと同じで、対象の積をタプルで表し、積集合のプログラムを実装すると次のようになる。
instance SetProduct (,) where product'' = \x -> intersection (p1 x) (p2 x)
上記のプログラムで、積は、積集合intersectionとして実装されている。
実際に下図の例について考えてみる。
この例において、対象は\(B_1=\{a,b,c,d,e\}\), \(B_2=\{d,e,f,g,h\}\), \(P=\{d,e\}=B_1 \times B_2\), \(X=\{\{d\}, \{e\}, \{ \} \}\)である。射は\(p_1\), \(p_2\), \(u\), \(f_1\), \(f_2\)である（なお、上の図で赤い矢印は要素数の少ない方から多い方へと共通の領域を辿っている）。
プログラムを実行することを考える。\(B_1,B_2\)をsetX0 = (fromList ['a', 'b', 'c', 'd', 'e'],fromList ['d', 'e', 'f', 'g', 'h'])として、\(B_1\), \(B_2\), \(P\)を求めると次のようになる。
*ProductCategory> let setX0 = (fromList ['a', 'b', 'c', 'd', 'e'],fromList ['d', 'e', 'f', 'g', 'h']) *ProductCategory> let setB1 = p1 setX0 *ProductCategory> let setB2 = p2 setX0 *ProductCategory> let setP = product'' setX0 *ProductCategory> setB1 fromList "abcde" *ProductCategory> setB2 fromList "defgh" *ProductCategory> setP fromList "de"
\(u\), \(f_1\), \(f_2\)を包含写像と考えると、\(f_1 = p_1 \circ u\), \(f_2 = p_2 \circ u\)が満たされていることが分かる。
５．最小値
負の無限大からある値\(x\)までの領域を\(x = [- \infty, x]\)とする。この時、\(x,y\)の最小値は、二つの領域の積集合となる。このため、二つの値を比較してその最小値を得るためには、上で説明した方法を利用すればよい。
