一次折叠一层结构
Catamorphisms 或折叠,模拟原始递归。cata
逐层拆除固定点,使用代数函数(或折叠函数 )处理每一层。cata
需要 Functor
实例作为模板类型 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