2015/07/11

カテゴリー : ,

関手, 自然変換とHaskell

$\require{AMScd}$ 最近, Mathjaxで遊んでいるので, それを使って, 関手と自然変換について調べたことのメモ.

関手とHaskellのFunctor


 関手$F$は圏$X$から$Y$へ対応を表し, 圏$X$の各関数$f : A \rightarrow B$を $F(f) : F(A) \rightarrow F(B)$ として移すものです. 関手は元の圏の関数について合成則を保存し, $f : A \rightarrow B, g : B \rightarrow C$,を関手$F$によって移すと, $F(f) \circ F(g) = F(f \circ g)$という性質を持ちます. また, 元の圏の各対象Xについて, 移した先の関手$F(id_X)$の射もその先の対象の$id$射となります.

 Haskellにおける関手$F$は, 名前も性質もmap関数に似ています.

class Functor a where
  mapf : (a -> b) -> f a -> f b

 mapfの実装として, リスト上のmap関数を考えると, 関手の合成則の保存が成立し, (map f) . (map g) = map (f . g)という規則が成立するはずですが, これは, プログラムの融合変換では一般にmap分配則と呼ばれるもので, 一般に成立します.

 つまり, ある型からなる圏〜リストへの関手とは, ただのリストのmap関数だということになります. 上記の定義では, 対象についての対応関係を考えていないように見えますが, 射$F(f)$が定義されれば, 自動的に対象同士の対応関係も定義されるということでしょう. というわけで, 任意の型Aのリスト/Map関数は, AからAのリストへの関手だということになります(太字部分, 2016/05/02追記修正).

 一般にmap関数は, リストだけのものでなく, 木構造へ応用できます. 例えば, 2分木について, 木構造の各要素に関数fを適用するmap関数は容易に想像できます.

data BTree a = Leaf a | Fork (BTree a) (BTree a) deriving Show

を考えることにして,

instance Functor BTree where
  fmap f (Leaf a) = Leaf (f a)
  fmap f (Fork a b) = Fork (fmap f a) (fmap f b)

 タプルのリストで, 二番目の要素のみへの関数適用を考えるなら,

data TList a b = Nil | Cons a b (TList a b)

instance Functor (TList a) where
  fmap f Nil = Nil
  fmap f (Cons a b rest) = Cons a (f b) (fmap f rest)

とすれば, Functorのインスタンスとして具体的な関数が実装でき, 関手が定義できる流れになります. 代数的データ型なら, (fmap f) $= F(f)$の対応について, 自由に考えることが可能です. 関手というと身構えてしまいますが, 関数型言語上では, 単なる高階関数として表されることがわかります.

自然変換とHaskell上の関数


 関手$F, G$における自然変換$\mu$は, 関手$F, G : X \rightarrow Y$について, $\mu \circ F(f) = G(f) \circ \mu$を成り立たせるもの. というわけで, 可換図式を考えると,
$$\begin{CD} F(A) @>{F(f)}>> F(B)\\ @V{\mu_A}VV @V{\mu_B}VV \\ G(A) @>{G(f)}>> G(B) \end{CD}$$
 となります(上図 : 2016/05/18修正). 前述の条件を満たしていることがわかります. 自然変換の概念は, 2つの関手$F, G : X \rightarrow Y$の移した先の対応$\mu : F \dot{\rightarrow} G$を定義するものですが, $\mu \circ F(f)$のルートと, $G(f) \circ \mu$のルートの結果(計算)を同一にするものと考えると, わかりやすいですね. ちなみに, 上記の可換図式の個々の$\mu_A , \mu_B$は, 別の射(関数)である場合もあり, 個々の射は, 自然変換のコンポーネントと呼ばれるそうです.

 問題は, この自然変換を表すプログラム上の関数とは何かということです. 調べたら, 以下に例がありました.

 Category theory/Natural transformation - Haskell Wiki

 前述のデータ型BTreeとリスト([])で書くとすれば, 自然変換 $\mu :$ (BTree a) $\rightarrow$ [a]の自然変換とは, 例えば,

flatten2List :: (BTree a) -> [a]
flatten2List (Leaf a) = [a]
flatten2List (Fork a b) = (flatten2List a) ++ (flatten2List b)

 になりそうです.
 可換図式の主張する合成規則$\mu \circ F(f) = G(f) \circ \mu$は,

((flatten2List . fmap f) = (map f . flatten2List)

 が成立するはず. あまりにシンプルですね. ただのキャストに相当する(?)何かになりました.

 さらに自然変換$\mu$には, 別の自然変換$\eta$との垂直合成$\eta \circ \mu$を考えることも可能です. 前述の可換図式に下にもうひとつ自然変換をくっつけた形で, 以下のようになります.
$$\begin{CD} F(A) @>{F(f)}>> F(B)\\ @V{\mu_A}VV @V{\mu_B}VV \\ G(A) @>{G(f)}>> G(B) \\ @V{\eta_A}VV @V{\eta_B}VV \\ H(A) @>{H(f)}>> H(B) \end{CD} $$

 関手fmapの実装として, Maybeについて考えると,

data Maybe x = Nothing | Just x deriving Show

instance Functor Maybe where
  fmap f Nothing = Nothing
  fmap f (Just x) = Just (f x)

と定義することができて, この時の自然変換$\eta : $[a]$ \rightarrow$ (Maybe a)を考えれば,

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

となると思います. この時の, $\eta \circ \mu$による自然変換の垂直合成は,

(list2Maybe . flatten2List)

となり, 可換図式を満たすなら,

((list2Maybe . flatten2List . fmap f)
= (list2Maybe . map f . flatten2List)
= (fmap f . list2Maybe . flatten2List)

となるはずです.

参考文献

0 件のコメント :

コメントを投稿