読者です 読者をやめる 読者になる 読者になる

bitterharvest’s diary

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

射は閉じている:どれだけ合成しても大丈夫

プログラマーのための圏論 (圏論とHaskell)

2.4 合成

1)圏の構成要素

ここでは、これから説明する合成も含めて、圏を構成する要素についてまとめておこう。圏は次の構成要素から成り立つ。
1) 対象\(A,B,C,..\)を有する。
2) 射\(f,g,h,..\)を有する
3) 射はドメインとコドメインを有する。なお、ドメイン、コドメインは対象である。例えば\(f: A \rightarrow B, g: B \rightarrow C, h: A \rightarrow C,..\)
4) すべての対象に対して恒等射が存在する。\(1_A: A \rightarrow A, 1_B: B \rightarrow B, 1_C: A \rightarrow C,..\)
5) コドメインドメインが一致している射は合成でき、それも射となる。\(f: A \rightarrow B\)で \(g: B \rightarrow C\)ならば、\(g \circ f : A \rightarrow \)が存在する。

なお、圏は次の二つの法則を満たさなければならない。
① 結合律:合成が複数あるとき、結果は、その計算の順序によらず、どれから計算しても同じである。即ち、\( (f \circ g) \circ h = f \circ (g \circ h) \)である。
② 単位律:恒等射とある射の合成は、ある射となる。即ち、\(f \circ 1_A = f = 1_B \circ f\)である。この法則があるため、恒等写像であっても、恒等射とはならないものがある。これについては後で述べる。

2)合成

今回の話題は、圏を構成する要素の中で、合成と呼ばれるものである。合成は、射と射とを結びつけるものである。

射のところで話をしたように、射は、ドメインとコドメインを有する。一つの射のコドメインと他の一つの射のドメインが同じ対象である時、この二つの射は合成できる。

例えば、射\(f:A \rightarrow B,g:B \rightarrow C\)があった時、射\(g \circ f : A \rightarrow C\)が存在する。この時、\( \circ \)を合成という。

いくつか例を挙げよう。

① 対象\(A\)を実数とし、対象\(B\)を整数とし、対象\(C\)を自然数(0から始まる)とし、射\(f:A \rightarrow B\)は小数点以下を四捨五入する関数であるとし、射\(g:B \rightarrow C\)は絶対値をとる関数とする。この時、射\(g \circ f : A \rightarrow C\)は、中心(0)からの整数値による距離(負の値はとらない)を表す。

② 少し変わった合成を定義してみよう。射は自然数(1から始まる)としよう。対象は星とし、すべての射のドメインであり、コドメインであるとする (星なので、対象はあまり意味を持たないと考えてよい)。即ち、任意の自然数\(i\)に対して、\(i : \star \rightarrow \star \) である。
f:id:bitterharvest:20161011123105p:plain

合成は、\(i \circ j : \star \rightarrow \star \)となる。そこで、合成\( \circ \)を乗算とみなしてみよう。即ち、\(i \circ j = i \times j\)とする。この時、合成された射は、これらの射を掛けたものと同じになる。例えば、射3と5の合成は射15と同じである。即ち、\(5 \circ 3 = 15\)である。すべての射は、星自身への射(恒等写像)であるが、単位律を満たすのは1だけなので、これらの射の中で、1だけが恒等射となる。

③ 射を0から始まる自然数とし、合成を加算とみなすと、合成された射は、これらの射を加えたものとなる。例えば、射3と5の合成は射8と同じである。上記と同様の理由で、これらの射の中で、0だけが恒等射となる。

④ 射を\(+n\),\(n\)は自然数(0から始まる)としよう。また、対象を自然数(0から始まる)とし、すべての射のドメインであり、コドメインであるとする。(図参照)射\(+m\)と\(+n\)の合成は\(+(m+n)\)となる。即ち、\(+m \circ +n = +(m+n)\)である。また、恒等射は\(+0\)である。

⑤ 同様に射\(*n\)を考えることができる。この時は、\(n\)は 1から始まる自然数である。この時、恒等射は\(+1\)である。

3)Haskellで実現する。

それでは、Haskellで実現しよう。①から始めよう。0から始まる自然数を必要とするが、これは、前の記事で説明したものを利用する。

data Nat0 = Zero | Succ Nat0 deriving (Read, Eq, Ord, Show)

toNat0 :: Int -> Nat0
toNat0 m
  | m == 0 = Zero
  | m > 0  = Succ $ toNat0 (m - 1)
  | otherwise = error "Not Natural Number"

fromNat0 :: Nat0 -> Int
fromNat0 Zero   = 0
fromNat0 (Succ n) = 1 + fromNat0 n

