Functional Programming with Bananas, Lenses, Envelopes and Barbed Wire
Let&#x27;s try to make this a tad less abstract with a (hopefully) more practical teaser:<p>1. Let&#x27;s define a simple binary tree and a (recursive) function to process it:<p><pre><code>    data Tree a
      = Leaf a
      | Node (Tree a) (Tree a)

    processTree :: (a -&gt; b) -&gt; (b -&gt; b -&gt; b) -&gt; Tree a -&gt; b
    processTree processLeaf processNode = walk
      where
        walk (Leaf v) = processLeaf v
        walk (Node l r) = processNode (walk l) (walk r)
</code></pre>
processTree takes 2 functions, namely the &quot;how to process a leaf?&quot; and the &quot;how to process a node?&quot; 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:<p><pre><code>    λ&gt; myTree = Node (Node (Leaf 3) (Leaf 9)) (Leaf 7)
    λ&gt; processTree (+ 1) (+) myTree
    22
    λ&gt; processTree id max myTree
    9
    λ&gt; processTree (const 1) (+) myTree
    3
</code></pre>
Great. Now, instead of defining the above Tree type as an inductive type, let&#x27;s factor that part out:<p><pre><code>    data TreeShape a rec
      = Leaf a
      | Node rec rec
</code></pre>
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&#x27;s define a weird type called Fix:<p><pre><code>    newtype Fix f = Fix {unFix :: f (Fix f)}
</code></pre>
Don&#x27;t get lost in it! Just read on. Let&#x27;s use this weird Fix type to define our original Tree type as such:<p><pre><code>    type Tree a = Fix (TreeShape a)
</code></pre>
Also let&#x27;s rewrite the original processTree function using this new type:<p><pre><code>    processTree :: (TreeShape a b -&gt; b) -&gt; Tree a -&gt; b
    processTree process = walk
      where
        walk (Fix (Leaf v)) = process (Leaf v)
        walk (Fix (Node l r)) = process (Node (walk l) (walk r))
</code></pre>
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:<p><pre><code>    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
</code></pre>
and recover:<p><pre><code>    λ&gt; myTree = Fix $ Node (Fix $ Node (Fix $ Leaf 3) (Fix $ Leaf 9)) (Fix $ Leaf 7)
    λ&gt; processTree sum myTree
    19
    λ&gt; processTree max myTree
    9
    λ&gt; processTree size myTree
    3
</code></pre>
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 &quot;TreeShape a&quot; (and thus also &quot;Tree a&quot;) 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&#x27;s make TreeShape work with fmap:<p><pre><code>    instance Functor (TreeShape a) where
      fmap _ (Leaf v) = Leaf v
      fmap f (Node l r) = Node (f l) (f r)
</code></pre>
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:<p><pre><code>    processFunctor :: Functor f =&gt; (f b -&gt; b) -&gt; Fix f -&gt; b
    processFunctor process = process . fmap (processFunctor process) . unFix
</code></pre>
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&#x27;s a Functor). As an added bonus we don&#x27;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:<p><pre><code>    data TreeShape a rec
      = Leaf a
      | Node rec rec
      deriving stock Functor
</code></pre>
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&#x27;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.