おじいさん、今日のご飯はHylomorphismですよ

• 前のご飯
  • おじいさん、今日のご飯はCatamorphismですよ
  • おじいさん、今日のご飯はAnamorphismですよ

Hylomorphism

下はCatamorphismとAnamorphismの可換図式をくっつけたもの。

\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}

右側に、$Catamorphism \circ Anamorphism : X \rightarrow Y$ という射が見える。これをHylomorphismと呼ぶ。

Haskellで書くと、

newtype Fix f = InF { outF :: f (Fix f) }

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

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

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

型を見る限りは、Anamorphismで種 から再帰的構造を展開し、さらにそれをCatamorphismで一つの値に畳み込む関数だと解釈できる。しかしこれはプログラミングにおいては一体どんな意味を持つものなのだろう。

Hylomorphismのプログラミングにおける利用

展開し畳み込むとはどういうことだろう。畳み込む必要があることから、展開される構造は有限の長さの構造を持つ必要があることが分かる。さもなくば、それは停止しない再帰関数に相当するものになる。
与えられた整数から0までを下る数列を作るような関数decと、それを畳み込むいくつかの関数を作ってみた。

-- Fix (ListF a) ~= [a]
data ListF a b = NilF | ConsF a b deriving (Functor)

dec :: Int -> ListF Int Int
dec 0 = NilF
dec n = ConsF n (n - 1)

sumA :: ListF Int Int -> Int
sumA NilF        = 0
sumA (ConsF m n) = m + n

mulA :: ListF Int Int -> Int
mulA NilF        = 1
mulA (ConsF m n) = m * n

hyloにこれらと種 を渡すと、ある数から与えられた数までの整数を様々に畳み込んだ値が得られる。

>>> hylo sumA dec 4
10
>>> hylo mulA dec 4
24

これらの関数を素直に実装すると、以下のような再帰関数になるはずだ。これを上のF代数、F余代数と見比べる。

sum' :: Int -> Int
sum' 0 = 0
sum' n = n + sum' (n - 1)

factorial' :: Int -> Int
factorial' 0 = 1
factorial' n = n * factorial' (n - 1)

引数が種 に相当し、F余代数decに切り出されている。二項演算はF代数に切り出されている。再帰関数を停止させる部分はF余代数で、dec 0は長さ0のリストを作り出す。長さ0のリストををどう畳み込むかはF代数に任されている。再帰的構造（ここではリスト）は、F代数、F余代数の下にある関手$F$（ここでは $ListF_X$）に切り出されている。
F代数にもF余代数にも切り出されていない部分、すなわちhyloに残された部分は、再帰呼出しだ。

プログラミングにおける意義

hyloのプログラミングにおける意義は何だろう。cataやanaにはベタな再帰関数を書くよりも意図が明確になり、記述上のミスも減るという利点がある。
hyloでは、ベースにする関手の構造が再帰呼び出しのツリーを決定する。上のように、リストのベース関手を使えばコールツリーは線形になる。二分木を使ってフィボナッチ関数を書けば、コールツリーは二分木になる。MaybeやEitherを使えば中間構造が値を保持しないことになり、これは末尾再帰に相当する。すなわち、関手から計算量が推察できるという利点がある。
また、関手の構造が再帰呼び出しのコールツリーに対応することに注目して、これに工夫を加えた派生Morphismがある。なんとかモルフィズム

二分木でフィボナッチ数を求める例。

data FibF a = ZeroF | OneF | SuccF a a deriving (Functor)

fibCof :: Int -> FibF Int
fibCof 0 = ZeroF
fibCof 1 = OneF
fibCof n = SuccF (n - 1) (n - 2)

fibF :: FibF Int -> Int
fibF ZeroF       = 0
fibF OneF        = 1
fibF (SuccF m n) = m + n

>>> hylo fibF fibCof 10
55

末尾再帰で階乗を求める例。きちんとhyloを実装すれば、末尾呼び出し最適化をきかせることもできる。

facCof :: (Int, Int) -> Either Int (Int, Int)
facCof (m, 0) = Left  m
facCof (m, n) = Right (m * n, n - 1)

idEither :: Either Int Int -> Int
idEither = either id id

>>> hylo idEither facCof (1, 4)
24

しかし実際のところ、ふつうプログラミングをする上でHylomorphism自体を使うことはあまりない。畳み込みと展開の合成がHylomorphismであること、Hylomorphismの型が $X \rightarrow Y$ であることを利用して、リストを扱う関数の合成をする上で中間構造を作らないよう最適化をするのに応用されることがあるらしい。この辺りに興味があれば、HylomorphismとMetamorphismという記事が面白いと思う。

まとめ

AnamorphismやCatamorphismの合成からHylomorphismが作られることを確認した。
Hylomorphismが再帰関数の再帰呼び出し部分を取り出したものであることを確認し、さらにF代数/F余代数が元にしている関手が再帰関数のコールツリーを形づくることを確認した。

おじいさんや、次は何Morphismにしようかね。