The Fix f data type allows you to specify a recursive datatype from its fixpoint. Folds and unfolds, as catamorphisms and anamorphisms, come for free. With these recursion schemes, functions can be specified over the data type without explicit recursion. A catamorphism folds bottom-top to a single value, while its dual the anamorphism can be used to unfold a single value.

newtype Fix f = Fix { unFix :: f (Fix f) }

cata :: Functor f => (f a -> a) -> Fix f -> a
cata alg = alg . fmap (cata alg) . unFix

ana :: Functor f => (a -> f a) -> a -> Fix f
ana coalg = Fix . fmap (ana coalg) . coalg


# Example

A binary tree is a recursive data type that lends itself perfectly well for definition by Fix. Notice that TreeF is not recursive and would also allow for example for a tagged binary tree by using a CoFree a f Comonad.

{-# LANGUAGE TypeSynonymInstances,FlexibleInstances,LambdaCase,DeriveFunctor #-}

type Tree a = Fix (TreeF a)
data TreeF a r = NodeF r r | LeafF a deriving Functor

instance Show a => Show (Tree a) where
show = cata $\case NodeF l r -> unwords ["(", l, r, ")"] LeafF x -> show x  *Main> let node l r = Fix$ NodeF l r
*Main> let leaf x = Fix $LeafF x *Main> (leaf 0 node leaf 1) node (leaf 2 node leaf 3) ( ( 0 1 ) ( 2 3 ) )  # Adding Context However, the catamorphism only passes information bottom to top. It is not possible to pass down context from a parent node to a child node. I came across this problem when converting an expression to its DeBruijn convention form. A simpler use case that can not be done solely using a catamorphism is tagging the leaves of a tree with their depth. ctxm :: Functor f => t -> (f (Fix f) -> t -> t) -> (t -> f b -> b) -> Fix f -> b ctxm ctx nxt alg (Fix f) = alg ctx (fmap (ctxm (nxt f ctx) nxt alg) f)  I believe it is certainly possible to archieve this using existing recursion schemes (there are a lot of them), but trying to do that took me longer than finding this function. Here is an example of depth-tagging the above-defined binary tree. label :: Tree a -> Tree (Integer, a) label = ctxm 0 nxt alg where -- state/context modifying function nxt (NodeF _ _) = (+1) nxt (LeafF _) = id -- algorithm that uses the context alg ctx (LeafF x) = Fix$ LeafF (ctx, x)
alg ctx (NodeF l r) = Fix $NodeF l r  *Main> label$ (leaf 0 node leaf 1) node leaf 3
( ( (2,0) (2,1) ) (1,3) )


And there it is, a catamorphism with context.