Let's try to make this a tad less abstract with a (hopefully) more practical teaser: 1. Let's define a simple binary tree and a (recursive) function to process

Let's try to make this a tad less abstract with a (hopefully) more practical teaser: 1. Let's define a simple binary tree and a (recursive) function to process it: data Tree a = Leaf a | Node (Tree a) (Tree a) processTree :: (a -> b) -> (b -> b -> b) -> Tree a -> b processTree processLeaf processNode = walk where walk (Leaf v) = processLeaf v walk (Node l r) = processNode (walk l) (walk r) processTree takes 2 functions, namely the "how to process a leaf?" and the "how to process a node?" ones as well as a tree and then... processes it :) Now, given a tree of Ints, we can use the above to eg. sum its values, find the biggest one or count the nodes: λ> myTree = Node (Node (Leaf 3) (Leaf 9)) (Leaf 7) λ> processTree (+ 1) (+) myTree 22 λ> processTree id max myTree 9 λ> processTree (const 1) (+) myTree 3 Great. Now, instead of defining the above Tree type as an inductive type, let's factor that part out: data TreeShape a rec = Leaf a | Node rec rec This type is kinda like the original except we add a new type variable (rec) for the inductive part. Ok, now comes the interesting (crazy?) part: Let's define a weird type called Fix: newtype Fix f = Fix {unFix :: f (Fix f)} Don't get lost in it! Just read on. Let's use this weird Fix type to define our original Tree type as such: type Tree a = Fix (TreeShape a) Also let's rewrite the original processTree function using this new type: processTree :: (TreeShape a b -> b) -> Tree a -> b processTree process = walk where walk (Fix (Leaf v)) = process (Leaf v) walk (Fix (Node l r)) = process (Node (walk l) (walk r)) Looks kinda like the original except that it now uses the same(!) function (aka. algebra) to process both leaves and nodes. This allows us to write simple (non-recursive) functions: sum (Leaf v) = v sum (Node l r) = l + r max (Leaf a) = a max (Node l r) = max l r size (Leaf _) = 1 size (Node l r) = l + r and recover: λ> myTree = Fix $ Node (Fix $ Node (Fix $ Leaf 3) (Fix $ Leaf 9)) (Fix $ Leaf 7) λ> processTree sum myTree 19 λ> processTree max myTree 9 λ> processTree size myTree 3 At this point you might rightfully ask: Why oh why would we go through all this suffering just to recover the same functionality we had originally? Good question :) To answer it we need to realise that "TreeShape a" (and thus also "Tree a") is a member of a class called Functor, which means it knows how to map functions over itself. The magic incantation to do such mapping is called fmap in Haskell. Let's make TreeShape work with fmap: instance Functor (TreeShape a) where fmap _ (Leaf v) = Leaf v fmap f (Node l r) = Node (f l) (f r) Now, knowing the above, we can rewrite our processTree function into a _much_ more generic form that works not just on our Tree type but on _any_ Functor: processFunctor :: Functor f => (f b -> b) -> Fix f -> b processFunctor process = process . fmap (processFunctor process) . unFix This processFunctor function (aka. catamorphism) has no notion of the shape it processes other than that shape should know how to map a function over itself (ie. it's a Functor). As an added bonus we don't even need to write Functor instances for our types by hand as deriving them is a deterministic and mechanical process and thus the compiler is more than happy to do it for us: data TreeShape a rec = Leaf a | Node rec rec deriving stock Functor To summarise: if we want to process some recursive data structure and that data structure happens to be a Functor then all we need to do is derive it's functor instance, write a simple function to do something with an element of the structure and apply that function to the whole using processFunctor.