次の例はモノイドだ。モノイドの定義はいくつかあるが、古典的な定義は、集合\(M\)の上に次の二つの射をもち、結合律と単位律を満たすことだ。なお\(1\)は自然数のときに用いた終対象だ。
\begin{eqnarray}
μ &:& M \times M \rightarrow M; x + y \mapsto z \ (if \ addition), \\
η &:&1 \rightarrow M; * \mapsto 0 \ (if \ addition)
\end{eqnarray}
これより\( [η, μ]:1 + M \times M \rightarrow M\)となり、\(F: X \rightarrow 1 + X \times X \)である。なお\(+\)は自然数のときと同様に直和だ。
モノイドは、演算を\(\circ\)としたとき、次を満たすものである(半群は単位元がなくてもよい)。
1) 任意の\(a,b\)に対して、\(a \circ b \in R\)
2) 結合律( \( (a \circ b) \circ c = a \circ (b \circ c)\) )を満たし、
3) 単位元( \(i \in R \))を有し、単位律( \( i \circ a = a = a \circ i \))を満たす。
アーベル群とは上記の性質に加えて、次を満たすものである。
4) 任意の\(a\)に対して逆元 \( (a^{-1}) \)を有する。なお、逆元とは\( a \circ a^{-1} = i \)を満たすものである。
5) 可換律(\( a \circ b = b \circ a \))を満たす。
従ってアーベル群は
\begin{eqnarray}
μ &:& M \times M \rightarrow M; x + y \mapsto z \ (if \ addition), \\
η &:&1 \rightarrow M; * \mapsto 0 \ (if \ addition) \\
ι &:& M \rightarrow M; x \mapsto (-x) \ (if \ addition)
\end{eqnarray}
に加えて、単位律、結合律、可換律を満たすものである。
このためアーベル群では自己関手\(F\)は\(F: 1 + X + X \times X\)となる。またモノイドでは\(F: 1 + X \times X\)であったので、環では\(F: 1 + 1 + X + X \times X + X \times X\)となる。
不動点の定義より、
\begin{eqnarray}
Fix \circ unFix = id \\
unFix \circ Fix = id
\end{eqnarray}
であることに注意しておこう。
４．３ Lambekの定理
台集合\(A\)と評価射\(α:F(A) \rightarrow A\)の対( \( (A, F(A) \rightarrow A \) )をF-代数と定めた。それでは、二つの代数が存在したときに、片方の代数の構造が他方の代数の構造の中で保持されているという性質をどのように記述したらよいのかについて考えよう。構造が保たれるということは、圏論の世界では大切な性質で、たとえば関手はこの役割を担っている。
F-代数の圏
いま二つのF-代数( \( A, α:F(A) \rightarrow A \) )と( \( B, β:F(B) \rightarrow B \) )があったし、前者の代数の構造が、後者の代数の構造の中で保持される条件を考えることにしよう。図７：F-代数( \( A, F(A) \rightarrow A \) )と( \( B, F(B) \rightarrow B \) )が準同型のとき、\(m\)は関手となり、上図は可換図式となる
対象\(A\)から対象\(B\)への射を\(m\)とする。上の図で\( F(A) \)から\(B\)を得ることを考える。経路は二つある。上側の経路を辿ると\(β \circ F(m) \)となる。これは後者の代数の方に移って計算するというものである。下側の経路を辿ると\(m \circ α\)である。これは前者の代数で計算した後で、その値を後者の値に変えるというものである。これが一致することが、構造を保持するための約束なので、次の式を得る。
\begin{eqnarray}
β \circ F(m) = m \circ α
\end{eqnarray}
ある代数の構造が別のある代数の構造の中で保たれるとき、準同型(homomorphism)であると言い、その条件は上に示した式である。これより\(F\)代数\( (A, α:F(A) \rightarrow A) \)と\( (B, β:F(B) \rightarrow B) \) を圏とした時に、\(m\)が関手であれば二つの圏は準同型となる。そして上図は可換図式となる。
そして準同型を射として構成した圏をF-代数の圏と呼ぶ。上図であれば\(m\)が射、( \( A, α:F(A) \rightarrow A \) )と( \( B, β:F(B) \rightarrow B \) )が対象となる。
cata :: Functor f => Algebra f a -> Fix f -> a
cata alg = alg . fmap (cata alg) . unFix
ここまでのプログラムはまとめると次のようになる。
type Algebra f a = f a -> a
newtype Fix f = Fix ( f (Fix f))
unFix :: Fix f -> f (Fix f)
unFix (Fix x) = x
cata :: Functor f => Algebra f a -> Fix f -> a
cata alg = alg . fmap (cata alg) . unFix
data ListF a b = Nil | Cons a b
instance Functor (ListF a) where
fmap f Nil = Nil
fmap f (Cons e lst) = Cons e (f lst)
sumAlg :: Algebra (ListF Int) Int
sumAlg Nil =0
sumAlg (Cons e acc) = e + acc
左下は\(Cons\)によってこれまでのものに\(e\)を追加するということになる。これまでのものは先ほどの\(Fix \ N il\)である。またここは不動点であるので、前のときと同じよう\(Fix\)をつけて\(Fix \ $ \ Cons \ e \ (Fix \ N il) \)となる。
これを\(unFix\)で持ち上げると、左上の\( Cons \ e \ (Fix \ N il) \)となる。これに\(fmap \ (cata \ sumAlg) \) を施すと、
\begin{eqnarray}
&& fmap \ (cata \ sumAlg) \ (Cons \ e \ (Fix \ N il)) \\
&=& Cons \ e \ ( (cata \ sumAlg) \ (Fix \ N il)) \\
&=& Cons \ e \ N il
\end{eqnarray}
より、右上は\( Cons \ e \ N il \)となる。これを評価射\(sumAlg\)で値を得ると、右下の\(e\)となる。
群論でのモノイドを、圏論での圏として、構成することを考えてみよう。圏の主要な構成要素は対象と射である。高校までの数学で学んできた「集合と関数」の考え方に素直に従った場合、集合を対象に、関数を射にするのが自然のように思われるだろう。すなわち集合\(S\)を対象に、二項演算子\(\bullet : S \times S \rightarrow S\)を射にしてはと思うだろう。
このようにすると、困った問題が生じる。圏を構成するためには、射と射を結びつける合成を必要とする。射が二項演算子\(\bullet : S \times S \rightarrow S\)だとすると、合成は何にしたらよいのだろう。私も圏論を学び始めたときは、ここでおおいに悩んだ。
newtype Product n = Product n
instance Num n => Semigroup (Product n) where
Product x <> Product y = Product (x * y)
instance Num n => Monoid (Product n) where
mempty = Product 1
同じように足し算は次のようになる。
newtype Sum n = Sum n
instance Num n => Semigroup (Sum n) where
Sum x <> Sum y = Sum (x + y)
instance Num n => Monoid (Sum n) where
mempty = Sum 0
instance Semigroup () where
_ <> _ = ()
instance Monoid () where
mempty = ()
instance (Semigroup a, Semigroup b) => Semigroup (a, b) where
(a, b) <> (a’,b’) = (a <> a’, b <> b’)
instance (Monoid a, Monoid b) => Monoid (a, b) where
mempty = (mempty, mempty)
\(λ : I \otimes M \cong M \\ ρ : M \cong M \otimes I\)
結合律
\((a \bullet b) \bullet c =a \bullet (b \bullet c) \)
\( α : (M \otimes M) \otimes M \cong M \otimes (M \otimes M)\)
すなわち圏\(\mathcal{C}\)を対象とし、関手\(M\)を射とし、そして自身への関手\(I\)を恒等射とし、関手と関手の合成\(\otimes\)をモノイドでの合成としたものだ。もちろん単位律
\begin{eqnarray}
λ : I \otimes M \cong M \\
ρ : M \cong M \otimes I
\end{eqnarray}
と結合律
\begin{eqnarray}
α : (M \otimes M) \otimes M \cong M \otimes (M \otimes M)
\end{eqnarray}
は満たさなければならない。なお上記で\( \cong \)は自然同型である。自然同型について簡単にふれておこう。ある空間\(A\)からある空間\( B\)への射\(f\)が逆写像を有するとき、射\(f\)を同型射あるいは単に同型という。空間を圏とし、写像を関手としたときに、関手にたいして同様なことが成り立つときに、自然同型という。
さて今導入したモノイドの構造では、モノイドが有する性質、すなわち二項演算子が見えにくい。そこで射\(M,I\)を対象にし、モノイドの構造が現れるようにしよう。二項演算子を一般化するとテンソル積となるが、ここではこれを表すために\(\otimes\)を用いよう。そしてテンソル積が圏の構成の中で表れるようにしよう。すなわち、テンソル積\(μ: M \otimes M \rightarrow M\)を射と考えることにしよう。
モノイド対象( \( M,μ,η\))とはモノイド圏(\( \mathcal{C}, \otimes, I, α, λ, ρ \))が与えられた時、\(\mathcal{C}\)の対象\(M\)および二つの射(\(μ : M \otimes M \rightarrow M, η: I \rightarrow M \))を有し、下記の単位子図式と五角形図式を満たすものである。図５：モノイド対象での単位子図式
図６：モノイド対象での五角形図式
３．６ モノイド圏
モノイド圏は一つまたは複数のモノイド対象をその対象にしたもので次のように定義される。
[モノイド圏の定義]
モノイド圏(\( \mathcal{C}, \otimes, I, α, λ, ρ \))とは、圏 \(\mathcal{C} \)が次の条件を備えているときである。
1) テンソル積と呼ばれる双関手\(\otimes : \mathcal{C} \times \mathcal{C} \rightarrow \mathcal{C} \)
2) モノイド単位(あるいは単位対象)\(I\)
3) 結合律：\(α_{A,B,C}: (A \otimes B) \otimes C \cong A \otimes (B \otimes C)\) (ただし、\(α\)は自然同型)
4) 右単位律：\(λ_A : I \otimes A \cong A \), 左単位律：\(ρ_A : A \otimes I \cong A \) (ただし、\(λ, ρ\)は自然同型)
モノイド圏を概念図で表すと以下のようになる。図７：モノイド圏の概念図
モノイド対象( \( M,μ,η\))は、モノイド圏(\( \mathcal{C}, \otimes, I, α, λ, ρ \))が与えられた時、\(\mathcal{C}\)の対象\(M\)および二つの射(\(μ : M \otimes M \rightarrow M, η: I \rightarrow M \))を有し、下記の単位子図式と五角形図式を満たすものであった。この定義の中で重要なのは、モノイド対象を定義している二つの射(\(μ : M \otimes M \rightarrow M, η: I \rightarrow M \))だ。
そこで、ここでは、これら二つについて考えてみることにしよう。矢印の方向を反対にすると、
\begin{eqnarray}
δ : M \rightarrow M \otimes M \\
ε: M \rightarrow I
\end{eqnarray}
集合と関数は馴染みのある言葉だ。集合\(A\)と\(B\)があり、\(A\)のそれぞれの要素に対して\(B\)のある要素を割当てる関数\(f\)があるというのが出発点になっている。さらに集合\(C\)があり、\(B\)から\(C\)へ写像する関数\(g\)がある。このとき、\(f\)と\(g\)を合成した関数は、\(A\)から\(C\)への写像となる。これを\(h\)で表すと、\(h (x) = g \circ f (x)\)となる。
このような集合と関数の概念を、圏論の世界で、なるだけ一般的に表そうとしたのが、アロー(arrow)と呼ばれる概念だ。そこではすべてをアローで表す。アローは\(k \ a \ b\)で表され、これは射\(k\)が\(a\)から\(b\)へと向かうと考えるとよい。
先の集合と関数で説明した関数\(f\)は\(k \ A \ B\)となり、集合\(A\)は恒等射\(k \ A \ B\)となる。また、関数の合成\(g \circ f\)は\(k \ B \ C \ . \ k \ A \ B\)となり、準同型写像となる。
上で説明した集合を任意のものについて論じている場合には、Haskellでは型変数を用い、その場合には小文字を用いる。例えば\(f\)は\(k \ a \ b\)のようになる。
これを図で表すと以下のようになる。これからも分かるように、集合と関数の空間からアローだけで構成された世界へと関手\(arr\)で写像して圏を構成している。図１２：アロー\(k \ a \ b \)は\(a\)から\(b\)へと向かう射\(k\)であるが、関手\(arr\)によって集合と関数の世界からアローだけで構成された世界へと移動することができる。
実行例を示してみよう。但し、”Data.Category”には関数が実装されていないので、”Control.Arrow”のライブラリーをインポートして使った。以下の実行例で、\(x -> x \)は入力、\(y -> y \)は出力を意味し、集合での\(A\)と\(B\)に相当する。図１３：アローを用いた世界での実行例
class Category k => HasTerminalObject k where
type TerminalObject k :: *
terminalObject :: Obj k (TerminalObject k)
terminate :: Obj k a -> k a (TerminalObject k)
ところで並列処理にするためには、上図に示したように、複数の入力、複数の関数、複数の出力が必要になる。ライブラリーでは、この複数に対応するのが、バイナリー積(\(BinaryProduct\))だ。クラスの定義の中で\( BinaryProduct (k :: * -> * -> *) x y :: *\)と定義されている。また、インスタンス\( (->)\)に対しては\( BinaryProduct (->) x y = (x, y) \)と定義されている。
ライブラリーではクラスは次のように定義されている。
class Category k => HasBinaryProducts k where
type BinaryProduct (k :: * -> * -> *) x y :: *
proj1 :: Obj k x -> Obj k y -> k (BinaryProduct k x y) x
proj2 :: Obj k x -> Obj k y -> k (BinaryProduct k x y) y
(&&&) :: k a x -> k a y -> k a (BinaryProduct k x y)
(***) :: k a x -> k b -> k (BinaryProduct k a b) (BinaryProduct k b1 b2)
l *** r = (l . proj1 (src l) (src r)) &&& (r . proj2 (src l) (src r))
instance HasBinaryProducts (->) where
type BinaryProduct (->) x y = (x, y)
proj1 _ _ = \(x, _) -> x
proj2 _ _ = \(_, y) -> y
f &&& g = \x -> (f x, g x)
f *** g = \(x, y) -> (f x, g y)
class (Category (Dom ftag), Category (Cod ftag)) => Functor ftag where
type Dom ftag :: * -> * -> *
type Cod ftag :: * -> * -> *
type ftag :% a :: *
(%) :: ftag -> Dom ftag a b -> Cod ftag (ftag :% a) (ftag :% b)
instance HasBinaryProducts k => Functor (ProductFunctor k) where
type Dom (ProductFunctor k) = k :**: k
type Cod (ProductFunctor k) = k
type ProductFunctor k :% (a, b) = BinaryProduct k a b
ProductFunctor % (a1 :**: a2) = a1 *** a2
class (Functor f, Dom f ~ (Cod f :**: Cod f)) => TensorProduct f where
type Unit f :: *
unitObject :: f -> Obj (Cod f) (Unit f)
leftUnitor :: Cod f ~ k => f -> Obj k a -> k (f :% (Unit f, a)) a
leftUnitorInv :: Cod f ~ k => f -> Obj k a -> k a (f :% (Unit f, a))
rightUnitor :: Cod f ~ k => f -> Obj k a -> k (f :% (a, Unit f)) a
rightUnitorInv :: Cod f ~ k => f -> Obj k a -> k a (f :% (a, Unit f))
associator :: Cod f ~ k => f -> Obj k a -> Obj k b -> Obj k c -> k (f :% (f :% (a, b), c)) (f :% (a, f :% (b, c)))
associatorInv :: Cod f ~ k => f -> Obj k a -> Obj k b -> Obj k c -> k (f :% (a, f :% (b, c))) (f :% (f :% (a, b), c))
instance (HasTerminalObject k, HasBinaryProducts k) => TensorProduct (ProductFunctor k) where
type Unit (ProductFunctor k) = TerminalObject k
unitObject _ = terminalObject
leftUnitor _ a = proj2 terminalObject a
leftUnitorInv _ a = terminate a &&& a
rightUnitor _ a = proj1 a terminalObject
rightUnitorInv _ a = a &&& terminate a
associator _ a b c = (proj1 a b . proj1 (a *** b) c) &&& (proj2 a b *** c)
associatorInv _ a b c = (a *** proj1 b c) &&& (proj2 b c . proj2 a (b *** c))
