In the past two posts, we defined a datatype `Term`

that represents the fixed-point of a functor `f`

, with an `In`

constructor that ties an `f (Term f)`

into a `Term f`

, and an `out`

deconstructor that unties a `Term f`

into an `f (Term f)`

:

`newtype Term f = In { out :: f (Term f) }`

Using `fmap`

, and the property that `fmap`

is the identity function over a `Functor`

with no children, we can define a `bottomUp`

function that applies a type-preserving transformation to any `Term f`

:

```
bottomUp :: Functor a => (Term a -> Term a) -> Term a -> Term a
bottomUp fn =
out -- 1) unpack
>>> fmap (bottomUp fn) -- 2) recurse
>>> In -- 3) repack
>>> fn -- 4) apply
```

And, when we omit the repacking stage in the above definition, we yield `cata`

, a generalized fold operator that allows us to collapse a given `Term f`

into an accumulated value `a`

, using an `Algebra`

that reunites an `f a`

into an `a`

:

```
type Algebra f a = f a -> a
cata :: (Functor f) => Algebra f a -> Term f -> a
cata fn =
out -- 1) unpack
>>> fmap (cata fn) -- 2) recurse
>>> fn -- 3) apply
```

Catamorphisms are simple and elegant, but in many real-world use-cases they are insufficient. For example, though the function we pass to `cata`

allows us to view the data we're transformating, it loses information about the original structure: in the case of pretty-printing, we only have access to the currently-printed tree (the `f Doc`

for any fix): any information about the structure of the original `Term Expr`

is lost, as it has already been pretty-printed.

This would be a problem if you wanted to print, say, zero-argument functions in a different manner than other functions: you'd have to use `==`

to examine the `Doc`

type, then dispatch on the result to implement this different behavior. And your `Doc`

type may omit an `Eq`

instance, so `==`

may not even be possible! (Besides, looking at the pretty-printed results to infer their inputs is clumsy at best and often inaccurate in the presence of hyphenation or spacing.)

It would be ideal if our `Algebra`

could, when examining an `Expr`

node, have access both to its pretty-printed representation and its original representation as a `Term`

—an `Algebra`

that has access to the original, un-transformed datum, represented as its fixed-point `Term`

. That is to say, whereas `Algebra`

is a function from a container `f`

of `a`

, we want a function from container that holds *both* a `Term f`

and its corresponding `a`

. Rather than using a function with two arguments, we'll bundle these two arguments together in a tuple (for reasons that will become clear later).

`f (Term f, a) -> a`

Algebras that carry this extra information are known as *R-algebras*.

`type RAlgebra f a = f (Term f, a) -> a`

There is another type of morphism that allows you to traverse a structure with an R-algebra: the *paramorphism*. As with previous examples, I'm going to explicate the etymology in the hope that it slightly illuminates a complicated concept: the *para* in paramorphism is the same as in *parallel*—from the Greek παρά, meaning "beside", "next to", or "alongside"^{1}. A paramorphism is like a catamorphism except that it can view the original structure *beside* the structure that is being transformed.

So, let's implement paramorphisms. They'll look like the catamorphism we already discussed. But instead of just directly recursing into the structure with `fmap para`

, we have to recurse with a function that returns a tuple, one that contains both the `Term`

we're recursing into and the result of recursively applying `para`

. We do this here with a helper function called `fanout`

, which takes a `Term f`

and returns both items in which we are interested: the `Term`

itself, and the result of recursively applying `para`

.

```
para :: (Functor f) => RAlgebra f a -> Term f -> a
para rAlg = out >>> fmap fanout >>> rAlg
where fanout :: Term f -> (Term f, a)
fanout t = (t, para rAlg t)
```

And we're done! This is the classical definition of a paramorphism. With it, we can have our cake and eat it too: we can intelligently fold over a data structure without losing any information about the original representation of said structure.

And Haskell comes with a function that makes expressing the above `fanout`

function even more elegant than it already is. The `&&&`

combinator, provided in the `Control.Arrow`

module, takes two functions^{2} `foo`

and `bar`

and returns another function that, when given a value `a`

, returns a tuple consisting of `(foo a, bar a)`

. Simply put, it combines the output of two functions.

Our `fanout`

function, when provided with a `Term f`

, needs to do two things: preserve its input in the first element of the tuple, and recurse with `para`

into its input, providing the result of doing so in the second element. We can use `&&&`

to express this concisely: given a `Term f`

, we preserve the element with the identity function `id`

, and apply `para`

recursively to the argument. Let's express this as such:

`fanout = id &&& para f`

Now we can express `para`

with our new, beautiful `fanout`

function:

```
para' :: Functor f => RAlgebra' f a -> Term f -> a
para' f = out >>> fmap (id &&& para' f) >>> f
```

The type signatures indicate that both these formulations of paramorphisms are equivalent: which one you choose is entirely up to which one you find more aesthetically pleasing.

For extra credit: rather than using a function that takes a container of tuples (which can strike the eye as somewhat ugly), we can use one that takes two arguments, both the `Term f`

and the container `f a`

. (We can convert between this representation and `RAlgebra`

trivially).

`type RAlgebra' f a = Term f -> f a -> a`

Balazs Komuves refers to this formulation as "slightly less natural" in his Fixplate library. The implementation is indeed less pleasing, as it cannot easily be expressed in a point-free fashion, but it has a nice property that we'll explore below.

```
-- The & function is reverse function application,
-- just like the $ operator, but with its arguments flipped.
para'' :: Functor f => RAlgebra' f a -> Term f -> a
para'' alg t = out t & fmap (para'' alg) & alg t
```

And just as we were able to represent `bottomUp`

in terms of `cata`

, we can express `cata`

in terms of `para'`

—after all, *a catamorphism is merely a paramorphism that ignores the provided Term*. And Haskell provides the

`const`

