bitterharvest’s diary

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

Haskellで学ぶ圏論・入門編 写像を対象に (モノイド圏)

1.モノイド圏

四則演算や論理演算など、単位元を有し結合律を満たす二項演算はモノイドと呼ばれる。この圏は次のように構成される。
(1) 対象:一つ(通常★で表される)
(2) 射:二項演算子の左あるいは右に表れる数(あるいは元)
(3) ソースとターゲット:★
(4) 恒等射:\(id\)(通常は0または1)
(5) 合成:二項演算子そのもの
単位律と結合律に関する二つの条件は満たす。

例:整数の加算
構成
(1) 対象:★
(2) 射:\( i \in \mathbb{Z} \)
(3) ソースとターゲット:★
(4) 恒等射:0
(5) 合成:+
条件は以下のように満たしている。
(1) 単位律:任意の\( i \in \mathbb{Z} \)に対して\(i + 0 = 0 + i = i\)
(2) 結合律:任意の\( i,j,k \in \mathbb{Z} \)に対して\(i+(j+k)=(i+j)+k\)

f:id:bitterharvest:20150319072728p:plain

例:論理和
(1) 対象:★
(2) 射:\(True\), \(False\)
(3) ソースとターゲット:★
(4) 恒等射:\(False\)
(5) 合成:\( \cup \)
条件は以下のように満たしている。
(1) 単位律:任意の\( i \in \{True,False\} \)に対して\(i \cup False = False \cup i = i\)
(2) 結合律:任意の\( i,j,k \in \{True,False\} \)に対して\(i\cup (j\cup k)=(i\cup j)\cup k\)
f:id:bitterharvest:20150319072740p:plain

実数の乗算
(1) 対象:★
(2) 射:\( r \in \mathbb{R} \)
(3) ソースとターゲット:★
(4) 恒等射:1.0
(5) 合成:\( \times \)
条件は以下のように満たしている。
(1) 単位律:任意の\( i \in \mathbb{R} \)に対して\(i \times 1.0 = 1.0 \times i = i\)
(2) 結合律:任意の\( i,j,k \in \mathbb{Z} \)に対して\(i\times (j\times k)=(i\times j)\times k\)
f:id:bitterharvest:20150319072752p:plain

2.モノイド間の写像を考える

集合圏を考えるときに、集合から集合への写像を考えた。これと同じように、モノイドからモノイドへの写像を考えることもできる。

例1:(0で始まる)自然数での加算から整数での乗算への写像\(f\)を考える。この時、恒等射は恒等射に移すこととする(自然数の0は整数の1に写像する)。写像\(f\)は何種類あるだろうか?
恒等射は恒等射に移すので\(f(0)=1\)である。
今、\(f(1)= a\)とする。この関数を\(f_a\)とする。この時、\(f_a(n=1+1+…+1) = a \times a \times...\times a = a^n\)となる。
このことから、\(f(1)\)を定めれば、任意の\(n\)に対して\(f(n)\)が定まる。\(f(1)\)が取りえる値は\(\mathbb{Z}\)であるので、写像\(f\)は整数の数だけ存在することとなる。
即ち、自然数での加算から整数での乗算への写像は\(f_{a \in \mathbb{Z}}\)となる。
下図は、\(f_2\)の例である。
f:id:bitterharvest:20150319072809p:plain

例1を圏として表すと次のようになる。ここでは、自然数の加算での射の集まり\(\mathbb{N}\)と、整数での乗算での射の集まり\(\mathbb{Z}\)とを対象として、これら対象間の写像\(f_{a \in \mathbb{Z}}\)を射として表す。
(1) 対象:\(\mathbb{N}=\{i \in \mathbb{N}:\)★\(_1\rightarrow\)★\(_1\}\), \(\mathbb{Z}=\{j \in \mathbb{Z}:\)★\(_2\rightarrow\)★\(_2\}\)
(2) 射:\(f_{a \in \mathbb{Z}}\)
(3) ソースとターゲット:ソースは\(\mathbb{N}\)、ターゲットは\(\mathbb{Z}\)
(4) 恒等射:\(id : 0 \rightarrow 1\)
(5) 合成:
なお、二つの条件が満たされていることを確認して欲しい。

例2:(0で始まる)自然数での加算から論理和への写像\(f\)を考える。
恒等射は恒等射に移すこととする(自然数の0は論理の\(False\)に写像する)。
先ほどと同様に\(f(1)\)の写像を考える。\(f(1)\)を\(True\)に移すと、\(f(n=1+1+…+1) = True \cup True \cup...\cup True = True\)となる。この関数を\(f_{True}\)とする(プログラミング言語Cでは、0を偽、それ以外を真としているが、この関係によく似ている)。
f:id:bitterharvest:20150319091829p:plain
逆に、\(f(1)\)を\(False\)に移すと、\(f(n=1+1+…+1) = False \cup False \cup...\cup False = False\)となり、偽一色の世界となる。この関数を\(f_{False}\)とする。
自然数での加算から論理和への写像は\(f_{True}\), \(f_{False}\)の二つであることが分かる。

