さて\(F\)が定まったので、評価射を具体的に定義しよう。\(F\)の台集合を自然数の代わりに便宜的に整数¥(I nt ¥)とし、評価射\(algN\)を次のように定めよう。
algN :: Algebra NatF Int
algN Zero = 0
algN (Succ n) = n + 1
これを用いて実行してみよう。
例2 モノイド(足し算と掛け算)
次の例はモノイドだ。モノイドの定義はいくつかあるが、古典的な定義は、集合\(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\)となる。
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
まず左下のところから説明しよう。ここは始対象が入る場所だ。\( N il \)がそのような役割を担うが、不動点であるので\( Fix \ N il \)となる。この値を求めたいのだが、下側の射\( (cata \ sumAlg) \)からは直接求めることができないので、上側の経路を経て値を得る。
すなわち\(unFix (Fix \ N il) \)を利用して、左上の\(N il\)を得る。次に\(fmap \ (cata \ sumAlg) \ N il = N il \)によって、右上の\(N il\)を得る。これを評価射\(sumAlg\)で値を得ると、右下の0となる。
それでは、これに\(e\)という値を加える場合を考えてみよう。下図のようになる。
左下は\(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 \))を有し、下記の単位子図式と五角形図式を満たすものである。
3.6 モノイド圏
モノイド圏は一つまたは複数のモノイド対象をその対象にしたもので次のように定義される。
[モノイド圏の定義]
モノイド圏(\( \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\)のようになる。
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
\((=>=)\)の定義の中では二つの関数を入力にしている。即ち\(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)と呼ばれる。
図で表してみよう。随伴の定義に関する図は次のようになっている。
また、三角恒等式を関図式で表すと次の通りだ。それではこの定義からコモナドを導くこととしよう。コモナドでの射\(δ,ε\)が、随伴を定めている\(η,ε\)から得られることを示せばよい。そこで、
\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}