それでは、四捨五入する関数round’を定義しよう。Haskellにもroundという関数が用意されているが、この関数は、小数点の数が0.5の時、整数部が偶数のときは切り捨てを、奇数の時は切り上げをする。このため、四捨五入とはなっていないので、次のように定義する。

round' :: Double -> Int
round' m 
  | m >= 0 && m - fromIntegral (floor m) >= 0.5 = 1 + floor m
  | m >= 0 = floor m
  | m - fromIntegral (floor m) > 0.5 = 1 + floor m
  | otherwise = floor m

ここで、floorは小数点の切り捨てを行う。ただし、負の数の時は、整数部から1引いたものとなる。即ち、floor (-4.*)=-5である。では、round’を調べてみよう。

*Main> round' (-3.6)
-4
*Main> round' (-3.5)
-4
*Main> round' 3.6
4
*Main> round' 3.5
4
*Main> round' 3.4
3
*Main> round' 2.6
3
*Main> round' 2.5
3
*Main> round' 2.4
2
*Main> round' (-2.4)
-2
*Main> round' (-2.5)
-3
*Main> round' (-2.6)
-3
*Main> round' (-3.4)
-3
*Main> round' (-3.5)
-4
*Main> round' (-3.6)
-4

それでは、絶対値を求める関数を求めよう。整数を自然数に移すことに注意して、次のようにしよう。

abs' :: Int -> Nat0
abs' m
  | m >= 0 = toNat0 m
  | otherwise = toNat0 (-m)

大丈夫だと思うが、確認してみよう。

*Main> abs' 3
Succ (Succ (Succ Zero))
*Main> abs' 2
Succ (Succ Zero)
*Main> abs' 1
Succ Zero
*Main> abs' 0
Zero
*Main> abs' (-1)
Succ Zero
*Main> abs' (-2)
Succ (Succ Zero)
*Main> abs' (-3)
Succ (Succ (Succ Zero))

それでは、round’とabs’の合成関数distanceを次のように定義しよう。

distance = abs' . round'

少し動かしてみよう。

*Main> distance 3.6
Succ (Succ (Succ (Succ Zero)))
*Main> distance 3.5
Succ (Succ (Succ (Succ Zero)))
*Main> distance 3.4
Succ (Succ (Succ Zero))
*Main> distance 2.6
Succ (Succ (Succ Zero))
*Main> distance 2.5
Succ (Succ (Succ Zero))
*Main> distance 2.4
Succ (Succ Zero)
*Main> distance (-2.4)
Succ (Succ Zero)
*Main> distance (-2.5)
Succ (Succ (Succ Zero))
*Main> distance (-2.6)
Succ (Succ (Succ Zero))
*Main> distance (-3.4)
Succ (Succ (Succ Zero))
*Main> distance (-3.5)
Succ (Succ (Succ (Succ Zero)))
*Main> distance (-3.6)
Succ (Succ (Succ (Succ Zero)))

このままだとわかりにくいので、fromNat0を用いて、整数に変換してみてみよう。

*Main> fromNat0 . distance $ 3.6
4
*Main> fromNat0 . distance $ 3.5
4
*Main> fromNat0 . distance $ 3.4
3
*Main> fromNat0 . distance $ 2.6
3
*Main> fromNat0 . distance $ 2.5
3
*Main> fromNat0 . distance $ 2.4
2
*Main> fromNat0 . distance $ -2.4
2
*Main> fromNat0 . distance $ -2.5
3
*Main> fromNat0 . distance $ -2.6
3
*Main> fromNat0 . distance $ -3.4
3
*Main> fromNat0 . distance $ -3.5
4
*Main> fromNat0 . distance $ -3.6
4

次に、②と③は脇において、④について考えよう。④では、対象を自然数としていたが、ここでは数に変えてみよう(数には整数、有理数無理数などが含まれる。分かりにくければ、整数と考えてもここでは問題ない)。このように変えると、Haskellで用意している\(+n\)を用いることができる。

(+3)という関数は次のようになっている。さらに、この関数に4を入力する。結果は、4に3くわえられた値7が出力される。

*Main> :t (+3)
(+3) :: Num a => a -> a
*Main> :t (+3) 4
(+3) 4 :: Num a => a
*Main> (+3) 4
7

それでは、合成関数を作ってみよう。+3と+4を合成した関数に、値4を入力してみる。

*Main> (+3) . (+4) $ 4
11

いくつもの関数を合成してみよう。

*Main> (+1) . (+2) . (+3) . (+4) . (+5) $ 4
19

同じことが⑤にも言える。