Haskell Language Recursion Schemes Unfolding and then folding, fused
Example
It's common to structure a program as building up a data structure and then collapsing it to a single value. This is called a hylomorphism or refold. It's possible to elide the intermediate structure altogether for improved efficiency.
hylo :: Functor f => (a -> f a) -> (f b -> b) -> a -> b
hylo f g = g . fmap (hylo f g) . f -- no mention of Fix!
Derivation:
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