これを圏で表すと次のようになる。
(1) 対象:\(\mathbb{N}=\{i \in \mathbb{N}:\)★\(_1\rightarrow\)★\(_1\}\), \(L=\{False,True:\)★\(_2\rightarrow\)★\(_2\}\)
(2) 射:\(f_{True}\), \(f_{False}\)
(3) ソースとターゲット:ソースは\(\mathbb{N}\)、ターゲットは\(L\)
(4) 恒等射:\(id : 0 \rightarrow False\)
(5) 合成:
なお、二つの条件が満たされていることを確認して欲しい。

例3: 例2は2進数への変換と予想した向きもあるかと思うが、そうはならなかった。次は2進数になる例である。(0で始まる)自然数での加算から2進数の演算(ここでは\( \oplus\)とする。すなわち、\( 0 \oplus 0 = 0, 0 \oplus 1 = 1, 1 \oplus 0 = 1, 1 \oplus 1 = 0 \)とする)への写像\(g\)を考える。
恒等射は恒等射に移すこととする(自然数の0を2進数の演算での0に写像する)。
先ほどと同様に\(g(1)\)の写像を考える。\(g(1)\)を\(1\)に移すと、\(g(n) \)は\(n\)が偶数のとき0となり、奇数の時1となる。この関数を\(g_1\)とする。
f:id:bitterharvest:20150319101946p:plain
逆に、\(g(1)\)を\(0\)に移すと、\(g(n=1+1+…+1) = 0 \oplus 0 \oplus...\oplus 0 = 0\)となる。
自然数での加算から2進数の演算への写像は\(g_0\), \(g_1\)の二つであることが分かる。

これを圏で表すと次のようになる。
(1) 対象:\(\mathbb{N}=\{i \in \mathbb{N}:\)★\(_1\rightarrow\)★\(_1\}\), \(B=\{0, 1:\)★\(_2\rightarrow\)★\(_2\}\)
(2) 射:\(g_0\), \(g_1\)
(3) ソースとターゲット:スースは\(\mathbb{N}\)、ターゲットは\(B\)
(4) 恒等射:\(id : 0 \rightarrow 0\)
(5) 合成:
なお、二つの条件が満たされていることを確認して欲しい。

3.Haskellでの実現

それでは、二つのモノイドを一つの圏にした例をHasekllで実現する。

ここでは、10進数を2進数に変換する場合を考える。
10進数の方は、数字ではなく、zero, one, two, three..のように表されているとする。また、2進数の方はodd, evenで表されているとする。
このため、10進数のモノイドは、射がzero, one, two, three..であり、2進数のモノイドは、射がodd, evenである。関数の合成がそれぞれの進数の規則に従って定められているとする。例えば、
zero + zero = zero
zero + one = one
one + zero = one
one + one = two
one + one + one = three
...
one + one + one + one + one + one + one + one + one + one = zero

even \(\oplus\) even = even
even \(\oplus\) odd = odd
odd \(\oplus\) even = odd
odd \(\oplus\) odd = even
である。

そこで、この二つのモノイドを一つの圏にまとめ、それぞれの射を対象にし、二つのモノイド間の写像を射とした圏(下図)は次のようにHaskellで表すことが可能である。
f:id:bitterharvest:20150320064835p:plain

module Monoid where

import Data.Map (Map)
import qualified Data.Map as Map
import Data.Set (Set)
import qualified Data.Set as Set


data SetStar1 = Star1      deriving (Show, Eq, Ord)
data SetStar2 = Star2      deriving (Show, Eq, Ord)

zero  = Map.fromList([(Star1, Star1)])
one   = Map.fromList([(Star1, Star1)])
two   = Map.fromList([(Star1, Star1)])
three = Map.fromList([(Star1, Star1)]) 
four  = Map.fromList([(Star1, Star1)])
five  = Map.fromList([(Star1, Star1)])
six   = Map.fromList([(Star1, Star1)])
seven = Map.fromList([(Star1, Star1)])
eight = Map.fromList([(Star1, Star1)])
nine  = Map.fromList([(Star1, Star1)])
homN  = Set.fromList[one,two,three,four,five,six,seven,eight,nine]

even'  = Map.fromList([(Star2, Star2)])
odd'   = Map.fromList([(Star2, Star2)])
homB  = Set.fromList[even', odd']

phi1  = Map.fromList([(zero, even'),(one, odd'),(two, even'),(three, odd'),(four, even'),(five, odd'),(six, even'),(seven, odd'),(eight, even'),(nine, odd')])
phi2  = Map.fromList([(zero, even'),(one, even'),(two, even'),(three, even'),(four, even'),(five, even'),(six, even'),(seven, even'),(eight, even'),(nine, even')])

class Morph f where
  morph :: Ord a => a -> f a b -> Maybe b

instance Morph Map where
  morph = Map.lookup 

実行例を示す。あまり面白くないのだが、関数oneがphi1によって写像された先を求めると次のようになる。

*Monoid> morph one phi1
Just (fromList [(Star2,Star2)])