原始递归

Paramorphisms 模型原始递归。在折叠的每次迭代中,折叠函数接收子树以供进一步处理。

para::Functor f => (f (Fix f, a) -> a) -> Fix f -> a
para f = f . fmap (\x -> (x, para f x)) . unFix

Prelude 的 tails 可以被建模为一个 paramorphism。

tails::List a -> List (List a)
tails = para alg
    where alg Nil_ = cons nil nil  -- [[]]
          alg (Cons_ x (xs, xss)) = cons (cons x xs) xss  -- (x:xs):xss