Help us understand the problem. What is going on with this article?

somehow-morphisms on fixed point written in Haskell

なんとかもるふぃずむ written in Haskell

λx.x K S K @ はてな - なんとかモルフィズムのHaskell版.

各もるふぃずむの概説はほとんど The Hitchhiker's Guide to MorphismsRecursion Schemes: A Field Guide (Redux) によるものをベースにしています.

現時点では未完成です.1

畳み込み(fold)系

catamorphism

anamorphismの双対.2
構造帰納法にあたります.
F代数つまりf a -> aなる関数による畳み込み計算を繰り返し適用します.

可換図式

実装コード

cata.hs
cata :: Functor f => (f a -> a) -> Fix f -> a
cata phi = phi . fmap (cata phi) . out

paramorphism

apomorphismの双対.
catamorphismが構造帰納法ならこちらは原始帰納法です.
タプリング法(Tupling-Trick)とも.
catamorphismと違って畳み込みの最中に全部分木にアクセスできます.
zygomorphismの補助関数に始代数つまりInを使ったらこいつになります.
つまり para = zygo In です.

可換図式

実装コード

para.hs
para :: Functor f => (f (Fix f, t) -> t) -> Fix f -> t
para phi = phi . fmap (pair (id, para phi)) . out

histomorphism

futumorphismの双対.
全ての部分構造においてそれ以前の全計算が使えます.
paramorphismと違って部分計算はすでに計算済みの状態で利用可能です.
逆に言えばparamorphismは再計算されます.
二種類の図式が書けるのでその両方の実装を紹介します.

Hisx

Histx.hs
data Hisx f a x = Hisx (a, f x)
newtype Cofree f a = Cf { unCf :: Fix (Hisx f a) }

台関手fがあったとしてf xという代数にaをadd-onしたような関手がHisx f aです.
Cofree f aは見ての通りその不動点に対して付けられた別名なので,その始代数つまり帰納的な型だと思えば良く,直感的には台関手で表示される型の各ノードに情報を付加したような型と見れば良さそうです.3

可換図式(その1)

実装コード(その1)

histo.hs
histo :: Functor f => (f (Cofree f t) -> t) -> Fix f -> t
histo phi = phi . fmap u . out
  where
    -- Cf and Hisx cast newtype
    u = Cf . ana (Hisx . pair (histo phi, out))

可換図式(その2)

alternativeな実装です.

実装コード(その2)

alternativeな実装です.

histo.hs
histo :: Functor f => (f (Cofree f t) -> t) -> Fix f -> t
histo phi = extract . cata ap
  where
    ap = cast . Hisx . pair (phi, id)
    cast :: Functor f => Hisx f a (Cofree f a) -> Cofree f a
    cast = Cf . In . bimap (id, unCf)

zygomorphism

cozygomorphismの双対.
paramorphismの一般化です.
補助関数を使って疊み込みします.

可換図式

実装コード

zygo.hs
zygo :: Functor f => (f a -> a) -> (f (a, b) -> b) -> Fix f -> b
zygo f phi = snd . cata (pair (f . fmap fst, phi))

cascade(a.k.a. supermap)

iterateの双対.
Bird先生はsupermapと呼んでる.

可換図式(その1)

実装コード(その1)

cascade.hs
cascade :: (Bifunctor f, Functor (f a)) => (a -> a) -> Fix (f a) -> Fix (f a)
cascade f = In . cata (bimap (id, map f . In))

可換図式(その2)

Alternativeな実装です.

実装コード(その2)

cascade.hs
cascade :: (Bifunctor f, Functor (f a)) => (a -> a) -> Fix (f a) -> Fix (f a)
cascade f = In . bimap (id, cascade f . map f) . out

prepromorphism

postpromorphismの双対.
基本的にはcatamorphismなんだけど,F代数によって潰される前に自然変換が適用されます.
都度前処理(preprocess)による書き換えを行っているものと見做せます.
この拡張は他の畳み込み系のmorphismと合成できます.

可換図式

実装コード

prepromorphismでは自然変換が登場します.4

natural.hs
type f :~> g = forall a. f a -> g a
prepro.hs
prepro :: Functor f => (f :~> f) -> (f a -> a) -> Fix f -> a
prepro h alg = alg . fmap (prepro h alg . cata (In . h)) . out

展開(unfold)系

anamorphism

catamorphism の双対.
種からはじめてF余代数つまりa -> f aなる関数による展開を繰り返し適用します.

可換図式

実装コード

ana.hs
ana :: Functor f => (a -> f a) -> a -> Fix f
ana psi = In . fmap (ana psi) . psi

apomorphism

paramorphismの双対.
余タプリング法(Co-Tupling-Trick)とも.
anamorphismと違ってその時点のものだけでなく全部分木を返すことも可能にしています.
cozygomorphismの補助関数に終余代数つまりoutを使ったらこいつになります.
つまり apo = cozygo out です.

