Haskell Language Recursion Schemes Folding up a structure one layer at a time
Example
Catamorphisms, or folds, model primitive recursion. cata tears down a fixpoint layer by layer, using an algebra function (or folding function) to process each layer. cata requires a Functor instance for the template type f.
cata :: Functor f => (f a -> a) -> Fix f -> a
cata f = f . fmap (cata f) . unFix
-- list example
foldr :: (a -> b -> b) -> b -> List a -> b
foldr f z = cata alg
where alg Nil_ = z
alg (Cons_ x acc) = f x acc
