bitterharvest’s diary

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

モノイドーモノイド圏での記述

13.4 モノイド圏での記述

前回の記事で、二項演算を表すための小さい圏の圏(category of small categories)を次のように表した。
f:id:bitterharvest:20171112175354p:plain

この図において、\(f,g\)や\(M(f),M(g)\)などは小さい圏の圏の構成要素には含まれていないので、これを省略することにしよう。
f:id:bitterharvest:20171116094834p:plain
顔がない間延びした図で、少し恐ろしさを感じるが、ここまで来ると、それぞれを構成していた具体的な要素が消失し、抽象化がかなり進んだと認識できるだろう。アセンブラ言語での記述から高級言語への記述へと変化した瞬間を感じ取ることができる。

それではこの図を用いて二項演算、即ち、モノイドを定義してみよう。

二項演算は、同じ対象から二つの値を得て、その間で演算を施し、やはり同一の対象に属す値を結果として返す。これは、圏論では双関手によって表すことができる。このクラスはHaskellでは次のように定義されている。

class Bifunctor p where
  bimap :: (a -> b) -> (c -> d) -> p a c -> p b d

上の定義で、二項演算子を\(\otimes\)と表すならば、\(p\)は\((\otimes)\)と書き直してもよい(二項演算子の中で最も汎用的な演算子テンソル積であり、テンソル積は( \( \otimes \) )と表される。ここでは、最も汎用性のある演算子を表しているという意味で( \( \otimes \) )を用いた)。

そこで、\(bimap\)の対象を自己関手で置き換えと、次のように表すことができる。
\(bimap :: (F \rightarrow F') \rightarrow (G \rightarrow G') \rightarrow (G \circ F \rightarrow F' \circ G') \)
上の定義で、\((F \rightarrow F'),(G \rightarrow G'),(G \circ F \rightarrow F' \circ G') \)は自然変換で、\(\circ\)は関手の合成で、\(\otimes\)と見なせるものである。上の式を互換図で表すと、以下のようになる。
f:id:bitterharvest:20171007174754p:plain

ところで、モノイドの定義はHaskellでは次のようになっていた。

class Monoid m where
  mu :: m -> m ->  m
  eta :: () -> m

これを、\(m\)と\( () \)を小さい圏の圏で用いた自己関手\(M\)と恒等な自己関手\(I\)とし、二項演算子\(\otimes\)を用いて、図で表すと下記のようになる。
f:id:bitterharvest:20171116095235p:plain
f:id:bitterharvest:20171116095250p:plain

これをまとめて一つの互換図で示すと下記のようになる。
f:id:bitterharvest:20171113061310p:plain

モノイド圏を説明するための準備が整ったが、ここでは、Haskellのプログラムで具体的な例を見て、モノイド圏を定義するための準備をしよう。

13.5 Haskellで記述する

はじめに、前回の記事で説明した小さい圏の圏をHaskellで用意しよう。

ここで作るプログラムは、乗算を演算子として持つモノイドである。

\(\mathcal{A}\)を\(n\)とし、\(M(\mathcal{A})\)を\(Product \ n\)とした時に、\(new type\)を用いて\(Product \ n\)を用意しよう。

newtype Product n = Product n deriving (Eq, Ord, Read, Show)

\(Product\)は\(n\)から\(Product \ n\)を導き出す関手である(小さい圏の圏を説明したときの\(M\)に相当)。そこで、これを\(Functor\)のインスタンスとして定義する。さらに\(Product (Product \ n)=Product \ n\)を満たすので、これを\(join\)という関数で定義しておこう。

instance Functor Product where
  fmap f (Product x) = Product (f x)
  
join (Product (Product x)) = Product x

さて、次に小さい圏の圏を作る作業に移ろう。この圏では射を関手としていたので、これを表すようなデータ型を用意しよう。その名前を\(Pfunctor \ x \ y\)とする。ここで、\(Pfunctor\)は、\(x\)を入力、\(y\)を出力とする関数である。また、この関数からの出力を得られるように\(run Pfunctor\)を用意しておこう。

newtype Pfunctor x y = Pfunctor {runPfunctor :: x -> Product y}

また、小さい圏の圏のクラスは次のように定義する。ここでは、恒等射と結合の関数を定義することにする。

class Category cat where
  id :: cat a a
  (.) :: cat b c -> cat a b -> cat a c

\(Pfunctor\)を小さい圏の圏のインスタンスにしよう。

instance Category Pfunctor where
  id = Pfunctor (\x -> Product x)
  (Pfunctor f) . (Pfunctor g) = Pfunctor $ join Prelude.. fmap f Prelude.. g

それでは、\(Pfunctor\)をクラス\(Monoid\)のインスタンスとして定義しよう。
HaskellのPreludeでは、\(Monoid\)は\(mempty,mappend\)を用いて定義されているが、ここでは前々回の記事で紹介したように、 \eta,\(\mu\)を用いることにしよう。