可換図式

実装コード

apo.hs
apo :: Functor f => (t -> f (Either (Fix f) t)) -> t -> Fix f
apo psi = In . fmap (either (id, apo psi)) . psi

futumorphism

histomorphismの双対.
F余代数が複数の階層の値付けられた部分構造を一発で返せます.
apomorphismと違って,この部分構造は何回も使われる可能性があります.
histormophismと同様やはり二種類の図式が書けるので両方の実装を紹介します.

Futx

Futx.hs
data Futx f a x = Futx { unFutx :: (Either a (f x)) }
newtype Free f a = Fr { unFr :: Fix (Futx f a) }

台関手fがあったとしてf xという代数とaのいずれかとなるような関手がFutx f aです.
Free f aは見ての通りその不動点に対して付けられた別名なので,その終余代数つまり余帰納的な型だと思えば良いです.5

可換図式(その1)

実装コード(その1)

futu.hs
futu :: Functor f => (t -> f (Free f t)) -> t -> Fix f
futu psi = In . fmap u . psi
  where
    u = cata (either (futu psi, In) . unFutx) . unFr

可換図式(その2)

alternativeな実装です.

実装コード(その2)

futu.hs
futu :: Functor f => (t -> f (Free f t)) -> t -> Fix f
futu psi = ana ap . inject
  where
    ap = either (psi, id) . unFutx . cast
    cast :: Functor f => Free f t -> Futx f t (Free f t)
    cast = bimap (id, Fr) . out . unFr

cozygomorphism

zygomorphismの双対.
apomorphismの一般化です.
補助関数による展開をします.

可換図式

実装コード

cozygo.hs
cozygo :: Functor f => (a -> f a) -> (b -> f (Either a b)) -> b -> Fix f
cozygo f psi = ana (either (fmap Left . f, psi)) . Right

iterate

cascadeの双対

可換図式

[TODO]

実装コード

[TODO]

postpromorphism

prepromorphismの双対.
基本的にはanamorphismなんだけど,F余代数によって展開された後に自然変換が適用されます.
都度後処理(postprocess)による書き換えを行っているものと見做せます.
この拡張は他の展開系のmorphismと合成できます.

可換図式

実装コード

postpro.hs
postpro :: Functor f => (f :~> f) -> (a -> f a) -> a -> Fix f
postpro h coalg = In . fmap (ana (h . out) . postpro h coalg) . coalg

合成系

hylomorphism

metamorphismの双対.
anaしてからcataします.
中間構造を導入するという概念を実現します.
抽象構文木にしてからコンパイルするとかリストをなんらかの木にしてまたリストにすることでソートするとか.
hylomorphismには二種類の実装があるので両方紹介します.

可換図式

実装コード

hylo.hs
hylo :: Functor f => (f b -> b) -> (a -> f a) -> a -> b
hylo phi psi = phi . fmap (hylo phi psi) . psi

alternativeな実装です.

hylo.hs
hylo :: Functor f => (f b -> b) -> (a -> f a) -> a -> b
hylo phi psi = cata phi . ana psi

metamorphism

hylomorphismの双対.
cataしてからanaします.
hylomorphismで紹介した二種類の実装についてそれぞれ双対があるのでこれも両方紹介します.
それとは別にmetamorphismにはGibbons版とErwig版とがありますがここで紹介しているのはGibbons版にあたります.
Erwig版は双代数(Bialgebra)の言葉で表現されたhylomorphismだそうです.

可換図式

実装コード

meta.hs
meta :: Functor f => (f a -> a) -> (a -> f a) -> Fix f -> Fix f
meta phi psi = In . fmap (meta phi psi) . out

alternativeな実装です.

meta.hs
meta :: Functor f => (f a -> a) -> (a -> f a) -> Fix f -> Fix f
meta phi psi = ana psi . cata phi

chronomorphism

cochronomorphism双対.
futuしてからhistoです.

可換図式(その1)

実装コード(その1)

chrono.hs
chrono :: Functor f => (f (Cofree f b) -> b) -> (a -> f (Free f a)) -> a -> b
chrono phi psi = histo phi . futu psi

可換図式(その2)

alternativeな実装です.

実装コード(その2)

chrono.hs
chrono :: Functor f => (f (Cofree f b) -> b) -> (a -> f (Free f a)) -> a -> b
chrono phi psi = extract . hylo phi' psi' . inject
  where
    phi' = toCofree . Hisx . pair (phi, id)
    toCofree = Cf . In . bimap (id, unCf)
    psi' = either (psi, id) . unFutx . fromFree
    fromFree = bimap (id, Fr) . out . unFr

cochronomorphism

chronomorphism双対.
histoしてからfutuです.

