Functional Programming with Bananas, Lenses, Envelopes and Barbed Wire

Here's a clearer version of the paper[0].

This paper[1] is a good way for object-oriented programmers to understand why functional programmers care about these higher order abstractions. The goal is not so different from OOP, which is about structuring programs as reusable components (AKA design patterns). The difference of course is that one doesn't need to resort to diagrams and prose, instead they can be written directly in the programming language.

Relatedly, one of my favorite books in functional programming is Algebra of Programming[2], which is about treating programs as an algebra that can be manipulated as easy (with practice) as algebraic expressions in math. The book solves various problems through program derivation, for instance solving the maximum subsegment problem by refining a naïve spec, deriving sorting algorithms, greedy algorithms, dynamic programming and thinning algorithms.

This draft book[3] has similar content to the earlier chapters of AoP but is far more accessible. The downside of AoP is that I had to resort to reading it with a math professor to understand it.

[0] https://maartenfokkinga.github.io/utwente/mmf91m.pdf

[1] http://www.cs.ox.ac.uk/jeremy.gibbons/publications/hodgp.pdf

[2] https://themattchan.com/docs/algprog.pdf

[3] http://www4.di.uminho.pt/~jno/ps/pdbc.pdf

Here is the PDF: https://ris.utwente.nl/ws/portalfiles/portal/6142049/meijer9... (and here is a more useful link to a publication database containing a link to a PDF: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.41.1...)

The text is from 1991.

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.

Useful as background reading for the "Ph.D. Haskell programmer" in https://willamette.edu/~fruehr/haskell/evolution.html .

TLDR explanation of the title: the paper introduces special mathematical notation for some recursion schemes: banana brackets (|...|) for folds and lense brackets [(...)] for unfolds as well as envelope brackets [[...]] and barbed wire (overlaying <...> and [...]).

That's a lovely paper. I'm glad it's still getting attention! Spread they joy.

To paraphrase: unnecessary, redundant abstractions is the root of all evil.

At least this is what plagued Haskell libraries - unnecessary abstract bullshit in dependencies.

Cabal works fine without any of those.