bitterharvest’s diary

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

Haskellで学ぶ圏論・ウォームアップ編 モノイドと二項演算子

1.モノイド圏の定義

前の記事でカリー化関数との関連の中でモノイドを説明した。モノイドは、二項演算子(中置演算子)を抽象化した概念で、対象が一つの圏である。そして、関数の合成を二項演算子とみなすことで、四則演算や、\(min\)や\(max\)などはモナイド圏の仲間となる。

一般的に、圏は次のように定義されている。圏は5つの要素と二つの条件により構成される。5つの要素は次のようになっている。

(1) 対象
圏は対象を有する。対象は、通常は大文字を用いて、\(A,B,C,..\)と表す(対象は多くの場合何かの集まりである。例えば、集合などが対象になる。しかし、集合の要素はこの場合対象とはいわない)。

(2) 射
圏は対象(複数の場合も可)から対象(こちらも複数の場合可)へ移すを有する。射は、通常小文字を用いて、\(f,g,h,..\)と表す(これまで習ってきた関数は射となるが、射となるのは関数だけではない。これから説明するモノイドの場合はこれまでの関数とは異なる)。

(3) ドメインとコドメイン
射の出発(入力)側の対象をドメインといい、到着(出力)側の対象をドメインという。

(4) 恒等射
射は恒等射\(id\)を有する。恒等射は自分から自分へ移す射である。

(5) 合成
任意の二つの射に対して、合成\(\circ\)が可能である。二つの射を\(f,g\)とした時、その合成は\(g \circ f\)と表す。この時、\(f\)のコドメインと\(g\)のドメインは同一である。

二つの条件は次の通りである。
(1) 恒等射は、ある射のドメインで適応したとしても、その射のコドメインで適応したとしても、変化を与えない。\(f: A \rightarrow B\)を任意の射とし、対象\(A\)での恒等射を\(id_A\)とし、対象\(B\)での恒等射を\(id_B\)としたとき、\(f \circ id_A = f = id_B \circ f\)である。

(2) 射では結合律が成り立つ。即ち、合成できる三つの射\(f,g,h\)において、\((h \circ g) \circ f = h \circ (g \circ f)\)である。

モノイド圏は、対象を一つだけ有する圏である。対象を★で表すと、射は次の図のようになる。
f:id:bitterharvest:20150215071919p:plain

あるいは次のように表すこともできる。
f:id:bitterharvest:20150211173231p:plain

2.モノイド圏の例:整数の加算

整数の加算は、射を整数の集合\(\mathbb{Z}\)、恒等射を\(0\)、合成\(\circ\)を\(+\)としたものである。図で表すと以下のようになる。なお、圏の二つの条件も満たされていることに注意してほしい。
f:id:bitterharvest:20150211173835p:plain

整数の減算は、射を整数の集合\(\mathbb{Z}\)、恒等射を\(0\)、合成\(\circ\)を\(-\)としたものになる。

整数の乗算は、射を整数の集合\(\mathbb{Z}\)、恒等射を\(1\)、合成\(\circ\)を\(*\)としたものになる。

同様に、自然数\(\mathbb{N}\)、有理数\(\mathbb{Q}\)、実数\(\mathbb{R}\)、複素数\(\mathbb{C}\)の加算、減算、乗算についてもモノイド圏で表すことができる。

除算の場合は、整数で割ったときは有理数\(\mathbb{Q}\)となる。従って、有理数の除算は、射を有理数の集合\(\mathbb{Q}\)、恒等射を\(1\)、合成\(\circ\)を\(/\)としたものになる。ただし、正の数を\(0\)で割ったときは\(\infty\)、負の数を\(0\)で割ったときは\(-\infty\)とする。

同様に、実数\(\mathbb{R}\)、複素数\(\mathbb{C}\)の除算についてもモノイド圏で表すことができる。

なお、上記のものは、いずれも圏の二つの条件も満たしていることに注意してほしい。

Haskellでのいくつかの例を示す。

Prelude> 4 + 2 + 7
13
Prelude> 8 - 4 - 2 - 5
-3
Prelude> 3 * 2 * 5 * 6 
180
Prelude> 5 / 4 / 2 / 6
0.10416666666666667

3.モノイド圏の例:\(min\)

二つの数\(a,b\)を比較して、小さい方の数を教えてくれる関数\(min \ a \ b\)を考える。関数名を中置演算子と考えて、\(a \ min \ b\)と書き改めると、\(min\)が四則演算などの二項演算子と変わらないことが分かる。

そこで、二つの整数を比較し、その小さい方の数を与える\(min\)は次のようにモノイド圏として表すことができる。

整数同士の\(min\)は、射を整数の集合\(\mathbb{Z}\)、恒等射を\(\infty\)、合成\(\circ\)を\(min\)としたものである。図で表すと次のようになる。
f:id:bitterharvest:20150215075503p:plain

二つの数\(a,b\)を比較して、大きい方の数を教えてくれる関数\(a \ max \ b\)も同様に、
整数同士の\(max\)は、射を整数の集合\(\mathbb{Z}\)、恒等射を\(-\infty\)、合成\(\circ\)を\(max\)としたものである。

同様に、自然数\(\mathbb{N}\)、有理数\(\mathbb{Q}\)、実数\(\mathbb{R}\)、無理数\(\mathbb{C}\)の\(min\)と\(max\)についてもモノイド圏で表すことができる。

なお、上記のものは、いずれも圏の二つの条件を満たしていることに注意してほしい。