function (aka the K-combinator) for just these situations where we want to ignore an argument to a function:```
cata' :: Functor f => Algebra f a -> Term f -> a
cata' = para'' (const f)
```

Beautiful, no? This is one of the really appealing things about recursion schemes: as we explore more and more powerful constructs, we see how the less-powerful constructs can be implemented straightforwardly in terms of more general ones.

The identity function `id`

, by definition, returns its argument unchanged: `id(x)`

can be replaced with `x`

in every case. Let's imagine a pretty-printer that, for some reason^{3}, performs this optimization step on its output.

To do this with a simple catamorphism, we'd need to check every function-call's pretty-printed name to determine whether it is `id`

, then return the argument unchanged—and, as I mentioned above, our pretty-printed `Doc`

representation shouldn't even support an equality operation, so examining it is a no-go. However, we can do this easily with a paramorphism. In order to avoid having to write a bunch of tuples, I'm going to use the second representation of R-algebras above (the ternary function), and I'm going to use the `Expr`

syntax tree defined in previous installments.

```
{#- LANGUAGE RecordWildCards -#}
import qualified Text.PrettyPrint.ANSI.Leijen as P
fastPretty :: RAlgebra' Expr Doc
-- All our cases, aside from the `Call` nodes in which
-- we are interested, are the same as in the pretty-printing
-- catamorphism in the previous installment. We just ignore
-- the first `Term` argument because it doesn't have anything we need
-- to look at.
fastPretty _ (Literal i) = P.int i
fastPretty _ (Ident s) = P.text
-- uninteresting cases omitted, blah blah blah
-- Here's where it gets interesting. We're going to look
-- at the first argument to determine whether this is a
-- `Call` node with the function name (an `Ident`) named `id`.
-- If so, we'll just return the only argument provided.
fastPretty (In (Call { name = "id", ..})
(Call {args = [theArg], ..}) = theArg
-- Otherwise, we won't look at the first `Term` argument,
-- and just glom the name and the parenthesized and
-- comma-separated arguments together.
fastPretty _ (Call f args) = f <> P.parens ("," `P.punctuate` args)
```

During complicated tree transformations, the context of the structure you're transforming will eventually come into play. Catamorphisms don't let you examine this context, but paramorphisms do.

In the previous post, we defined `ana`

, the anamorphism, a generalized unfold operating on any given data type to generate a `Term f`

. While unfolds are a little more abstruse and less common than folds, it's worth walking through their construction, if only to observe the generality achieved from reversing the arrows in a given morphism.

We expressed `ana`

as the dual to `cata`

, replacing instances of `out`

with `In`

, and replacing left-to-right function composition with the right-to-left equivalent, `<<<`

(more commonly expressed with Haskell's `.`

function)—in short, reversing the arrows of the definition.

```
cata f = out >>> fmap (cata f) >>> f
ana f = In <<< fmap (ana f) <<< f
```

And we defined the function argument that `ana`

takes as a `Coalgebra`

, seeing as how it is dual to the `Algebra`

we already defined:

```
type Coalgebra f a = a -> f a
ana f :: (Functor f) => Coalgebra f a -> a -> Term f
```

It stands to reason that we can define the dual of a paramorphism—a co-paramorphism. But, as always, we have a better name for this: the dual of a paramorphism is an *apomorphism*. Just as the ana- prefix is the opposite of the cata- prefix, so the para- prefix is the opposite of the apo- prefix. In this case, apo- comes from the Greek ἀπο, meaning "away from" or "separate", as in "apogee" (the moon being away from the earth) or "apostasy" (someone turning away from their beliefs).

So, let's start by defining the categorical dual of the R-algebra. We've reversed the arrows in every case, so the following definition should be correct, right?

`type Nope = a -> f (Term f, a)`

Wrong! We have to apply the dual to every construct in the definition of `RAlgebra`

. We need to reverse the direction of the function, yes, but we also need to reverse the tuple associated with the above definition. So what's the dual of a tuple?

Well, let's consider what a tuple is for. Given two arguments `big`

and `pac`

, a tuple bundles both of them together as `(big, pac)`

. That makes sense, yes, but what can we do with both of these arguments that fits the notion of the "opposite" of holding both? Well, we can hold one or the other. And Haskell provides a concept to hold either a `big`

or a `pac`

: namely, `Either`

. So, given that an `Algebra f a`

holds a `Term f`

and an `a`

, we can express the dual of an R-algebra using an `Either`

:

`type RCoalgebra = a -> f (Either (Term f) a)`

But what does this *mean* when we're using apomorphisms in practice? Well, it allows us to *separate* the flow of computation during our unfolds. If our R-coalgebra returns a `Left`

value in which is contained a `Term`

, the apomorphism will terminate and return the provided value. If it returns a `Right`

value containing an `f a`

, the unfold will continue onwards. This is cool! The ability to terminate during a corecursive iteration depending on the argument is a very useful property—and we need no imperative constructs such as `break`

or (*shudder*) exceptions^{4}.

So, just as we expressed `ana`

by reversing the arrows of `cata`

, we can express `apo`

by reversing the arrows of `para`

:

```
para :: Functor f => RAlgebra' f a -> Term f -> a
para f = out >>> fmap fanout >>> f where fanout = id &&& para f
apo f :: Functor f => RCoalgebra f a -> a -> Term f
apo f = In <<< fmap fanin <<< f where fanin = ???
```

It may not be immediately obvious how to implement `fanin`

. But, when you reverse the arrows of the `fanout`