class Monoid' m where
  mu :: m -> m ->  m
  eta :: () -> m

instance Monoid' (Pfunctor x x) where
  eta () = Pfunctor (\x -> Product x)
  mu f g = Pfunctor (\x -> runPfunctor (f Pfunctor.. g) x) 

上のインスタンスの定義の中で、関手\(f,g\)は、\(f=g\)であり、\(f \circ f=f\) を満たさなければならない。

そこで、\(mu\)を直接使うのではなく、同一の関手を使うようにするため、次の\(mu'\)を用意する。

mu' f =  mu f f

また、\(f \circ f=f\)であることを確認するために、\(f \circ f\)と\(f\)で同じ値が得られるかをチェックし、同じであれば出力し、違っていれば出力しないようにしよう。そのために次の関数\(getResult\)を用意する。

getResult f (x,y)
  | a == b = Just a
  | otherwise = Nothing
  where
    a = runPfunctor (mu' f) (x*y)
    b = runPfunctor f (x*y)

\(n\)で割った時の剰余と、絶対値を出力する関手\(modular,abosolute\)を次のように用意しよう。これは、\(f \circ f = f\)の条件を満たしている。

modular :: (Integral y) => y -> Pfunctor y y
modular n = Pfunctor (\x -> Product (mod x n))

absolute :: Pfunctor Integer Integer
absolute = Pfunctor (\x -> Product (abs x))

それではこれを用いて、二つの数\(x,y\)を入力し、\(F x \otimes F y\)を求めてみよう。

*Pfunctor> getResult (modular 5) (34, 67)
Just (Product 3)
*Pfunctor> getResult absolute (12, (-9))
Just (Product 108)

最初の実行例は、入力34,67の5の剰余を求め、その乗算を行うものだ。34の剰余は4であり、67の剰余は2である。従って、4と2の乗算結果は8であるが、これも5の剰余での乗算を行うので、結果は\(Product \ 3\)である。正しい答えであることが分かる。

13.6 モノイド圏

それでは、モノイド圏をまとめよう。モノイド圏は自己関手を対象とし、自然変換を射としているので、次のように定義できる。
1) 対象:関手の集まり\(\{M,I\}\)
2) 射:自然変換\(\mu\)
3) ドメイン・コドメイン
4) 恒等射:自然変換 \eta
5) 合成:\(\circ\)

モノイド圏が結合律、単位律を満たしていることを互換図で確認してみよう。ここでは、\(M \circ M\)を\(M^2\)で表す。
f:id:bitterharvest:20171113062902p:plain

13.7 モナドはモノイド?

この圏の定義も、結合律、単位律の互換図もどこかで見たことはないだろうか。そう、\(M\)を\(T\)で置き換えれば、モナドを説明した記事と同じものだ。このことから次のことがいえる。

モナドは、自己関手の小さい圏の圏で記述されたモノイドと同じ」と言える。

これは重要な定理である。

最後に用いたプログラムのリストをつけておこう。

instance Functor Product where
  fmap f (Product x) = Product (f x)
  
join (Product (Product x)) = Product x

newtype Pfunctor x y = Pfunctor {runPfunctor :: x -> Product y}

class Category cat where
  id :: cat a a
  (.) :: cat b c -> cat a b -> cat a c

instance Category Pfunctor where
  id = Pfunctor (\x -> Product x)
  (Pfunctor f) . (Pfunctor g) = Pfunctor $ join Prelude.. fmap f Prelude.. g

otimes :: (Num n) => (Pfunctor a n, Pfunctor a n) -> (a, a) -> Product n
otimes (Pfunctor f, Pfunctor g) (x, y) = Product c 
  where 
    Product a = runPfunctor (Pfunctor f) x
    Product b = runPfunctor (Pfunctor g) y
    c = a * b

class Bifunctor p where
  bimap :: (a -> b) -> (c -> d) -> (p a c -> p b d)

class Monoid m where
  mu :: m -> m ->  m
  eta :: () -> m

instance Pfunctor.Monoid (Pfunctor x x) where
  eta () = Pfunctor (\x -> Product x)
  mu f g = Pfunctor (\x -> runPfunctor (f Pfunctor.. g) x) 
  
mu' :: Pfunctor n n -> Pfunctor n n
mu' f = mu f f

getResult f (x,y)
  | a == b = Just a
  | otherwise = Nothing
  where
    a = runPfunctor (mu' f) (x*y)
    b = runPfunctor f (x*y)

modular :: (Integral y) => y -> Pfunctor y y
modular n = Pfunctor (\x -> Product (mod x n))

absolute :: Pfunctor Integer Integer
absolute = Pfunctor (\x -> Product (abs x))