bitterharvest’s diary

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

自然変換

8. 自然変換

圏論の話もそろそろ終わりに近づいてきた。これまでの話の中で重要であった話題は、圏そのものと、関手である。圏は計算の構造を示し、関手は構造を維持しての圏から圏への射を与えてくれる。今回は、この二つの概念に劣らないほどに重要な自然変換(Natural Transformation)の話をする。

8.1 自然変換の定義

自然変換は関手のイメージ間での射を定めるものである。今二つの圏\(\mathcal {C,D}\)を考えよう。二つの関手\(F,G\)が与えられたとする。図に示すように、\(F(A)\)は、\(F\)によって\(\mathcal {C}\)の対象\(A\)を写像した時のイメージとする。同様に、\(G(A)\)は\(G\)によるイメージとする。
f:id:bitterharvest:20170606092255p:plain

\(F(A)\)から\(F(B)\)への射を\(\alpha_A\)とする。

また、\(f\)は\(\mathcal {C}\)で\(A\)を対象\(B\)に移す射とする。この時、\(B\)は\(F\)により\(F(B)\)に、\(G\)により\(G(B)\)に移される。また、\(f\)は\(F\)により\(F(f)\)に、\(G\)により\(G(f)\)に移される。図で示すと以下のようになる。
f:id:bitterharvest:20170606092318p:plain

この時、圏\(\mathcal{D}\)の中に生じている\(F(A)\)から\(G(B)\)に至る四角形のグラフが、全ての\(A\)に対して可換(すなわち、\(\alpha_B \circ F(f) = G(f) \circ \alpha_A\)になっているとき、すぐ後に定義するが、自然変換であるという。

可換図のところをもう少し詳しく示すと以下のようになる。対象\(A\)内の要素\(x\)は図に示すように移される。
f:id:bitterharvest:20170606092331p:plain
なお、上の図で、\(F(B)\)はある対象の内部になることもあるので、\(\alpha_B\)は一意に定まらないことに注意してほしい。

それでは、自然変換についての定義をしておこう。
\(F,G\)が、二つの圏\(\mathcal{C,D}\)の間の関手であって、次の二つの条件1),2)を満たす時、\(F\)から\(G\)への自然変換\(\alpha\)は射(Morphisms)の族(Family)である。
1) 自然変換は、\(\mathcal{C}\)の全ての対象Aに対して、\(\mathcal{D}\)のある対象(複数の場合もある)に関連づける射\(\alpha_A\)が存在する。\(\alpha_A\)は\(A\)での\(\alpha\)の成分(Component)という。
2)全ての成分は\(\mathcal{C}\)の全ての射\(f:A \rightarrow B\)に対して、\(\alpha_B \circ F(f) = G(f) \circ \alpha_A\)でなくてはならない。

8.2 ポリモーフィズム

Haskellのプログラムでは、自然変換はポリモーフィズム(Polymorphism)を用いて記述される。ポリモーフィズムは日本語では多態性、多相性、多様性などと呼ばれるが、ここではポリモーフィズムと表すことにする。ポリモーフィズムプログラミング言語の型システムの性質を表すもので、プログラミング言語の各要素についてそれらが複数の型に属することを許す。Haskellでは、型変数を用いてポリモーフィズムは実現される。また、Haskellでは、自然変換の条件は自然に満たされるので、プログラミングするときに気を使う必要はない。

alpha :: F a -> G a
alpha . (fmap f) = (fmap f) . alpha

上記の定義で、\( alpha :: F \ a \rightarrow G \ a\)は\( alpha :: forall \ a . F \ a \rightarrow G \ a\)を表しているので、全ての型\(a\)に対して成り立つという意味である。即ち、図中の\(F(A) \rightarrow G(A)\)に対しても\(F(B) \rightarrow G(B)\)に対しても成り立つ(これにより、自然変換の条件1)は満足される)。
例を示そう。
リストの先頭を安全に出力する関数\(safeHead\)を定義しよう。\(safeHead\)を定義するためには、\(F\)をリストにする関手\([ ]\)に、\(G\)を関手\(Maybe\)として実現すればよいので下図のようになる。
f:id:bitterharvest:20170606092400p:plain
それでは、\(safeHead\)を定義してみよう。

safeHead :: [a] -> Maybe a
safeHead [] = Nothing
safeHead (x:xs) = Just x

それでは、自然変換の条件2)の\(\alpha_B \circ F(f) = g(f) \circ \alpha_A\)が満たされていることを確認しよう。まず、

safeHead [] = Nothing

について考える。この場合、以下が満たされることを示せばよい。

safeHead . ( fmap f) $ [ ] = fmap f $ Nothing

右辺の方は次のようになる。

safeHead . ( fmap f) $ [ ]
= safeHead $ fmap f [ ]
= safehead [ ]
= Nothing

左辺は次のようになる。

fmap f $ Nothing
= Nothing

従って、両辺は同じである。

safeHead (x:xs) = Just x

についても確認しよう。
この時は、以下が満たされることを示せばよい。

safeHead . (fmap f) $ (x:xs) = (fmap f) . safeHead $ (x:xs) 

右辺は

safeHead . (fmap f) $ (x:xs) 
= safeHead $ fmap f (x:xs) 
= safehead $ (f x: fmap f xs) 
= Just (f x)

左辺は

(fmap f) . safeHead $ (x:xs) 
= fmap f $ safeHead (x:xs) 
= fmap f $ Just x 
= Just (f x)

同じように、両辺は一致する。従って、自然変換の条件2)は満たされていることが分かる。

ついでに、この関数を利用して確認してみよう。\(f\)を\(length\)とした場合である。

*Main> safeHead . (fmap length) $ ["better", "bad", "ok"]
Just 6
*Main> (fmap length) . safeHead $ ["better", "bad", "ok"]
Just 6

\(f\)を\((+2)\)とした場合である。

*Main> safeHead . (fmap (+2)) $ [1,2,3,4]
Just 3
*Main> (fmap (+2)) . safeHead $ [1,2,3,4]
Just 3

別の例を示そう。関手が二つあって、\(Identity\)は自分自身に\([ ]\)はリストに移すものとする。図で示すと以下のようになる。

また、\(Identity \ a\)をリスト\([a ]\)に変換する関数を\(toList\)としよう。
f:id:bitterharvest:20170606092418p:plain

プログラムで表現すると以下のようになる。

data Identity a = Identity a deriving (Show, Read, Eq)

instance Functor Identity where
  fmap f (Identity a) = Identity (f a)

toList :: Identity a -> [a]
toList (Identity a) = [a]

下記が成り立っていることをプログラムで確認してみよう。

alpha :: F a -> G a
alpha . (fmap f) = (fmap f) . alpha

\(f\)に\((+3)\)と\(length\)を利用してみよう。

*Main> fmap (+3) (Identity 4)
Identity 7
*Main> Identity ((+3) 4)
Identity 7
*Main> fmap length (Identity "Tom")
Identity 3
*Main> Identity (length "Tom")
Identity 3

実行結果から右辺と左辺が一致していることが分かる。時間がある人は、一般的に\(f\)についても成り立つことを証明してほしい。