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

bitterharvest’s diary

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

Haskellで学ぶ圏論・ウォームアップ編 和(余積)のまとめ

1.和(余積)の定義

圏論での和(余積)は積とは双対の概念である。積のところで定義されていた写像のソースとドメインを交換することで、即ち、可換図での矢印を反対向きにすることで、また、積の演算\(\times\)を和の演算\(+\)に代えることで和は定義される。従って、和は次のように定義できる

和の定義:
対象\(B_1\), \(B_2\)の和とは、対象\(Q\)、射\(q_1: Q \rightarrow B_1\), \(q_2: P \rightarrow B_2\)からなり、次の条件を満足するものである。任意の対象\(Y\)と任意の射\(g_1: B_1 \rightarrow Y\), \(f_2: B_2 \rightarrow Y\)が与えられた時、以下の図式が可換となるような\(u': Q \rightarrow Y\)が唯一つ存在する。このとき、\(Q\)は \(B_1 + B_2\)と表す。
f:id:bitterharvest:20150307204002p:plain

和も積と同じようにいろいろな圏に共通する普遍的な性質である。

定義から分かるように、和の圏は次の対象と射で成り立っている。
(1) 対象:\(B_1=\{b_1\}\), \(B_2=\{b_2\}\), \(Q = B_1+B_2=\{b_1+b_2\}\), \(Y=\{y_1, y_2, y_3,..\}\)
(2) 射:\(q_1\), \(q_2\), \(g_1\), \(g_2\), \(u’\)

2.Haskellでの実装

和の圏をHaskellの型クラスSumCategoryとし、射\(q_1\), \(q_2\)次のように定義する。

module SumCategory where
class Sum t where
  q1 :: a -> t a b
  q2 :: a -> t b a

\(B1\),\(B2\)の和が作る対象の具体的な型はインスタンス作成時に指定することとし、ここでは型変数tで与える。
射\(q_1\)は\(B1\)を\(B1+B2\)に写像するので、型シグネチャは、型変数aのものを型変数t a aに写像する。この時、t a a の最初のaは\(B1\)の、次のaは\(B2\)の型変数である。射\(q_2\)についても同様である。

\(B1\),\(B2\)の和をEitherで実装すると、上記の型クラスのインスタンスは次のようになる。

instance Sum Either where
  q1 = Left 
  q2 = Right

上記のプログラムで、q1はLeftで、q2はRightで実現した。Eitherは型コンストラクタ、LeftとRightは値コンストラクタである。その関係は次のように定義される。aとbは型引数である。

data Either a b = Left a | Right b

例えば、

Left ‘A’

とすると、Either Char bという型となる。 また、

Right 7

とすると、Num b -> Either a bとなり、aの型が型クラスNumに属するという制約が与えられる。

3.最小公倍数

和を用いて最小公倍数を得ることを考える。具体的な例で説明したほうが分かりやすいので、下図の場合について説明する。
f:id:bitterharvest:20150308072928p:plain

この例では\(B_1=\{360\}\)と\(B_2=\{4620\}\)の最小公倍数を求める。素数分解すると\( 360 = 2 \times 2 \times 3 \times 5 \times 2 \times 3 \), \( 4620 = 2 \times 2 \times 3 \times 5 \times 7 \times 11 \)となる。素数の中で、最初の四つの数字は両方に共通する素数である。

これから、\(B_1 + B_2 = \{LCM(360,4620)\}= \{27720\}\)。また、\(X\)はそれぞれの数を\(n\)倍したものの集まり、あるいは、\(n\)を約数に含めたものである。即ち、次のようになる。

\begin{eqnarray*}
X & = \{ & LCM(2 \times 2 \times 2 \times 3 \times 5 \times 2 \times 3, 2 \times 2 \times 2 \times 3 \times 5 \times 7 \times 11), \\
& & LCM(3 \times 2 \times 2 \times 3 \times 5 \times 2 \times 3, 3 \times 2 \times 2 \times 3 \times 5 \times 7 \times 11), \\
& & .. \\
& & LCM(n \times 2 \times 2 \times 3 \times 5 \times 2 \times 3, n \times 2 \times 2 \times 3 \times 5 \times 7 \times 11)\} \\
& & ..
\end{eqnarray*}

また、
\begin{eqnarray*}
g_1 & = & ( \times \ y_i / b_1), \ x_i = LCM( (i+1) \times 2 \times 2 \times 3 \times 5 \times 2 \times 3, (i+1) \times 2 \times 2 \times 3 \times 5 \times 7 \times 11), \ i=1,2,3,.. \\
g_2 & = & ( \times \ y_i / b_2), \ x_i =LCM( (i+1) \times 2 \times 2 \times 3 \times 5 \times 2 \times 3, (i+1) \times 2 \times 2 \times 3 \times 5 \times 7 \times 11), \ i=1,2,3,..
\end{eqnarray*}

さらに、
\begin{eqnarray*}
q_1 & = & ( \times \ LCM(b_1,b_2) / b_1) \\
q_2 & = & ( \times \ LCM(b_1,b_2) / b_2) \\
u' & = & ( \times \ y_i / LCM(b_1,b_2))
\end{eqnarray*}
となる。

これから\(u'\)は次の式を満足することが分かる。
\begin{eqnarray*}
u' \circ q_1 & = & g_1, \\
u' \circ q_2 & = & g_2
\end{eqnarray*}

Haskellで実現する。

最小公倍数を扱えるようにするために、型クラスSumのサブクラスを考える。\(b_1\),\(b_2\)の型が整数となるので、サブクラスの名前をIntegralSumとし、次のように定義する。

class  Sum t => IntegralSum t where
  sum' :: (Integral a) => t a a -> t a a -> a

\(b_1\),\(b_2\)との和を型コンストラクタEitherで実装すると、サブクラスIntegralSumのインスタンスは次のようになる。和は最小公約数を求めるlcmとなる。

instance IntegralSum Either where
  sum' x y = lcm (either id id x) (either id id y)

これを用いて先の最小公倍数を求めると次のようになる(なお、このプログラムの実行に当たっては、Data.Eitherをインポートする必要がある)。

b1 = 3 * 4 * 5 * 6
b2 = 3 * 4 * 5 * 7 * 11
q = sum' ((q1 :: a -> Either a b) b1) ((q2 :: a -> Either b a) b2)

実行結果は次のようになる。

*SumCategory> b1
360
*SumCategory> b2
4620
*SumCategory> q
27720

4.和集合

和集合を求める場合を考える。下図の例を用いて説明する。
f:id:bitterharvest:20150308094408p:plain
上の図で、\(B_1=\{a,b,c,d,e\}\), \(B_2=\{d,e,f,g,h\}\)である。また、
\begin{eqnarray*}
Q=B_1+B_2=\{a,b,c,d,e\}\cup (B_2=\{d,e,f,g,h\}=\{d,e\}
\end{eqnarray*}
である。

また、\(X\)は、元の集合に、同じ要素を次々と付け加えたものとなる。上の図では、元の集合のそれぞれに、\(u,v,w,x,y,z,...\)を次々にその要素として加えている。

ここでは集合を扱っているので、集合を対象としたサブクラスを次のように定義する。

class  Sum t => SetSum t where
  sum'' :: (Ord a) => t (Set a) (Set a) -> t (Set a) (Set a) -> (Set a)

これから、Eitherを実装したインスタンスを作成すると次のようになる。なお、sum''はunionで実現される。

instance SetSum Either where
  sum'' x y = union (either id id x) (either id id y)

このサブクラスを用いて、図で示した例を実行すると次のようになる(なお、Data.Either, Data.Setをインポートする必要がある)。

例を実行する。

setB1 = fromList ['a', 'b', 'c', 'd', 'e']
setB2 = fromList ['d', 'e', 'f', 'g', 'h']
setQ  = sum'' ((q1 :: a -> Either a b) setB1) ((q2 :: a -> Either b a) setB2)

実行結果は以下のようになる。

*SumCategory> setB1
fromList "abcde"
*SumCategory> setB2
fromList "defgh"
*SumCategory> setQ
fromList "abcdefgh"

また、\(g_1,g_2,u'\)は包含写像\(\hookrightarrow\)である。これから、
\begin{eqnarray*}
u' \circ q_1 = g_1, \\
u' \circ q_2 = g_2
\end{eqnarray*}
を満たしていることは容易に示すことができる。

5.最大値

負の無限大からある値\(x\)までの領域を\(x = [- \infty, x]\)とする。この時、\(x,y\)の最大値は、二つの領域の和集合となる。このため、二つの値を比較してその最大値を得るためには、上で説明した方法を利用すればよい。