Catamorphism

結局11時頃起床.昨日走り過ぎた分の筋肉痛が痛い.昼間はちょっとした打ち合わせで,Ruby とか Rails とか書くことになるねー,という話し.まあネットワーク絡むプログラム全然わからんので,ちょうど良い機会だ.そのあとは久しぶりにずっと自分の数学とプログラムができた.いや,というかそろそろやらんとやばいのだが….

 F-代数の圏  \mathbf{Alg}(F) の initial object を  F-initial algebra という.んで,F-initial algebra から任意の F-代数への射を catamorphism という.この F-initial algebra が何者かよくわからなかったんだが,単なる  F の最小不動点で,その畳み込み (要するに foldr みたいなもの) が catamorphism なんだと.なるほど.例えば

例えば,Haskell

data Nat = Zero | Succ Nat

と書くと,Nat 型をつくれるけど,これって要するに  F(X) = \mathbf{1} + X という functor  Fの最小不動点  \mu F に Nat という名前をつけているわけなんだと.うむ,なるほど.Nat 型からの catamorphism ってよくわからんかったけど,動きをて計算してみると何となーく納得.c に f を n 回適用するみたいなやつね.

でも,肝心の多相型の catamorphism の圏論的な取り扱いがよくわかっていないのでもうちょっと勉強しないとダメ.ついでに終余代数と anamorphism も理解したい.それはともかく,終余代数って名前超かっこいいよね.