展開然後摺疊融合
將程式構建為構建資料結構然後將其摺疊為單個值是很常見的。這就是所謂的 hylomorphism 或復性。為了提高效率,可以完全忽略中間結構。
hylo::Functor f => (a -> f a) -> (f b -> b) -> a -> b
hylo f g = g . fmap (hylo f g) . f -- no mention of Fix!
推導:
hylo f g = cata g . ana f
= g . fmap (cata g) . unFix . Fix . fmap (ana f) . f -- definition of cata and ana
= g . fmap (cata g) . fmap (ana f) . f -- unfix . Fix = id
= g . fmap (cata g . ana f) . f -- Functor law
= g . fmap (hylo f g) . f -- definition of hylo