展開然後摺疊融合

將程式構建為構建資料結構然後將其摺疊為單個值是很常見的。這就是所謂的 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