Tutorial by Examples

Fix takes a "template" type and ties the recursive knot, layering the template like a lasagne. newtype Fix f = Fix { unFix :: f (Fix f) } Inside a Fix f we find a layer of the template f. To fill in f's parameter, Fix f plugs in itself. So when you look inside the template f you find a...

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 . fma...

Anamorphisms, or unfolds, model primitive corecursion. ana builds up a fixpoint layer by layer, using a coalgebra function (or unfolding function) to produce each new layer. ana requires a Functor instance for the template type f. ana :: Functor f => (a -> f a) -> a -> Fix f ana f = Fi...

It's common to structure a program as building up a data structure and then collapsing it to a single value. This is called a hylomorphism or refold. It's possible to elide the intermediate structure altogether for improved efficiency. hylo :: Functor f => (a -> f a) -> (f b -> b) ->...

Paramorphisms model primitive recursion. At each iteration of the fold, the folding function receives the subtree for further processing. para :: Functor f => (f (Fix f, a) -> a) -> Fix f -> a para f = f . fmap (\x -> (x, para f x)) . unFix The Prelude's tails can be modelled as ...

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...