次の例はモノイドだ。モノイドの定義はいくつかあるが、古典的な定義は、集合\(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))
class Applicative m => Monad m where
(>>=) :: forall a b. m a -> (a -> m b) -> m b
(>>) :: forall a b. m a -> m b -> m b
m >> k = m >>=\_ -> k
return :: a -> m a
return = pure
fail :: String -> m a
fail s = errorWithoutStackTrace s
それではデータ型\(Prod \ e \ a\)をコモナドのインスタンスとして定義しよう。これは次のようになる。
instance Functor (Prod e) where
fmap f (Prod e a) = Prod e (f a)
instance Comonad (Prod e) where
f =>= g =\(Prod e a) ->let b = f (Prod e a)
c = g (Prod e b)
in c
extract (Prod e a) = a
それではプログラムを使った例を示そう。図６：環境でカプセル化したデータ型\(P( e \ a)\)の実行例
プログラムのコードは次のようになっている。図７：環境でカプセル化したデータ型\(P( e \ a)\)のコード
\((=>=)\)の定義の中では二つの関数を入力にしている。即ち\(f : w \ a \rightarrow b\)と\(g: w \ b \rightarrow c\)である。\(g\)は入力として\(w \ b\)を必要とするので、\(f\)を利用して\(w \ b\)を出力するような関数\(extend\)を定義しよう。これは次のようになる。
instance Functor Stream where
fmap f Null = Null
fmap f (Cons a as) = Cons (f a) (fmap f as)
instance Comonad Stream where
extract (Cons a _) = a
duplicate Null = Null
duplicate (Cons a as) = (Cons (Cons a as) (duplicate as))
sumN :: Num a => Int -> (Stream a) -> a
sumN n Null =0
sumN n (Cons a as) =if n <=0then0else a + (sumN (n-1) as)
aveN :: Fractional a => Int -> Stream a -> a
aveN n Null =0
aveN n stm = (sumN n stm) / (fromIntegral n)
以下のプログラムで、\(zipstream\)はある時点での出力信号を求めるためのものである。これはストリームになっていて、この時点に入ってきた入力信号に対するこの時点の出力信号、その一つ前の時点で入ってきた入力信号に対するこの時点の出力信号、さらに一つ前の入力信号に対するこの時点の出力信号となっている。即ち、この時点までに入ってきた入力信号からの子の時点での出力信号の列である。\(zipstream\)は三つの入力を受ける。それらは \( f \ inp \ stm\)で、\(inp\)はインパルス応答、\(stm\)は入力信号である。なお、\(f\)はインパルス応答と入力信号のそれぞれに対する演算で、この場合は常に乗算である。
また、\(conv\)はある時点での出力信号の総和をとる。
zipstream :: Num a => (a -> a -> a) -> (Stream a) -> (Stream a) -> (Stream a)
zipstream f Null _ = Null
zipstream f _ Null = Null
zipstream f (Cons a as) (Cons b bs) = Cons (f a b) (zipstream f as bs)
conv :: Num a => (Stream a) -> a
conv Null =0
conv (Cons a as) = a + (conv as)
\(out\)は現時点までの出力信号の列である。
outC :: Num a => (Stream a) -> (Stream a) -> (Stream a)
outC inp stm = fmap conv (extend (zipstream (*) inp) stm)
--outC inp stm = fmap conv (fmap (zipstream (*) inp) (duplicate stm))
それではコモナドと随伴との関係を見てみよう。随伴には、内容は同じだが複数の定義がある。余単位(counit)・単位(unit)随伴はその中の一つで、それは次のようになっている。
圏\(\mathcal{C}\)と\(\mathcal{D}\)の余単位・単位随伴は二つの関手
\begin{eqnarray}
L: \mathcal{D} \rightarrow \mathcal{C} \\
R: \mathcal{C} \rightarrow \mathcal{D}
\end{eqnarray}
および二つの自然変換
\begin{eqnarray}
η: I_\mathcal{D} \rightarrow R \circ L \\
ε: L \circ R \rightarrow I_\mathcal{C}
\end{eqnarray}
であって(ηは単位、εは余単位と呼ばれる)、これらの合成
\begin{eqnarray}
L =L \circ I_\mathcal{D} \xrightarrow{L \circ η} L \circ R \circ L \xrightarrow{ε\circ L} L \\
R = I_\mathcal{D} \circ R \xrightarrow{η\circ R} R \circ L \circ R \xrightarrow{R \circ ε} R
\end{eqnarray}
がそれぞれ\(L\)と\(R\)上の恒等変換\(I_L,I_R\)となることである。これは三角恒等式(triangle identities)と呼ばれる。
図で表してみよう。随伴の定義に関する図は次のようになっている。図１７：随伴の定義にはいくつかあるが、単位(\(unit:I_\mathcal{D} \rightarrow R \circ L\))・余単位(\(counit:L \circ R \rightarrow I_\mathcal{C}\))を用いての定義も良く用いられる
また、三角恒等式を関図式で表すと次の通りだ。図１８：余単位・単位による随伴の定義の一部である三角恒等式の可換図式それではこの定義からコモナドを導くこととしよう。コモナドでの射\(δ,ε\)が、随伴を定めている\(η,ε\)から得られることを示せばよい。そこで、
\begin{eqnarray}
W=L \circ R
\end{eqnarray}
としてみよう。コモナド側の\(ε\)を得ることは簡単だ。
\begin{eqnarray}
ε : I_\mathcal{D} \xrightarrow{ε} L \circ R = W
\end{eqnarray}
それでは\(δ\)について考えよう。次のようにすればよい。
\begin{eqnarray}
δ : W = L \circ R = L \circ I_D \circ R \xrightarrow{L \circ η \circ R} L \circ R \circ L \circ R = W \circ W
\end{eqnarray}