definition above (I have omitted said reversal for brevity's sake), you'll discover that you yield a function that takes an `Either (Term f) a`

and returns a `Term f`

.

`fanin :: Either (Term f) a -> Term f`

As such, our function will handle this either by applying `id`

in the case of a `Left`

value (as getting a `Term`

means that we can just return the `Term`

) and recursing with `apo`

in the case of a plain old `a`

value, out of which we ultimately yield a `Term`

, thanks to the ultimate signature of `apo`

. And Haskell's built-in `either`

function, which takes two functions and an Either and returns a result of applying the first to a `Left`

case or the second to the `Right`

case, allows us to express this `fanin`

function beautifully. `id`

does nothing the value contained inside a `Left`

, returning just a `Term f`

, and `apo f`

continues the unfold operation when provided a `Right`

:

```
apo f :: Functor f => RCoalgebra f a -> a -> Term f
apo f = In <<< fmap fanin <<< f where fanin = either id (apo f)
```

Similarly, we can rewrite `fanin`

with `|||`

, the dual of the `&&&`

function above. (The operators here are a useful visual mnemonic: `&&&`

uses both the functions it provides, where as `|||`

uses one or the other).

```
apo f :: Functor f => RCoalgebra f a -> a -> Term f
apo f = In <<< fmap (id ||| apo f) <<< f
```

If you made it this far, you've got some serious chops, and I salute you. Next time, we'll look at futumorphisms and histomorphisms, and uncover some seriously powerful constructs (and some seriously dubious etymologies).

*I am indebted to Rob Rix, Colin Barrett, and Manuel Chakravarty for their input and suggestions regarding this post*.

Modern English tends to use "para" as a prefix meaning "pseudo" or "abnormal" (as in "parapsychology" or "paresthesia")—this is an extension of the "alongside" meaning, implying that abnormal things appear alongside normal things. Be sure not to confuse these two meanings—there's nothing abnormal or second-class about paramorphisms.↩

Technically, two

`Categories`

, but if you use instances of`Category`

beyond`(->)`

then you are way ahead of me.↩You'd have to be a complete lunatic to put this optimization step in your pretty-printer—you'd either perform this as an optimization over the original code or during a conversion to a separate intermediate representation—but I'm going to stick with this incredibly contrived example, because the

`Doc`

type makes it very clear, when operating on`Expr`

types, when and where the pretty-printing step is happening.↩I hate exceptions. Hate 'em. But that subject deserves its own post.↩

On the last episode of this very-infrequently-updated analysis of *Programming with Bananas, Lenses, Envelopes, and Barbed Wire*, we took a look at how to represent and traverse nested structures. This time, we’ll start getting into the meat of the paper^{1}. We’ll define two simple recursion schemes, explore

On the last episode of this very-infrequently-updated analysis of *Programming with Bananas, Lenses, Envelopes, and Barbed Wire*, we took a look at how to represent and traverse nested structures. This time, we’ll start getting into the meat of the paper^{1}. We’ll define two simple recursion schemes, explore how they relate to each other, and I’ll offer up some example sitations (both real-world and contrived) of situations that admit the use of recursion schemes.

We’ll start by defining a simple syntax tree, as we did last time.

```
{-# LANGUAGE DeriveFunctor #-}
data Expr a
= Literal { intVal :: Int }
| Ident { name :: String }
| Index { target :: a, idx :: a }
| Unary { op :: String, target :: a }
| Binary { lhs :: a, op :: String, rhs :: a }
| Call { func :: a, args :: [a] }
| Paren { target :: a }
deriving (Show, Eq, Functor)
```

We define two root constructors to represent the leaf nodes of the tree (`Literal`

and `Ident`

, wrapping `Int`

and `String`

values respectively) and five other constructors. Every position in which subexpressions may appear – the left-hand and right-hand sides to a binary operation, the target of a unary operation, the function and arguments in a function invocation – is represented by a value of type `a`

, in terms of which Expr is defined^{2}.

We use the `DeriveFunctor`

GHC extension to provide a definition of the `Functor`

typeclass for `Expr`

, which provides us with an `fmap`

function. `fmap f`

, applied to a given `Expr`

, applies `f`

to each subexpression `a`

, and is the identity function when passed a `Literal`

or `Ident`

value, as they contain no subexpressions.

At this point, we can represent expressions with no subexpressions with the type `Expr ()`

; for expressions at most one level of subexpressions, we can use `Expr (Expr ())`

; for two, `Expr (Expr (Expr ())`

, and so on and so forth. What we want is to represent an arbitrarily-nested `Expr`

– in essence, an `Expr (Expr (Expr (Expr ...)))`

– but, since Haskell doesn’t support infinite types, we have to resort to a least-fixed-point combinator. We call this combinator `Term`

, with an `In`

constructor and an `out`

accessor function.

`newtype Term f = In { out :: f (Term f) }`

Now we represent arbitrarily-nestable `Expr`

s with values of type `Term Expr`

, obtained by applying the `In`

constructor with a constructor from `Expr`

^{3}:

```
ten, add, call :: Term Expr
ten = In (Literal { intVal = 10 })
add = In (Ident { name = "add" })
call = In (Call { func = add, args = [ten, ten]}) -- add(10, 10)
```

Using the `>>>`

operator for left-to-right function composition, we expressed a generalized bottom-up traversal capable of operating on any data type that implements the `Functor`

typeclass.

```
bottomUp :: Functor a => (Term a -> Term a) -> Term a -> Term a
bottomUp fn =
out -- 1) unpack a `Term a` into an `a (Term a)`
>>> fmap (bottomUp fn) -- 2) recurse, with fn, into the subterms
>>> In -- 3) repack the `a (Term a)` into a `Term a`
>>> fn -- 4) finally, apply fn to the packed `Term a`
```

While this is a pleasing and concise representation of bottom-up transformations, it’s not as powerful as it could be: specifically, `fn`

is limited to taking *and returning* a value of type `Term f`

. We could not use `bottomUp`

to count the total number of subexpressions in a tree (going from `Expr`

s to `Int`

s), nor could we transform this tree to a DOM representation (`Node`

), nor could we render a term into a pretty-printed representation (`Doc`

).

This is a direct result of the third step above: after recursing into the data structure with `fn`

in step #2, we stuff it into a `Term`

using the `In`

constructor in step #3 before passing it to `fn`

. This forces `fn`

to both take and return a `Term`

. What if we wrote a version of `bottomUp`

that omitted that particular call to `In`

? Would it typecheck?

It does:

```
mystery fn =
out -- 1) unpack the Term
>>> fmap (mystery fn) -- 2) recursively apply `fn`
>>> fn -- 3) apply `fn`
```

Loading this function in `ghci`

and querying its type yields the following result:

```
λ> :t mystery
mystery :: Functor f => (f a -> a) -> Term f -> a
```

Cool. How does this work?

Let’s take a closer look at that first parameter:

`Functor f => (f a -> a)`

This is a function type, taking as input a container^{4} `f`

of values of type `a`

and returning a bare value of type `a`

. If we wanted to write a `countNodes`

function that counts (as an `Int`

) the number of subexpressions within a given `Term Expr`

, `f`

would be equal to `Expr`

(which has a `Functor`

instance), and `a`

would be `Int`

.

`countNodes :: Expr Int -> Int`

The crucial element of understanding this function is its first parameter, here `Expr Int`

. It captures an `Expr`

*in the process of transformation* – because subexpressions (the `lhs`

and `rhs`

field of `Binary`

, the `func`

and `args`

fields of `Call`

) were represented as values of the parameterized type `a`

, we can capture the bottom-up nature of transformation *in the type itself*. This means that each case for `countNodes`

is easy to express: merely add 1 to the sum of all the contained subexpressions.

```
countNodes (Unary _ arg) = arg + 1
countNodes (Binary left _ right) = left + right + 1
countNodes (Call fn args) = fn + sum args + 1
countNodes (Index it idx) = it + idx + 1
countNodes (Paren arg) = arg + 1
```

And our base case for this transformation falls out easily: `Literal`

and `Ident`

have no subexpressions, so they just return 1:

```
countNodes (Literal _) = 1
countNodes (Ident _) = 1
```

Applying `mystery countNodes`

to our example `add(10, 10)`

datum should yield 4. Does it?

```
λ> mystery countNodes call
4
```

Dope.

I had a major mental block in understanding when, in fact, the `countNodes`

function was actually called, and how `mystery`

managed to recurse as deeply as possible into the passed structure. The key lies in the invocation of `fmap`

within `mystery`

:

`fmap (mystery fn)`

Because `fmap f`

applies `f`

to each subexpression within an `Expr`

, `mystery`

starts out by recursing as deeply as possible into the `Term`

it is passed, since it calls itself recursively with `fmap`

. It’s almost magical how `mystery`

“knows” how to stop recursing – but it lies in the definition of `fmap`

. `fmap mystery`

*is the identity function* over `Literal`

and `Ident`

values, as they do not contain any subexpressions. At this point, `mystery`

stops recursing, applies the function `f`

, and returns into its previous invocations. As the stack unwinds, `fn`

gets applied to the next-highest node in the tree, then the next, then the next, until all the original `Expr`

values are gone and we yield only an `a`

. It all comes down to the capabilities of `fmap`

– from a straightforward purpose and declaration emerges a deep and subtle way to fold over a structure.

Indeed, functions of type `f a -> a`

are so ubiquitous that we refer to them by their own name:

`type Algebra f a = f a -> a`

When you see a value of type `Algebra f a`

, know that it’s a function from a container `f`

to a collapsed value `a`

. We could rewrite the type signature of the above `countNodes`

function to use it:

`countNodes :: Algebra Expr Int`

The use of the term “algebra” to in this context may seen a bit discomfiting. Most people use the term “algebra” to describe manipulating numerical expressions (as well as the associated drudgery of childhood math courses). Why are we overloading this term to represent a class of functions?

The etymology of “algebra” can shed some light on this—it stems from the Arabic root جبر, *jabr*, which means “restoration” or “reunion”. An algebra is a function that *reunites* a container of `a`

’s—an `f a`

—into a single accumulated `a`

value.

So, now that we have a grasp on what an algebra is and why we’re calling it that, let’s rewrite the type signature of `mystery`

using the `Algebra`

type synonym.

`mystery :: (Functor f) => Algebra f a -> Term f -> a`

This `mystery`

function is known as a *catamorphism*, usually given the name `cata`

:

```
cata :: (Functor f) => Algebra f a -> Term f -> a
cata f = out >>> fmap (cata f) >>> f
```

Again, though the term “catamorphism” may seem needlessly arcane, its etymology both simplifies and clarifies its purpose: the “cata” in “catamorphism” is the same “cata” in “catastrophe”, “catabolism”, and “catalyst”—from the Greek κατα, meaning “downwards”, “into”, or “collapse”. Just as a catastophe is an unlucky event that tears things down, and catabolism is the collapse of muscle fibers, a catamorphism uses an algebra (a reunion) to collapse a container of values into a single value.

If you’re reminded of the `fold`

operation on lists, you’re on the right track: a list fold (specifically `foldr`

^{5}) is merely a catamorphism limited to operate on lists (the `[]`

type, the archetypal `Functor`

). That’s the essence of catamorphisms: they’re *generalized fold operations*, applicable to *any* functor—not just lists—all without having to write a line of boilerplate traversals and without sacrificing a mote of type safety.

Another excellent example of catamorphisms is pretty-printers for trees. If the representation you require of a tree type can be expressed in a purely bottom-up manner – that is to say, it requires no information about the original structure of the tree being transformed – you can express pretty-printing functions in a truly wonderfully concise manner. (Spoiler alert: later on, we’ll figure out how to do this even when you need access to the original structure.) We can describe a pretty-printing algebra from `Expr`

to `Doc`

, an abstract document type provided by the Text.PrettyPrint module.

```
import Text.PrettyPrint (Doc)
import qualified Text.PrettyPrint as P
prettyPrint :: Algebra Expr Doc
```

Again, expanding the type synonym yields us a function type, going from `Expr`

s with values of type `Doc`

as their subexpressions, out to a final `Doc`

value. These values represent the leaves of the nodes that have already been pretty-printed.

`prettyPrint :: Expr Doc -> Doc`

Our base cases are straightforward:

```
prettyPrint (Literal i) = P.int i
prettyPrint (Ident s) = P.text s
```

And our inductively-defined cases are beautifully clutter-free:

```
prettyPrint (Call f as) = f <> P.parens (P.punctuate "," as) -- f(a,b...)
prettyPrint (Index it idx) = it <> P.brackets idx -- a[b]
prettyPrint (Unary op it) = (P.text op) <> it -- op x
prettyPrint (Binary l op r) = l <> (P.text op) <> r -- lhs op rhs
prettyPrint (Paren exp) = P.parens exp -- (op)
```

Applying `prettyPrint`

to our example `call`

datum should yield a nice representation:

```
λ> cata prettyPrint call
add(10,10)
```

One final detail: we can represent our `bottomUp`

function in terms of `cata`

. Indeed, `bottomUp f`

is just `cata f`

, with the additional step of stuffing the accumulator value into a `Term`

with `In`

before handing it off to `f`

:

`bottomUp f = cata (In >>> f)`

In the last post, we defined a corresponding `topDown`

method, the opposite of `bottomUp`

. Furthermore, we did so by “reversing the arrows” in `bottomUp`

: we changed the left-to-right composition operator `>>>`

to its flipped `<<<`

(which is equivalent to the `.`

operator), and we flipped around all invocations of `out`

to `In`

and `In`

to out.

```
bottomUp f = out >>> fmap (bottomUp f) >>> In >>> f
topDown f = In <<< fmap (topDown f) <<< out <<< f
```

By applying this “reversing the arrows” trick, we managed to express the duality between bottom-up and top-down traversals. So what happens if we do the same to our definition of `cata`

? Does it typecheck?

```
cata f = out >>> fmap (cata f) >>> f
-- reverse the arrows: >>> becomes <<<. and out becomes In
what f = In <<< fmap (what f) <<< f
```

You’re damn right it does. What’s its type signature?

`what :: (Functor f) => (a -> f a) -> a -> Term f`

Just as when we yielded a top-down traversal by reversing a bottom-up one, we yield an *unfold* when we reverse the arrows in our generalized fold function. Again, let’s take a look at the type of the first parameter, the unfolding function:

`Functor f => (a -> f a)`

Similar to our `Algebra`

type `a -> f a`

, right? Exactly the same, except the direction of the function arrow has reversed: whereas algebras are mappings from `f a`

to `a`

, this new function type maps `a`

s to `f a`

s. We call this function type a *coalgebra*.

`type Coalgebra f a = a -> f a`

We call the `what`

an *anamorphism* – the “ana” prefix, meaning “building”, is the opposite of “cata”. Just like `cata`

generalized `fold`

from lists to any `Functor`

, `ana`

generalizes `unfold`

to any `Functor`

.

```
ana :: (Functor f) => Coalgebra f a -> a -> Term f
ana = f = In <<< fmap (ana f) <<< f
```

If we thought about algebras as *reunions*, we can think about coalgebras as *disassembly* or *dispersion*. We’re taking one established `a`

value and stuffing it inside a context `f`

. If that `f`

is `Maybe`

, then we’re allowing for the possibility that no value will be present; if that `f`

is `[]`

, the list monad, it means we’re allowing there to be zero or more results. (Extremely alert readers of the Typeclassopedia will notice that `Algebra`

and `Coalgebra`

are extraordinarily similar to the `Pointed`

and `Copointed`

typeclasses. Bully for you if you noticed that.)

Thanks very much for Rob Rix for encouraging me to publish this.

On a personal note, I am deeply grateful for all the comments I’ve received thus far, both complimentary and constructive.

*In part 3, we explore the limits of catamorphisms, and address these limits with paramorphisms and apomorphisms.*

By “meat of the paper”, I mean “the first two pages”. Have patience.↩

In other words,

`Expr`

is an inductively-defined data type of kind`* -> *`

.↩Packages like compdata provide Template Haskell magic to avoid the syntactic clutter associated with applying the

`In`

constructor everywhere: given our above definition of`Expr`

, we could use the`smartConstructors`

splice to generate`iLiteral`

,`iIdent`

,`iUnary`

, etc. functions, each of which are straightforward compositions of the constructors of`Expr`

with the`In`

fixed-point operator.↩The purists in the audience are no doubt cringing at my use of “container” to describe the capabilities of a

`Functor`

. As the Typeclassopedia points out,`Functor`

s are broader than just containing values: the best phrase for a`Functor f => f a`

is “a value`a`

within some computational context`f`

”. That doesn’t exactly roll off the tongue, though, so I will be using ‘container’ throughout. Sorry, purists. (But I already lost you with my hand-wavy treatment of least-fixed-points and codata last time.)↩Digression: Some of you may be wondering “if the catamorphism applied to lists is equivalent to

`foldr`

, what’s the analogous construct for`foldl`

?” This is somewhat of a trick question, as`foldl`

can be expressed in terms of`foldr`

, as Oleg demonstrates.↩

Because nested structures appear in almost every problem domain and programming environment, from databases to 3D graphics to filesystems, the act of iterating through these structures is common, so common that most programmers barely notice when they’re doing it. As such, generalizing the act of recursive traversals provides immediate real-world benefits: our new generalized traversal can replace a host of type-specific traversal functions. In addition, by decoupling *how* a function recurses over data from *what* the function actually does, we reduce cognitive overhead and can focus entirely on the core behavior of our recursive functions. No matter the structures in question—lists, directory hierarchies, control flow graphs, database records—recursion schemes bring us an orderly and predictable way to traverse them. In addition, recursion schemes aren’t a product of any one programming language or environment—you can express recursion schemes in any language with first-class functions. Clojure, for example, uses them to power its clojure.walk API for generically traversing s-expressions and maps.

Meijer et. al go so far as to condemn functional programming without recursion schemes as morally equivalent to imperative programming with `goto`

. While comparisons to Djikstra’s infamous letter to the ACM are often inane, the analogy is apt: just as using `while`

and `for`

loops rather than `goto`

brings structure and harmony to imperative control flow, the use of recursion schemes over hand-written brings similar structure to recursive computations. This insight is so important that I’ll repeat it: *recursion schemes are just as essential to idiomatic functional programming as for and while are to idiomatic imperative programming*.

I’ve chosen to express the ideas in *Bananas, Lenses, Envelopes and Barbed Wire* in Haskell, though the paper was written years before Haskell came to prominence^{1}. If you don’t know Haskell very well, **don’t panic**: you don’t need to be a Haskell whiz to understand the ideas presented here. I assume only a basic familiarity with Haskell syntax and the use of algebraic data types. I’m going to rely on a few idioms to better illustrate the concepts underlying recursion schemes—when I do, I will explain what happens behind the scenes. If you’re wholly unfamiliar with Haskell, you may want to dip into the first few chapters of Learn You a Haskell.

I’ll start with the simplest way to represent a well-typed syntax tree, then show how that simplicity makes it difficult to write a function that generically traverses and modifies trees. I’ll then redefine our syntax tree so as to take advantage of existing Haskell idioms and the expressive power of parameterized data types. Finally, I’ll show how recursion schemes emerge naturally when we express step-by-step descriptions of recursion patterns with common Haskell idioms.

Let’s take a look at the simplest way to represent a syntax tree in Haskell: an ordinary algebraic datatype.

```
data Lit
= StrLit String
| IntLit Int
| Ident String
deriving (Show, Eq)
data Expr
= Index Expr Expr
| Call Expr [Expr]
| Unary String Expr
| Binary Expr String Expr
| Paren Expr
| Literal Lit
deriving (Show, Eq)
data Stmt
= Break
| Continue
| Empty
| IfElse Expr [Stmt] [Stmt]
| Return (Maybe Expr)
| While Expr [Stmt]
| Expression Expr
deriving (Show, Eq)
```

This is a perfectly adequate syntax tree: it’s simple, straightforward, and works nicely with parsing libraries such as attoparsec or Peggy. Yet writing a function that operates on a `Expr`

node and all its subexpressions is a tedious exercise indeed: here’s an example that flattens an `Expr`

, recursively removing all `Paren`

nodes:

```
-- this would turn the expression
-- (((anArray[(10)])))
-- into
-- anArray[10]
flatten :: Expr -> Expr
-- base case: do nothing to literals
flatten (Literal i) = Literal i
-- this is the important case: we shed the Paren constructor and just
-- apply `flatten` to its contents
flatten (Paren e) = flatten e
-- all the other cases preserve their constructors and just apply
-- the flatten function to their children that are of type `Expr`.
flatten (Index e i) = Index (flatten e) (flatten i)
flatten (Call e args) = Call (flatten e) (map flatten args)
flatten (Unary op arg) = Unary op (flatten arg)
flatten (Binary l op r) = Binary (flatten l) op (flatten r)
```

This code is oppressive, ugly, and unmaintainable. Four out of this function’s six lines are dedicated to the simple yet tedious task of ensuring that `flatten`

propery recurses into its argument’s subexpressions—not only is this boring to write, but any future changes (such as added constructors or fields) to `Expr`

will force us to rewrite it. (I’ll refer to recursion written in this style as *explicit recursion*, in contrast with the implicit recursion provided by recursion schemes.) In addition, it’s extremely easy to make mistakes in this definition—the syntatic noise that the primitive recursion introduces renders it hard to spot a missing recursive invocation of `flatten`

, yet even one such omission introduces a critical bug.

We can, however, bring some sanity to this madness by writing a function `apply`

that, given a function `f`

operating on `Expr`

s, applies `f`

to each subexpression of a given `Expr`

:

```
applyExpr :: (Expr -> Expr) -> Expr -> Expr
-- base case: applyExpr is the identity function on constants
applyExpr f (Literal i) = Literal i
-- recursive cases: apply f to each subexpression
applyExpr f (Paren p) = Paren (f p)
applyExpr f (Index e i) = Index (f e) (f i)
applyExpr f (Call e args) = Call (f e) (map f args)
applyExpr f (Unary op arg) = Unary op (f arg)
applyExpr f (Binary l op r) = Binary (f l) op (f r)
```

By separating out the act of recursing over subexpressions, we can reduce our six-line definition of flatten to two lines. In the body of `flatten`

, we need only specify that `Paren`

nodes be treated differently than other nodes, relying on the `applyExpr`

function to take care of recursion for us:

```
flatten (Paren e) = flatten e
flatten x = applyExpr flatten x
```

This function just got far, far easier to write and maintain. The `apply`

function is now responsible for both the base case and the simple recursive case of flattening an expression: all we have to do is define the interesting case, i.e. its handling of `Paren`

nodes. *Awesome.*

But let’s not get ahead of ourselves. We haven’t really prevented any boilerplate or eliminated room for bugs here: `applyExpr`

just contains and isolates the boilerplate, and we’d need to write a new `apply`

function for each and every new type we define. A sufficiently smart compiler could write them for us. And GHC, being a very smart compiler, can. First, though, we’ll have to make this `Expr`

data type a little bit more general.

```
data Expr a
= Index a a
| Call a [a]
| Unary String a
| Binary a String a
| Paren a
| Literal Lit
deriving (Show, Eq)
```

This new definition of `Expr`

is identical to our previous one, except here we’ve added a type variable `a`

and replaced all recursive occurrences of the `Expr`

type with it. Put another way, we have *parameterized* this type in terms of its subexpressions. As such, we have to change our definition of `applyExpr`

: the function we apply to each subexpression can no longer be of type `Expr -> Expr`

, but must become `a -> a`

: indeed, we can make it `a -> b`

, letting the function change the type of an `Expr`

’s subexpressions if necessary.

`apply :: (a -> b) -> Expr a -> Expr b`

The sharp-eyed among you will notice how similar this function is to the built-in `map`

function over lists:

```
-- `map` takes a function (a -> b) and makes it operate on lists containing 'a's
map :: (a -> b) -> [a] -> [b]
```

This is not a coincidence: in fact, the `apply`

function is exactly analogous to `map`

for lists—you can think about both functions as mapping or promoting a function `f`

so as to operate on a larger datatype, whether that’s an `Expr`

type or a list (`[]`

) type. This pattern of mapping is so common that its generalized version is a central Haskell concept: the typeclass `Functor`

represents all the types that provide a `map`

-like function, called `fmap`

^{2}:

```
class Functor f where
fmap :: Functor f => (a -> b) -> f a -> f b
```

Countless datatypes—lists, trees, optional (`Maybe`

) values, IO actions, even functions themselves—implement the `Functor`

typeclass. Indeed, it’s so common, and implementing `fmap`

is usually so straightforward, that GHC provides a built-in mechanism to write the definition of `fmap`

for you: we can just add `Functor`

to the list of classes our `Expr`

declaration derives, along with `Show`

and `Eq`

:

```
{-# LANGUAGE DeriveFunctor #-}
data Expr a
= Index a a
| Call [a]
| Unary String a
| Binary a String a
| Paren a
| Literal Lit
deriving (Show, Eq, Functor) -- fmap for free
```

In addition, you can derive instances of the `Foldable`

and `Traversable`

typeclasses, which provide dozens of of useful functions to access and iterate through an `Expr`

’s subexpressions—in essence, `Expr`

now comes with batteries included. Parameterizing `Expr`

and deriving `Functor`

, `Foldable`

, and `Traversable`

provides us with an embarrassment of helper functions—but this parameterized version of `Expr`

isn’t quite the same as our previous defintion!

Our first formulation of `Expr`

, since its recursive subfields were of type `Expr`

, could represent arbitrarily-nested `Expr`

s, but this new one can’t—it seems like we always have to insert `Lit`

—to establish the maximum possible depth of a tree of `Expr`

s:

`Expr Lit`

represents an expression with no subexpressions`Expr (Expr Lit)`

represents expressions with at most one more layer of subexpressions.`Expr (Expr (Expr Lit))`

represents two-level expressions, and so on, and so forth.

In order for the parameterized definition of `Expr`

to be equal to our original formulation, we have to assume that there exists a type such that, when substituted for `a`

in the definition of `Expr a`

, yields an expression with arbitrarily-nested `Expr`

subexpressions.

`type NestedExpr = Expr (Expr (Expr (Expr …)))`

But in order for our assumption about the type variable `a`

to hold true, we need some sort of trick that allows us to represent, in a finite manner, a representation of the type of arbitrarily-nested `Expr`

s.

Consider the Y-combinator. Given a function f that takes one argument, `y(f)`

represents the result of repeatedly applying `f`

to itself:

`y(f) = f(f(f(f(f ...))))`

The sharp-eyed will have noticed that the expansion of `y(f)`

is very similar to our `NestedExpr`

type above. If we have a Y-combinator embedded entirely *in the type system*, we can describe the repeated application of `Expr`

to itself, in a manner identical to how the value-level Y-combinator operators on functions, and in turn we can describe an `Expr a`

where `a`

represents arbitrarily-nested `Expr`

s.

`type Y t = t (t (t (t (t ...))))`

This general concept^{3} is known as ‘fixed-point’: we say that `y(f)`

is the fixed point (or fixpoint) of the `f`

function, and that `Y Expr`

is the *fixed point of the Expr functor*. And here’s the kicker—we can build a Y-combinator that works

`Expr`

’s subexpressions.We need a data type `Y`

that, when given another type `f`

, wraps an `f`

whose children are of type `(Y f)`

. Let’s call it `Term`

, and let’s call its constructor `In`

, representing the fact that we are stuffing one level of recursion into a fixed form. In addition, we’ll define an `out`

function that unwraps a `Term`

.

```
data Term f = In (f (Term f))
out :: Term f -> f (Term f)
out (In t) = t
```

It’s illuminating to substitute `Expr`

in for the type variable in the above definition:

```
Term Expr = In (Expr (Term Expr))
out :: Term Expr -> Expr (Term Expr)
```

From this definition, we can see that, given a `Term Expr`

, we can use the `out`

function to convert it to an `Expr`

the subexpressions of which are, in turn `Term Expr`

s. That means that we can unwrap a `Term Expr`

into an *arbitrarily-nested* `Expr`

through successive applications of `out`

: our `Term Expr`

can expand into an `Expr (Term Expr)`

, which can expand into an `Expr (Expr (Term Expr))`

, and so on and so forth. This style of defining recursive types using fixed-points of functors is an example of *codata*. A full discussion of the theory behind codata (and the many different forms that codata can take) is, unfortunately, beyond the scope of this article; I recommend this excellent introduction.

At this point, we’re well grounded in defining our data types with fixed-points of functors. Let’s do something awesome with them.

Consider the notion of the bottom-up traversal: specifically, let’s write pseudo-English instructions for traversing the fixed-point of a functor:

```
To traverse a Term bottom-up with a function ƒ:
1. Unpack the term so as to access its children.
2. Recursively traverse each child of the unpacked term with ƒ.
3. Repack the term.
4. Apply ƒ to it.
```

We have the tools to express each step of this procedure—let’s call it `bottomUp.`

`bottomUp :: Functor a => (Term a -> Term a) -> Term a -> Term a`

Given a function `fn`

from `Term`

s to `Term`

s, we’ll unpack the `Term`

with the `out`

function, recursively traverse each child of the unpacked term with `fmap (bottomUp fn)`

, repack the term with the `In`

constructor, and then simply apply `fn`

to the result. The `fmap bottomUp`

call does all the heavy lifting in this function: it captures the act of recursing into each child (if any) of a given functor.

Rather than naming both the `fn`

function parameter and the `Term`

parameter, I’m going to define `bottomUp`

using combinators to join these four invocations—`out`

, `fmap bottomUp`

, `In`

, and `fn`

. Namely, I’m going to use the `>>>`

operator, defined in `Control.Arrow`

, for left-to-right function composition,`f >>> g x`

is equal to `g(f(x))`

. Though this style is a bit unconventional—the right-to-left function composition operator, `.`

, is more common—I’ve chosen to do this because it’s a useful visual indicator of the order in which functions are invoked. (This order will become important later.)

So now let’s write this function, gluing each element together left-to-right with the `>>>`

operator:

```
bottomUp fn =
out -- 1) unpack
>>> fmap (bottomUp fn) -- 2) recurse
>>> In -- 3) repack
>>> fn -- 4) apply
```

And there it is, our first recursion scheme. In writing `bottomUp`

we have developed a type-safe *and* type-generic combinator for recursively transforming *any* Functor: whether it’s our `Expr`

type from earlier, a list, a rose tree, or anything else. This is, frankly, kind of amazing. As such, let’s rewrite our original `flatten`

function so that it operates on `Term`

s that wrap arbitrarily-nested `Expr`

s:

```
flattenTerm :: Term Expr -> Term Expr
flattenTerm (In (Paren e)) = e -- remove all Parens
flattenTerm other = other -- do nothing otherwise
flatten :: Term Expr -> Term Expr
flatten = bottomUp flattenTerm
```

Though our previous definition of `flatten`

that used `apply`

to represent its recursion was concise, this is even more elegant: our `bottomUp`

recusion scheme lets us factor out the recursive parts of this definition entirely. We can focus on the relevant behavior of the flattening function—namely, that it removes all `Paren`

nodes—and define it in two simple clauses. In addition, recursively invoking this function with `bottomUp flattenTerm`

is clearer than our prior definitions in that we have made the bottom-up nature of this traversal explicit. This is really a remarkable departure from our previous definition of `flatten`

—it’s hard to imagine how it could be made shorter.

But let’s not rest on our laurels. Let’s consider the steps involved with writing a top-down traversal of a `Term`

, the obvious analogue to our bottom-up traversal:

```
To traverse a Term top-down with a function ƒ:
1. Apply ƒ to the term.
2. Unpack the term so as to access its children.
3. Recursively traverse each child of the term with ƒ.
4. Repack the term.
```

These instructions are elegantly symmetrical with the ones for our bottom-up traversal—if you read the instructions in reverse and replace occurrences of “unpack” and “repack”, they are identical. And here’s the kicker: our code can capture this. We can express this notion of “reading in reverse” by replacing occurrences of the left-to-right operator `>>>`

with `<<<`

, the right-to-left operator^{4}, and we swap “unpack” and “repack” with `out`

and `In`

.

```
topDown, bottomUp :: Functor f => (Term f -> Term f) -> Term f -> Term f
topDown f = In <<< fmap (topDown f) <<< out <<< f
bottomUp f = out >>> fmap (bottomUP f) >>> In >>> f
```

The fact that we can express the duality between top-down and bottom-up traversals merely by “reversing the arrows” that determine our code’s flow, all the while retaining generality and type safety, is nothing short of amazing. That these definitions emerged naturally out of fixed-points and functors, two concepts central to Haskell and to functional programming in general, is doubly amazing.

Top-down and bottom-up traversals are the simplest of recursion schemes—we’ve barely touched the surface of what *Bananas, Lenses, Envelopes, and Barbed Wire* has to offer us. In the next installment of this series I’ll explore two additional varieties of recursion schemes—and how generalizing each recursion scheme allows us to derive new, more-general schemes.

I’d like to thank everyone who read a draft of this entry, especially Nate Soares and Manuel Chakravarty. I’d also like to thank Colin Barrett, who helped me puzzle all this out over late-night Skype sessions. If you have any comments or questions, please drop me a line on Twitter.

*In part 2, we go on to define and discuss catamorphisms and anamorphisms*.

Rather than tying

*Bananas, Lenses, Envelopes and Barbed Wire*to any particular programming language, Meijer et. al used notation derived from Bird-Meertens formalism, a calculus of program construction based on recursion schemes. (Meijer’s Ph.D. thesis discussed compiler specifications using the Bird-Meertens formalism). This calculus was also known as “Squiggol”, after its “squiggly” notation. Though this notation is well-specified, its syntactic constructions, featuring elements such as “banana brackets” and “concave lenses”, is somewhat abstruse.↩You may be curious as to why Haskell provides both

`map`

and`fmap`

functions in its Prelude, considering that`map`

is just a version of`fmap`

that can only operate on lists. This has indeed been a bone of contention within the Haskell community. As Brent Yorgey, author of the essential Typeclassopedia, put it: “the usual argument is that someone just learning Haskell, when using`map`

incorrectly, would much rather see an error about lists than about`Functor`

s.”↩A complete discussion of the beauty and notability of fixed-point combinators is beyond the scope of this article: for such explorations, please refer to Raymond Smullyan’s wonderful

*To Mock a Mockingbird*or Reginald Braithwaite’s combinators.info.↩This function is provided by the Prelude with the

`.`

operator.↩