可換図式(その1)

[TODO]

実装コード(その1)

cochrono.hs
cochrono :: Functor f => (f (Cofree f t) -> t) -> (t -> f (Free f t)) -> Fix t -> Fix t
cochrono phi psi = futu psi . histo phi

synchromorphism

[TODO]

可換図式

[TODO]

実装コード

[TODO]

dynamorphism

codynamorphismの双対.
動的計画法というやつです.

可換図式(その1)

[TODO]

実装コード(その1)

dyna.hs
dyna :: Functor f => (f (Cofree f b) -> b) -> (a -> f a) -> a -> b
dyna f g = chrono f (fmap inject . g)

可換図式(その2)

[TODO]

実装コード(その2)

dyna.hs
dyna :: Functor f => (f (Cofree f b) -> b) -> (a -> f a) -> a -> b
dyna f g = histo f . ana g

可換図式(その3)

[TODO]

実装コード(その3)

dyna.hs
dyna :: Functor f => (f (Cofree f b) -> b) -> (a -> f a) -> a -> b
dyna f g = extract . hylo ap g
  where
    ap a = Cf $ In $ Hisx (f a, fmap unCf a)

codynamorphism

dynamorphismの双対.

可換図式

[TODO]

実装コード

codyna.hs
codyna :: Functor f => (f b -> b) -> (a -> f (Free f a)) -> a -> b
codyna f g = chrono (f . fmap extract) g

exomorphism

[TODO]

可換図式(その1)

[TODO]

実装コード(その1)

exo.hs
exo :: Functor h =>
  (m b -> b, b -> n b) -> (h b -> m b) -> (h a -> h (g a)) -> (f a -> a, g a -> h a) -> g a -> b
exo c f g d = cata (fst c . f) . ana (g . snd d)

可換図式(その2)

alternativeな実装です.

[TODO]

実装コード(その2)

exo.hs
exo :: Functor h =>
  (m b -> b, b -> n b) -> (h b -> m b) -> (h a -> h (g a)) -> (f a -> a, g a -> h a) -> g a -> b
exo c f g d = hylo (fst c . f) (g . snd d)

mutumorphism

相互再帰だそうですが.
[TODO]

可換図式

実装コード

mutu.hs
mutu :: Functor f => (a -> b) -> (f a -> a) -> Fix f -> b
mutu proj phi = proj . cata phi

map(type functor)

なんとかもるふぃずむには数えないようですが型関手も仲間に入れてあげたい.
図式中のTと$\alpha$を合わせて始型(Initial Type)などと呼んだりします.

可換図式

実装コード

map.hs
map :: (Bifunctor f, Functor (f a)) => (a -> c) -> Fix (f a) -> Fix (f c)
map f = cata (In . bimap (f, id))

alternativeな実装.
双対を取ればよいです.

map.hs
map' :: (Functor (f c), Bifunctor f) => (a -> c) -> Fix (f a) -> Fix (f c)
map' f = ana (bimap (f, id) . out)

参考文献

  1. なんとかモルフィズム Ocaml版です.これに触発されてHaskellでこの記事を書きました.
  2. Haskellでも動的計画法がしたい 大変分かりやすい解説です.histoが理解できずにすがりました.
  3. The Hitchhiker's Guide to Morphisms チートシートです.
  4. category-extras ekmettさんによるhackageです.現時点での完全体といえばこれでしょうか.
  5. Recursion Schemes: A Field Guide (Redux) ekmettさんによるまとめ記事.
  6. Promorphisms, Pre and Post prepro/postproが分からなくてFokkingaの元論文では理解できなかったのですがりました.
  7. Ractical Recursion Schemes 基本となる再帰スキームを解説してます.Baseの解説がわかり易かった.
  8. Algebra of Programming Bird先生の古い名著.
  9. Law and Order in Algorithmics Fokkingaの元論文.
  10. 数学パズル ものまね鳥をまねる―愉快なパズルと結合子論理の夢の鳥物語 結合子論理のパズル本.
  11. 無限論の教室 ラノベ.
  12. 2013年 圏論勉強会資料(動画) @9_ties さんによる講義.初歩から解説してくれています.

脚注


  1. てか終わりとかないか. 

  2. 双対は分るよね.射を逆向きにしたときの対応する概念ね. 

  3. 例えば台関手をf x = 1 + xとすると,このF始代数は自然数型になりますが,a * (1 + x) => a + a * xとなるので,非空リストと同型になるはず. 

  4. fとgがFunctorであるというのが表れてないけどいいのかね.よかないか.なんとなくゆるい方向に逃げているんだと思う. 

  5. 例えばf x = 1 + xと取ると自然数の代数になりますが,aとして仮に終対象1を取れば1+Natつまり,Maybe Natと同型になるんじゃないかな多分  

Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away