1. rinse_

    Posted

    rinse_
Changes in title
+おじいさん、今日のご飯はAnamorphismですよ
Changes in tags
Changes in body
Source | HTML | Preview
@@ -0,0 +1,191 @@
+$\require{AMScd}$
+
+昨日のご飯 -> [おじいさん、今日のご飯はCatamorphismですよ](https://qiita.com/rinse_/items/878a962f92e675f21695)
+
+昨日のCatamorphismに引き続き、F余代数から出発して、Anamorphismを理解することを目指します。
+
+#F余代数
+ある関手Fに対して、対象と射の組 $(A, a : A \rightarrow F(A))$ のこと。名前の通り、F代数の双対。
+
+
+```math
+\begin{CD}
+A @>a>> F(A)
+\end{CD}
+```
+
+Haskellで書くと、
+
+```haskell
+type Coalgebra f a = a -> f a
+```
+
+## F余代数の準同型
+
+ある2つのF余代数 $(A, a)$, $(B, b)$ に対して、 $a \circ f = F(f) \circ b$ を満たす射 $f : B \rightarrow A$ のこと。
+可換図式を見ると、F代数の準同型の[それ](https://qiita.com/rinse_/items/878a962f92e675f21695#f代数の準同型)と比べて矢印の向きが全て反転していることがわかる。
+
+```math
+\begin{CD}
+F(A) @<a<< A \\
+@AF(f)AA @AfAA \\
+F(B) @<b<< B
+\end{CD}
+```
+
+## F終余代数
+任意のF余代数 $(X, \varphi)$ への準同型が一意に定まる特別なF余代数。F終余代数の対象を特に終対象と呼ぶ。
+ここで、$(T, t)$ がF終余代数であるならば、 $T \simeq F(T) $ ということが知られている[^1]。つまり、任意のF余代数 $(X, \varphi)$ に対して以下の可換図式が成り立つ。
+
+```math
+\begin{CD}
+F(T) @<t<< T \\
+@AF(f)AA @AfAA \\
+F(X) @<\varphi<< X
+\end{CD}
+```
+
+Haskellで書くと、
+
+```haskell
+newtype Fix f = InF { outF :: f (Fix f) }
+```
+
+`Fix f`が終対象$T$に, `outF`が可換図式の射 $t : T \rightarrow F(T)$ に相当する。`InF` は $t$ の逆射 $t^{-1} : F(T) \rightarrow T$ である。
+名前の由来は終対象 $T$ が関手 $F$ の最大不動点であることから。
+
+おや、この`Fix f`、[昨日のご飯](https://qiita.com/rinse_/items/878a962f92e675f21695)の献立に出てきた`Fix f`と全く同じものだ。
+
+```math
+\begin{CD}
+F(Fix(F)) \overset{inF}{\underset{outF}{\rightleftarrows}} Fix(F)
+\end{CD}
+```
+
+Haskellでは、ある関手 $F$ に対するF始対象とF終余対象は同じ型 `Fix f`で表すことができるのである。
+
+# Anamorphism
+
+上の可換図式で、射 $f$ は任意のF余代数 $(X, \varphi)$ からF終余代数への準同型である。これをAnamorphismと呼ぶ。
+関手 $F$ におけるF終余対象が関手 $F$の 不動点であることを強調するために、上図 $T$ を $Fix(F)$ に置き換えた図を示す。
+
+```math
+\begin{CD}
+F(Fix(F)) @<outF<< Fix(F) \\
+@AF(ana(\psi))AA @Aana(\psi)AA \\
+F(X) @<\psi<< X
+\end{CD}
+```
+
+Haskellで書くと、
+
+```Haskell
+ana :: Functor f => (a -> f a) -> a -> Fix f
+ana psy = InF . fmap (ana psy) . psy
+```
+
+可換図式の見方はcataのときと同様だ。Haskellの実装は、可換図式を左側からぐるっと回り込むようなイメージでされている。
+`inF`は $outF$ の逆射で、F終余代数の性質 $Fix(F) \simeq F(Fix(F)) $ より得られる。
+
+```math
+\begin{CD}
+ana(\psi) = X @>\psi>> F(X) @>F(ana(\psi))>> F(Fix(F)) @>inF>> Fix(F)
+\end{CD}
+```
+
+# プログラミングにおける意義
+
+Catamorphismはプログラミングにおける畳込み処理と対応していた。Anamorphismの場合はどうだろう。
+`Fix f`が何らかの再帰的構造を表していた(`Fix f = f (Fix f) = f (f (Fix f))`)ことを思い出すと、ある一つの*種* から再帰的な構造を作り出す何かだと想像できる。再帰的構造を一つの値に潰す`fold`は想像がつきやすいが、一つの値から再帰的構造を作るとは一体どういうことなのだろうか?
+
+これをリストに特殊化した関数がHaskellでは`unfoldr`として提供されている。`ana`とは似ても似つかない外見だ。
+
+```Haskell
+unfoldr :: (b -> Maybe (a, b)) -> b -> [a]
+```
+
+これを見ると、ある*種* `b`からある値`a`と次項のための種`b`を得ることを再帰的に繰り返し、得られた値全て`[a]`を返す関数のようだ。あまり見慣れない関数なので、使用例を見てみよう。
+
+```Haskell
+>>> iota :: Int -> Maybe (Int, Int)
+>>> iota n = Just $ (n, n + 1)
+>>> unfoldr iota 0
+[0,1,2,3,4,5,6,7,8,9,..]
+
+>>> fib :: (Int, Int) -> Maybe (Int, (Int, Int))
+>>> fib (m, n) = Just $ (m, (n, (m + n)))
+>>> unfoldr f (0, 1)
+[0,1,1,2,3,5,8,13,21,34,..]
+
+>>> fiz :: Int -> Maybe (String, Int)
+>>> fiz n
+>>> | n `mod` 15 == 0 = Just ("fizzbuzz", n + 1)
+>>> | n `mod` 3 == 0 = Just ("fizz", n + 1)
+>>> | n `mod` 5 == 0 = Just ("buzz", n + 1)
+>>> | otherwise = Just (show n, n + 1)
+unfoldr fiz 1
+["1","2","fizz","4","buzz","fizz","7","8","fizz","buzz","11","fizz","13","14","fizzbuzz",..]
+```
+
+一つ目は最もシンプルな例だ。種と値が共に`Int`で、初項`0`等差`1`の数列を作っている。
+二つ目は種がタプルになっているが、これは初項を2つ渡しているというだけの話だ。お馴染みフィボナッチ数列である。
+三つ目は値の方が`String`だが、やっていることは一つ目と同じだ。fizzbuzzの無限リストを作っている。
+
+少し`unfoldr`に慣れてきたところで、`ana`がこれとどう関係しているのかを確認してみよう。やり方は`cata`のときと同じだ。
+$ListF_X = 1 + X \times Y$ という関手の不動点 $Fix(ListF_X)$ は、$List(X)$ と同型である。よって、関手 $List_X$ におけるAnamorphismは`unfoldr`と本質的に同じであるはずだ。
+
+```Haskell
+-- ListFx = 1 + X * Y
+data ListF a b = Nil | Cons a b deriving (Functor)
+
+-- ListFで特殊化したana
+ana :: (b -> ListF a b) -> b -> Fix (ListF a)
+```
+
+もう一度`unfoldr`の型を確認しよう。
+
+```Haskell
+unfoldr :: (b -> Maybe (a, b)) -> b -> [a]
+```
+
+`cata`の時と同じように、`ana`の型を同型を使って変形していき、最終的に`unfoldr`の型が得られることを確認しよう。
+
+1. `Fix (ListF a) ~= [a]`
+まずは、$ListF_X$の不動点がリスト$List$と同型であるので、そこから置き換えていく。
+
+ ```Haskell
+ana :: (b -> ListF a b) -> b -> [a]
+```
+
+1. `ListF a b ~= Maybe (a, b)`
+$ListF_X = 1 + X \times Y$ だった。
+`(a, b)`が $X \times Y$ 、`Maybe a`が $1 + X$ と対応する。
+
+ ```Haskell
+ana :: (b -> Maybe (a, b)) -> b -> [a]
+```
+
+できた。
+
+# まとめ
+F余代数を学ぶところから出発して、任意のF余代数からF終余代数への準同型であるAnamorphismを学んだ。また、これをHaskell上に表現した`cata`やそれを特殊化した`unfoldr`を使うとうまく数列や漸化式を表すことができることを確認した。
+
+最後に、AnamorphismとCatamorphismの可換図式をくっつけてみよう。
+
+```math
+\begin{CD}
+F(X) @<\psi<< X \\
+@VF(ana(\psi))VV @Vana(\psi)VV \\
+F(Fix(F)) @<outF<< Fix(F) \\
+@| @| \\
+F(Fix(F)) @>inF>> Fix(F) \\
+@VF(cata(\varphi))VV @Vcata(\varphi)VV \\
+F(Y) @>\varphi>> Y
+\end{CD}
+```
+
+おや、$X \rightarrow Y$ という射が見えるぞ。これはいったい何morphismなんだ……?
+
+おじいさん、明日のご飯はhylomorphismですよ。
+
+[^1]: https://ncatlab.org/nlab/show/terminal+coalgebra+for+an+endofunctor