F-代数の具体例として見るList
型を見てみよう
code:haskell
cata :: Functor f => Algebra f a -> FixF f -> a
ここで重要なのは次の2点である
FixF f は、関手 f によって表現される再帰的構造そのもの
FixF f -> a という型は、再帰的構造から値 a に畳み込むことを表している
つまり、Catamorphismは、再帰的構造を、構造に対応した規則（Algebra）を使って、1つの値に潰す操作だと解釈できる これは、List に対する foldがやっていることを、任意の再帰的データ構造に拡張したものと考えることができる
ここでは、具体例としてListを考える
List には本質的に次の2つの操作がある
空リスト
code:_
nil : 1 → List A
要素を1つ追加する
code:_
cons : A × List A → List A
上記2つを見ると、定義の中にListが再帰的に現れてしまっており、このままでは再帰構造を一般化して扱うことができない
そこで、再帰を含めないように、List の1段分の形だけを取り出すと、次の関手で表せる
$ F(X) = 1 + A \times X
この関手をHaskellの型として書くと次のようになる
code:haskell
data ListF a r = Nil | Cons a r deriving Functor
$ 1がNilに対応
$ A × X がCons a rに対応
Xが再帰部分の穴としてrに対応
この時点では、ListF a rは再帰していない
Listは、この関手の不動点として定義できる
code:hs
newtype FixF f = InF { outF :: f (FixF f) }
次のように定義できる
code:haskell
type List a = FixF (ListF a)
これは再帰構造になっているので、例えば展開すると下記のようになる
code:haskell
List a
≅ FixF (ListF a)
= ListF a (FixF (ListF a))
= Nil | Cons a (FixF (ListF a))
= ...
= Nil | Cons a (Nil | Cons a (Nil | Cons a (...)))
これは 普通のリスト そのものである
ここで、List aは$ \mu Fに対応する
一般化されたcataはこうだった
code:haskell
cata :: Functor f => Algebra f b -> FixF f -> b
Listに特殊化する
code:haskell
cata :: Algebra (ListF a) b -> FixF (ListF a) -> b
この型は次のように解釈できる
Algebra (ListF a) b
Nil の場合どうするか
Cons a r の場合どうするか
それを使って FixF (ListF a) を b に畳み込む
よく知っているfoldrと型が異なるように見えるのはなぜか？
code:haskell
foldr :: (a -> b -> b) -> b -> a -> b これは下記のように同型変換すれば、一致することがわかる
Fix (ListF a) ≅ [a]なので、Fix (ListF a) -> b を[a] -> b に置き換えられる
code:haskell
cata :: Algebra (ListF a) b -> a -> b 代数 Algebra (ListF a) b は、「(Nil の値, Cons の関数)」と同型である
まず、Algebra (ListF a) bを展開すると、ListF a b -> bとなる
ListF a b の値は Nil か Cons a b のどちらかである
ListF a b -> bは、↑のそれぞれに対してbを返すので、次の2つの情報を持っているのと同じ
nilCase :: b
consCase :: a -> b -> b
従って、(ListF a b → b) ≅ (b, a → b → b)
code:haskell
cata :: (b, a -> b -> b) -> a -> b ペアの引数はカリー化できるので
code:haskell
cata :: (a -> b -> b) -> b -> a -> b これは ちょうど foldr の型と一致する
code:haskell
foldr :: (a -> b -> b) -> b -> a -> b