一次摺疊一層結構
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