Haskellでは中置演算子にする時は関数を`で囲む必要がある。これに注意して例を示すと次のようになる。

Prelude> 5 `min` 2 `min` 4 `min` 7
2
Prelude> 5 `min` 2 `min` 4 `min` 7 `min` (-5)
-5

4.モノイド圏の例:文字列

これまでは数を扱ってきたが、今度は文字列を考えてみる。二つの文字列は連結したとしても文字列であるので、二項演算子の場合と同様に扱えると考えられる。そこで、文字列の連結を圏での結合と考えると、文字列の連結は次のようなモノイド圏となる。

文字列の連結は、射を文字列の集合\(String\)、恒等射を空の文字列\([ ]\)、合成\(\circ\)を\(++\)としたものである(圏の二つの条件は満たしている)。図で表すと次のようになる。
f:id:bitterharvest:20150215084314p:plain

Haskellでのいくつかの例を示す。

Prelude> "hard" ++ "work" 
"hardwork"
Prelude> [] ++ "work" 
"work"
Prelude> "work" ++ [] 
"work"

5.Haskellでのモノイド

Haskellでは、Data.Monoidでモノイドを定義している。次のようになっている。

class Monoid a where
  mempty :: a
  mappend :: a -> a -> a
  mconcat :: [a] -> a

四則演算、\(min,max\)、文字列のモノイド圏を定義するときに、射、恒等射、合成を与えたが、上記のaが射、memptyが恒等射、mappendが合成である。また、mconcatは射と合成で表されたもの(例えば、3+5+2+7+1)に対して、それらを計算して合成のない射だけで表す。mconcatはfoldr mappend memptyと定義されている。

モノイドのインスタンスを定義するときは、mempty, mapend, mconcatを指定すればよい。mconcatはこれらから自然に定義されるので、通常は、インスタンスで定義する必要はない。

Data.Monoidでは、リスト、和、積、Maybeなどのインスタンスを用意している。

instance Monoid [a] -- Defined in ‘Data.Monoid’
instance Num a => Monoid (Sum a) -- Defined in ‘Data.Monoid’
instance Num a => Monoid (Product a) -- Defined in ‘Data.Monoid’
instance Monoid Ordering -- Defined in ‘Data.Monoid’
instance Monoid a => Monoid (Maybe a) -- Defined in ‘Data.Monoid’
instance Monoid (Last a) -- Defined in ‘Data.Monoid’
instance Monoid (First a) -- Defined in ‘Data.Monoid’
instance Monoid (Endo a) -- Defined in ‘Data.Monoid’
instance Monoid a => Monoid (Dual a) -- Defined in ‘Data.Monoid’
instance Monoid Any -- Defined in ‘Data.Monoid’
instance Monoid All -- Defined in ‘Data.Monoid’
instance Monoid b => Monoid (a -> b) -- Defined in ‘Data.Monoid’
instance (Monoid a, Monoid b, Monoid c, Monoid d, Monoid e) => Monoid (a, b, c, d, e) -- Defined in ‘Data.Monoid’
instance (Monoid a, Monoid b, Monoid c, Monoid d) => Monoid (a, b, c, d) -- Defined in ‘Data.Monoid’
instance (Monoid a, Monoid b, Monoid c) => Monoid (a, b, c) -- Defined in ‘Data.Monoid’
instance (Monoid a, Monoid b) => Monoid (a, b) -- Defined in ‘Data.Monoid’
instance Monoid () -- Defined in ‘Data.Monoid’

沢山のものが用意されているので、これらを使えば多くの場合は間に合うが、自分でも作成することができる。
例えば、整数の加算のモノイドを作成したければ、次のようにする。

module IntegerAdd where

import Data.Monoid

newtype IntegerAdd a = IntegerAdd { getIntegerAdd :: a } deriving (Eq, Ord, Read, Show, Bounded) 

instance Integral a => Monoid (IntegerAdd a) where
  mempty = IntegerAdd 0
  IntegerAdd x `mappend`  IntegerAdd y = IntegerAdd (x + y)

実行結果は以下のようになる。

*IntegerAdd Data.Monoid> getIntegerAdd $ IntegerAdd 3 `mappend` IntegerAdd 4
7
*IntegerAdd Data.Monoid> getIntegerAdd $ IntegerAdd 3 `mappend` IntegerAdd 4 `mappend` IntegerAdd 7
14

例えば、整数の乗算のモノイドを作成したければ、次のようにする。

module RealMultiply where

import Data.Monoid

newtype RealMultiply a = RealMultiply { getRealMultiply :: a } deriving (Eq, Ord, Read, Show, Bounded) 

instance Real a => Monoid (RealMultiply a) where
  mempty = RealMultiply 1
  RealMultiply x `mappend`  RealMultiply y = RealMultiply (x * y)

実行結果は以下のようになる。

*RealMultiply Data.Monoid> getRealMultiply $ RealMultiply 3.5 `mappend` RealMultiply 6.3
22.05

また、整数、有理数、実数などを定めずに、実行時に型推論で決められるようにするためには、RealのところをNumに変えればよい。

module Multiply where

import Data.Monoid

newtype Multiply a = Multiply { getMultiply :: a } deriving (Eq, Ord, Read, Show, Bounded) 

instance Num a => Monoid (Multiply a) where
  mempty = Multiply 1
  Multiply x `mappend`  Multiply y = Multiply (x * y)

実行結果は次のようになる。

*Multiply Data.Monoid> getMultiply $ Multiply 3.5 `mappend` Multiply 6.3
22.05
*Multiply Data.Monoid> getMultiply $ Multiply 3 `mappend` Multiply 6
18
*Multiply Data.Monoid> getMultiply $ Multiply 3 `mappend` Multiply 6  `mappend` Multiply 8
144
*Multiply Data.Monoid> getMultiply $ Multiply 3.5 `mappend` Multiply 6.3  `mappend` Multiply 8
176.4