Haskell Language Recursion Schemes Primitive corecursion


Apomorphisms model primitive corecursion. At each iteration of the unfold, the unfolding function may return either a new seed or a whole subtree.

apo :: Functor f => (a -> f (Either (Fix f) a)) -> a -> Fix f
apo f = Fix . fmap (either id (apo f)) . f

Note that apo and para are dual. The arrows in the type are flipped; the tuple in para is dual to the Either in apo, and the implementations are mirror images of each other.