１３．２ 代数学から圏論へ
モノイドになれたところで、モノイドを代数学での定義から始めて圏論での定義へと段々に抽象化してみよう。丁度、プログラミングで、アセンブリ言語での記述から高級言語での記述に変えていくことに相当する。
１） 代数学での定義
代数学では、モノイドは単位元のある半群と定義される。半群が分からないとこの定義は何だかわからないが、次のように定義しなおすことができる。
[代数学でのモノイドの定義]
モノイドは次の二つの条件を満たすものである。なお、最初の条件を満たすものを半群という。
1) 集合を\(S\)とし、そのうえで定義されている二項演算子を\(\times\)とする。このとき、集合\(S\)の任意の元を\(x,y\)とした時、\(z=x \times y\)となる元\(z \in S\)が存在し、また、任意の元\(x',y',z' \in S\)に対して、結合律\((x'\times y') \times z'=x' \times (y' \times z')\)が成り立つ。
2) 単位元\(e \in S\)を有し、任意の元\(x \in S\)に対して単位律\(e \times x = x = x \times e\)が成り立つ。
[モノイドの例]
それでは、モノイドの例を挙げてみよう。
集合を\(S = \{1, 0, 2+\sqrt{3}, 2-\sqrt{3}\}\)とし、二項演算子を乗算とすると、この集合は1を単位元とするモノイドである。
数学で集合を用いることは、プログラミングでアセンブリ言語を用いることに相当する。ここから逃げ出したい。
２） 構成図での定義
圏論を学び始めると、モノイドの構成図が出てくる。最初は戸惑うのだが、集合の要素を射とし、二項演算子を射の合成としたものである。上の例は次のように表される。
これも、射の集合(Hom-Set)なので、やはり、集合から抜け出たい気分だ。
３） デカルト積での定義
デカルト積は二つの集合\(A,B\)のそれぞれから任意の元\(a \in A,b \in B\)を取り出す。\(a, b\)を元とする新たな集合\(A \times B\)を作り出す。即ち、
\begin{eqnarray}
A \times B = \{(a,b) | a \in A \land b \in B\}
\end{eqnarray}
である。
デカルト積を用いて、モノイドを定義しよう。ここでは、新たに、\(\mu\)とという関数を用いて定義し、少し抽象度を上げる。
[デカルト積を用いての定義]
1) 二項演算：任意の\( (x, y) \in S \times S\)に対して\(\mu (x,y) = z\)となるような\(z \in S\)が存在する。
2) 単位元：シングルトン集合(要素のない集合)\(\ () \)に対してとなる。なお、\(e\)は\(S\)での単位元である。
結合律：任意の元\( (x, y, z) \in S \times S\)に対して、\(\mu(\mu(x,y),z)=\mu(x, \mu(y,z))\)が成り立つ。
単位律：任意の元\(x \in S\)に対して\(e \times x = x = x \times e\)が成り立つ。
結合律に対して、可換図式を示すと以下のようになる。
上の図で、\((S \times S) \times S\)と\(S \times (S \times S)\)とが同値である時を強い結合律を満たすと言い、同型である時を弱い結合律を満たすという。従って、少なくとも、弱い結合律を満足するためには
\begin{eqnarray}
\alpha :: (S \times S) \times S \rightarrow S \times (S, S) \\
\alpha ( (x,y), z) = (x, (y,z) )
\end{eqnarray}
を満たさなければならない。
また、単位律に対しては、次のことを満たさなければならない。
\begin{eqnarray}
\lambda :: () \times S \rightarrow S \\
\lambda (\_, x) = x
\end{eqnarray}
\begin{eqnarray}
\rho :: S \times () \rightarrow S \\
\rho (x, \_) = x
\end{eqnarray}
それでは、この定義を実際にHaskellで実装してみよう。上記の定義を満たすようなクラスを\(Cartesian\)と名付け、次のように定義する。
class Cartesian m where mu :: (m, m) -> m eta :: () -> m
文字列
次に、文字列の集合を上記での\(S\)と考えて、クラス\(Cartesian\)のインスタンスを作ろう。文字列はHaskellでは\([a]\)と表すことができ、また、二項演算子は\(++\)で、単位元は\([]\)であるので、次のようになる。
instance Cartesian [a] where mu (x,y) = x ++ y eta () = []
実行してみよう。
*Main> mu ("A ", "dog") "A dog" *Main> mu (eta () , "a cat") "a cat" *Main> mu(" a pig", eta()) " a pig" *Main> mu ("A ", "dog") "A dog" *Main> mu (eta () , "a cat") "a cat" *Main> mu("a pig", eta()) "a pig"
乗算
それでは、乗算を利用できる数の集まりを\(Product'\)とし、次のように定義する。
newtype Product' n = Product' n deriving (Eq, Ord, Read, Show)
これに対して\(Cartesian\)のインスタンスを作ろう。二項演算子は乗算\( *\)で、単位元は1である。
instance Num n => Cartesian (Product' n) where mu (Product' x, Product' y) = Product' (x * y) eta () = Product' 1
実行してみよう。
*Main> mu (Product' 3.5, Product' 4.8) Product' 16.8 *Main> mu (Product' 4, eta ()) Product' 4 *Main> mu (eta (), Product' 7.5) Product' 7.5 *Main> mu (Product' 3, Product' 4) Product' 12
加算
次は、加算を利用できる数の集まりを\(Product'\)とし、次のように定義する。
newtype Sum' n = Sum' n deriving (Eq, Ord, Read, Show)
これに対して\(Cartesian\)のインスタンスを作ろう。二項演算子は加算\( +\)で、単位元は0である。
instance Num n => Cartesian (Sum' n) where mu (Sum' x, Sum' y) = Sum' (x + y) eta () = Sum' 0
実行してみよう。
*Main> mu (Product' 3, Product' 4) Product' 12 *Main> mu (Sum' 7.9, Sum' 4.3) Sum' 12.2 *Main> mu (Sum' 6, eta ()) Sum' 6 *Main> mu (eta(), Sum' 5.6) Sum' 5.6
余積
最後に、余積に対してもインスタンスを作ってみよう。余積も二項演算子には変わりはないが、インスタンスを作るには少し工夫がいる。余積はHaskellでは\(Either\)である。
instance (Cartesian a, Cartesian b) => Cartesian (Either a b) where mu (Right x, Right y) = Right $ mu (x, y) mu (Left x, Left y) = Left $ mu (x, y) mu (x@(Left _), _) = x mu (_, x@(Left _)) = x eta () = Right $ eta ()
実行してみよう。なお、実行に当たっては、出力のデータ型を指定しないと結果が得られないものがある。最初と最後の方の実行例にみられるが、これは\(Right\)あるいは\(Left\)のデータ型が確定しない場合に起こる。
*Main> mu (Right (Product' 3), Right (Product' 7)) :: Either String (Product' Int) Right (Product' 21) *Main> mu (Right (Product' 3.5), Right (Product' 7)) :: Either String (Product' Float) Right (Product' 24.5) *Main> mu (Left "Error1", Right (Product' 7)) Left "Error1" *Main> mu (Right (Product' 3.5), Left "Error2") Left "Error2" *Main> mu (Left "Error1", Left "Error2") :: Either String (Product' Int) Left "Error1Error2" *Main> mu (Right (Product' 11), eta ()) :: Either String (Product' Int) Right (Product' 11) *Main> mu (eta (), Right (Product' 13)) :: Either String (Product' Int) Right (Product' 13)
４） Haskellでの定義
前回の記事で、Haskellではモノイドは次のように定義した(但し、\(mconcat\)は省いても構わないので省略した)。
class Monoid m where mappend :: m -> m -> m mempty :: m
デカルト積を用いての定義は次のようになっていた。
class Cartesian m where mu :: (m, m) -> m eta :: () -> m
\(mu\)の型シグネチャ\((m, m) \rightarrow m\)は、カリー化を行えば、\(m \rightarrow m \rightarrow m\)となる。従って、\(mappend\)と\(mu\)は同じことを表していることが分かる。
さらに、は単位元を導き出す式であるので、\(mempty\)と同じである。これを用いると、前回の記事で示したHaskellでの定義は次のように置き換えることができる。
class Monoid m where mu :: m -> m -> m eta :: () -> m
但し、結合律と単位律は満足しなければならない。
書き換えたモノイドのインスタンスを示してみよう。
instance Monoid [a] where mu x y = x ++ y eta () = [] newtype Product n = Product n deriving (Eq, Ord, Read, Show) instance Num n => Monoid (Product n) where mu (Product x) (Product y) = Product (x * y) eta () = Product 1 newtype Sum n = Sum n deriving (Eq, Ord, Read, Show) instance Num n => Monoid (Sum n) where mu (Sum x) (Sum y) = Sum (x + y) eta () = Sum 0 instance Monoid a => Monoid (Maybe a) where mu Nothing x = x mu x Nothing = x mu (Just x) (Just y) = Just $ mu x y eta () = Nothing instance Monoid b => Monoid (Either a b) where mu (Right x) (Right y) = Right $ mu x y mu x@(Left _) _ = x mu _ x@(Left _) = x eta () = Right $ ita ()
上のプログラムで、()は、二項演算子が積である時は終対象であり、余積である時は始対象であることが分かる。これはたまたまそうなったのではなく、積と余積が双対関係にあることから、一般的にこのようになる。
