Previous installments: 1, 2, 3, 4, 4½.
Thus far, we’ve explored a myriad array of recursion schemes. Catamorphisms and anamorphisms fold and unfold data structures, paramorphisms and apomorphisms fold with additional information, and histomorphisms and futumorphisms allow us to fold using historical values
]]>Previous installments: 1, 2, 3, 4, 4½.
Thus far, we’ve explored a myriad array of recursion schemes. Catamorphisms and anamorphisms fold and unfold data structures, paramorphisms and apomorphisms fold with additional information, and histomorphisms and futumorphisms allow us to fold using historical values and unfold with userdefined control flow.
Given each fold—cata
, para
, histo
—we derived its corresponding unfold by ‘reversing the arrows’ of the fold—put another way, we computed the categorical dual of each fold operation. Given the fact that we can derive an unfold from a fold (and vice versa), and given the powerful tool in our toolbox that is function composition, an important question we can ask is “what happens when we compose an unfold with a fold?” In this entry, we’ll explore the structures generated from such compositions. (This post is literate Haskell; you can find the code here.)
Meijer et. al answered the above question in Bananas, Lenses, Envelopes, and Barbed Wire. They called this concept—unfolding a data structure from a seed value, then computing a final result by folding over the data structure thus produced —a hylomorphism^{1}. The hylomorphism is sometimes referred to as a ‘refold’, which is a slightly more approachable but not particularly illustrative name—I prefer to think of a hylomorphism as a ‘producerconsumer function’, where the unfold produces values for the fold to consume.
If you grasp the concept of a catamorphism (a fold) and an anamorphism (an unfold), a hylomorphism is easy: it’s just the latter followed by the former. The definition follows:
hylo :: Functor f => Algebra f b > Coalgebra f a > a > b
hylo alg coalg = ana coalg >>> cata alg
Pretty straightforward, right? Unfold with ana
and the provided coalgebra, then fold with cata
and the provided algebra.
The ‘hylo’ in ‘hylomorphism’ comes from the Greek hyle, ὕλη, meaning ‘matter’. The ancient Greeks used ‘matter’ to mean the substance out of which an object is formed (‘morpho‘); as such, we can read ‘hylomorphism’ as a function that forms a result object out of some intermediate, constituent matter.
Something interesting to note is that Term
, the fixed point of a Functor
, appears nowhere in the signature of hylo
. Though ana
produces and cata
consumes a Term f
, this is elided in the type signature, a hidden detail of the implemementation: all that is necessary is a Functor
instance to parameterize the algebra and coalgebra. (Of course, your input a
or your output b
could be a Term
over some Functor
. But it doesn’t have to be.) Similarly, Kmett’s formulation of hylo makes no Base
functor visible.
hylo
The hylomorphism is more than an elegant result—it generalizes many computations that we as programmers encounter in our daytoday work. The canonical example is the factorial function, but an abstraction that encapsulates building then collapsing a data structure is far more useful than yet another cute way to compute fac(n)
. Though we often don’t notice the underlying generality, we’re using hylomorphisms every time we:
aggregate and compute properties of data structures, e.g. determining the mean or median or outliers present in a set of numeric data;
interpret or compile a final result from some textual representation of a nested structure;
apply recursive divideandconquer techniques, e.g. quicksort, mergesort, or the fast Fourier transform;
determine differences between data structures, e.g. edit distance or Levenshtein distance over strings.
Let’s put hylo
to work. We’ll build a RPN calculator with hylo
. Given the string + 1 2
, our calculator should compute 1 + 2
, and given 2 1 12 3 /  +
it should calculate (2 + 1)  (12 / 3)
: every RPN postfix expression has one unambiguous parse, obviating the need for parentheses associated with infix operators. Our coalgebra will unfold a list of operations from a seed (a string), producing a list of numbers and operators, and the algebra will consume the generated list, ultimately yielding a stack of numbers.
As I just mentioned, the input to an RPN calculator consists of two kinds of values: mathematical operations (addition, multiplication, &c.) and integer literals. We’ll define a Token
datatype upon which our calculator will operate:
data Token
= Lit Int
 Op (Int > Int > Int)
Note that our Op
constructor contains a binary function Int > Int > Int
, rather than a string representation of the relevant operation. While this precludes a Show
instance for Token
, since functions have no meaningful string representation at runtime, it will simplify the implementation: when we parse an Op
, we’ll store the Haskell function that corresponds to the operator, so that when we perform computations we need only call the stored function with the arguments present on the stack.
We need to be able to read a Token
out of a string. If we were more principled and honest people, we would use a parsing library like megaparsec
or trifecta
, or even a Maybe
monad to represent parse failures—but in an effort to keep things simple, let’s make this function pure using read
, which fails at runtime if someone decides to get saucy and provide invalid data.
parseToken :: String > Token
parseToken "+" = Op (+)
parseToken "" = Op ()
parseToken "*" = Op (*)
parseToken "/" = Op div
parseToken num = Lit $ read num
Nothing too difficult here. We patternmatch on a given string; given a mathematical operator, we return an Op
containing the corresponding Haskell function; otherwise, we use read
to yield an Int
and wrap it in a Lit
.
The easiest way to represent a LIFO stack in Haskell is with a list: we push with a cons operator (:
) and pop by dropping the first item in the list (tail
). As such, we’ll need a Term
compatible (parameterized) list type. Though last time we explored how the Base
type family allows us to use Haskell’s []
list type with recursion schemes, we’ll roll our own here.
data List a b
= Cons a b
 Nil
deriving (Show, Eq, Functor)
Now we have a Token
type to operate on and a List
type to store tokens. Our next objective is to define a coalgebra that builds a List
of Token
s from a String
. Remember the definition of coalgebras from part II:
type Coalgebra f a = a > f a
The seed value a
will be a String
, while the container type f
will be List Token
. We’ll write the type signature of our coalgebra now:
parseRPN :: Coalgebra (List Token) String
Keep in mind that List Token
here is partiallyapplied, as List
has three arguments, being of kind * > * > *
. If we were to expand the f a
, we would yield the type List Token String
:
parseRPN :: String > List Token String
This makes sense. In each step of our unfold we return a List value containing a Token
value and the remaining String
that we have yet to parse, unless the result is Nil
, at which point we stop unfolding, yielding the list. Because Nil
contains no children of type a
or b
, an occurrence of Nil
can assume whatever type we need them to be—here Token
and String
.
Now let’s implement the body of rpn
. The simplest case handles the empty string: if there’s no more input to parse, we terminate the unfold by returning Nil
. (ana
knows to stop unfolding if it encounters Nil
because the recursive fmap
calls will cease: Nil
contains no child nodes into which to recurse.)
parseRPN "" = Nil
The case for a nonempty string is more interesting. Given a string str
, we take as many characters from it as we can, until we encounter a space. We then pass that chunk into parseToken
, sticking its result into the a
field of Cons
, then drop all spaces in the remainder of the string and stick it into the b
field of the Cons
. We’ll use Haskell’s span
function to do that, which takes a predicate and returns a tuple containing the items that satisfy the predicate and those that don’t.
parseRPN str = Cons token newSeed
where (x, rest) = span (not . isSpace) str
token = parseToken x
newSeed = dropWhile isSpace rest
Let’s look at the function all together:
parseRPN :: Coalgebra (List Token) String
parseRPN "" = Nil
parseRPN str = Cons token newSeed
where (x, rest) = span (not . isSpace) str
token = parseToken x
newSeed = dropWhile isSpace rest
Not too shabby! Six lines of code, two cases, no compiler warnings. (And this would be even cleaner if we used an actual parser.) If we run ana parseRPN
with 3 4 +
as a seed value, we yield a result equivalent to the list Lit 3, Lit 4, Op +, Nil
.
It’s time to write our evaluator. Let’s consult the definition of an Algebra
:
type Algebra f a = f a > a
Our container type f
will be, as in parseRPN
, a List Token
. But our result type a
will differ: rather than operating on strings, we want a stack of integers to which we can append (with Lit
) and upon which we can operate (with Op
). Let’s make a type alias:
type Stack = [Int]
And now we can set down a type signature for our evaluator:
evalRPN :: Algebra (List Token) Stack
But here we encounter a dilemma! Given a reversePolish expression: 2 3 +
or 4 2 5 * + 1 3 2 * + /
, we need to compute the result lefttoright, pushing literals onto the stack and performing the operations we find on the values in the stack. This means our evaluator must work from the left (in the manner of foldl
) rather than from the right (a la foldr
). But our old friend cata
is a right fold—it travels all the way to the Nil
at the end of the list and then propagates its result from the right. How do we work around this, given that hylo
provides us no opportunity to reverse the parsed list of tokens (an admittedly kludgy fix)?
The answer is simple—our result type will not be an ordinary Stack
value. We will instead use a function that takes and returns a Stack
: Stack > Stack
. The ultimate result of this catamorphism will be such a function—we kick off the computation by invoking it with an empty stack. Since the leftmost element was evaluated most recently, the aggregated function will operate on the leftmost element first. Further invocations will operate on each subsequent item, lefttoright, until we encounter the Nil
element and cease computation. And, conveniently, the value we provide to this function at the toplevel will be the initial stack that this calculator uses.
If this is difficult to visualize, the following diagram may help:
The fact that we can transform cata
, a rightward fold, into a leftward fold by switching from computing a value to computing a function on values is utterly staggering to me. By adding the most fundamental concept in functional programming—a function—we yield additional power from cata
, the lowliest of recursion schemes. This strategy is a wellknown idiom in the functionalprogramming world: this stack is an example of a ‘difference structure’, similar to the difference list that is used in Haskell’s Show
construct.
Let’s rewrite evalRPN
to use Stack > Stack
as its carrier type:
evalRPN :: Algebra (List Token) (Stack > Stack)
That looks right. Our algebra takes a list of tokens and returns a function that takes and returns a stack. When hylo
completes, we’ll yield such a function; the value that we provide to that function will be used as the initial stack. To check our assumptions, we can expand the definition of evalRPN:
evalRPN :: List Token (Stack > Stack) > (Stack > Stack)
When folding over a list, we need to consider two cases: Nil
and Cons
. The Nil
case falls out quite easily: we simply return the identity function, as there is no data with which we would modify a passedin stack.
evalRPN Nil stack = stack  aka `id`
Though we are technically returning a function from evalRPN
, Haskell allows us to write this function in a more beautiful way: rather than returning an explicit function λstack > stack
, we can move that stack
argument into the parameter list of evalRPN
^{2}.
Now let’s handle the case of adding a new value onto the stack. Our Cons
constructor provides two values: a Lit
that contains an integer, and our accumulator/carrier type, a ‘difference function' from Stack
to Stack
. We’ll call that cont
, since we’ll continue evaluation by invoking it. (If, for some reason, we wanted to terminate early, we would return a function that did not invoke the difference function.) As such, evalRPN
will take a stack, push the integer from the Lit
value onto that stack, and invoke cont
to continue to the next stage:
evalRPN (Cons (Lit i) cont) stack = cont (i : stack)
The case of applying a function to the stack is similar, except we have to introspect the top two values so as to have some operands to the provided Op
. As such, we patternmatch on the Cons
structure over which we are folding in order to pop off its top two values. We then apply those operands to the function inside the Op
, append that value to the stack, and invoke cont
to proceed to the next stage.
evalRPN (Cons (Op fn) cont) (a:b:rest) = cont (fn b a : rest)
evalRPN _ stack = error ("too few arguments on stack: " <> show stack)
If there are too few values on the stack, we call error
to bail out^{3}. After applying the function contained in the Op
value to these two values, we append the result of this function to the remainder of the list, then call the difference function to proceed to the next computational stage.
Let’s take a look at the evalRPN
function, assembled in one place:
evalRPN :: Algebra (List Token) (Stack > Stack)
evalRPN Nil stack = stack
evalRPN (Cons (Lit i) cont) stack = cont (i : stack)
evalRPN (Cons (Op fn) cont) (a:b:rest) = cont (fn b a : rest)
evalRPN _ stack = error ("too few arguments on stack: " <> show stack)
I find this a lovely definition: it shows clearly that evaluation terminates in the Nil
case, and continues in the Cons
cases by virtue of invoking the carried cont
function.
Now we have a coalgebra (the parser) and an algebra (the evaluator, in differencefunction style). Let’s put it all together—we can start by interrogating GHCi as to the type of passing these to hylo
.
λ> :t hylo evalRPN parseRPN
hylo evalRPN parseRPN :: String > Stack > Stack
That makes sense: the String
parameter is our input, and the Stack
parameter is the initial value of the RPN machine’s stack. So now we can build a toplevel rpn
function that takes a string, invoking the result of hylo
with the provided string and an empty initial stack:
rpn :: String > Stack
rpn s = hylo evalRPN parseRPN s []
We can test this by evaluating it in GHCi:
λ> rpn "15 7 1 1 +  / 3 * 2 1 1 + + "
[5]
Dope.
Though an RPN calculator isn’t enormously complicated, I’d argue that our implementation demonstrates the virtue of recursion schemes: by separating what we’re doing from how we’re doing it, we draw attention to the meat of the problem—parsing from a string and operating on a stack—without concerning ourselves with the details of aggregating data from an input string or iterating over a parsed sequence of tokens. The machinery of unfolding and folding is all contained within hylo
: all we have to worry about is the core of our problem. And that’s pretty remarkable.
We don’t need to invoke cata and ana explicitly to build a hylomorphism. We can build hylo
just out of the algebra and coalgebra itself.
hylo' :: Functor f => Algebra f b > Coalgebra f a > a > b
hylo' alg coalg = coalg >>> fmap (hylo' alg coalg) >>> alg
Though this definition is arguably less indicative of the fact that a hylomorphism is the composition of an an anamorphism and catamorphism, it bears a compelling property: it entails half as many calls to fmap
as does the previous definition.
Our original hylo
unfolded our List
to its maximum extent, entailing O(n) calls to fmap
, where n is the number of tokens passed to rpn
. Subsequently, that structure is torn down with cata
, using an additional O(n) calls to fmap. In contrast, this new definition of hylo
only recurses O(n) rather than O(2n) times: as soon as the unfolding completes and the recursive fmap
invocations bottom out, each level of the structure is passed directly to alg
as the stack unwinds. This is a significant optimization, especially for deeplynested structures!
Though Meijer et al. introduced the hylomorphism along with the catamorphism and anamorphism, Uustalu and Vene’s paper does not mention what happens when you compose a histomorphism and futumorphism. It appears to have taken until roughly 2008 (nine whole years!), when Edward Kmett and the #haskell IRC channel dubbed it the chronomorphism—chrono (χρόνος) being the prefix related to time.
The definition of the chronomorphism follows from that of the hylomorphism:
chrono :: Functor f => CVAlgebra f b > CVCoalgebra f a > a > b
chrono cvalg cvcoalg = futu cvcoalg >>> histo cvalg
Pretty straightforward: futu
unfolds a structure multiple layers at a time (thanks to the power of the free monad), and histo
tears it down.
Unfortunately, coming up with a useful example of chronomorphisms is a bit more difficult than that of a hylomorphism. The plantgrowing example in part IV of this series comes close—we used a futumorphism to generate plant life, but only used a catamorphism, rather than a histomorphism, to render the resulting plant. We could have expressed that catamorphism as a histomorphism, as we showed when we implemented cata
in terms of histo
, but bringing in the power of histomorphisms and not using them is pretty pointless. I haven’t been able to find a useful or illustrative of chrono
in action (if you know of one, get in touch!) but I at least have the reassurance that its discoverer himself can’t think of one either. chrono
can, however, be used to implement the dynamorphism, a scheme specialized towards solving dynamic programming problems, which we will discuss in future installments. (It’s possible that Uustalu and Vene neglected to mention the chronomorphism for precisely this reason—it’s hard to find a truly compelling use case for it.)
Histomorphisms are useful: building up and then collapsing some intermediate structure is a pattern worth abstracting, as separating ‘what’ from ‘how’ always gains us some degree of insight into our code. But in practice, this process of construction and destruction is often interrupted. Perhaps, during the construction of our intermediate structure, we determine that the input data violates our assumptions, requiring us to terminate the construction early; perhaps, during destruction, we enter an optimizable state that allows us to skip future destruction steps.
While we could use failure monads over hylo
to represent these patterns, a paper by Jiří Adámek, Stefan Milius, and Jiří Velebil, entitled Elgot Algebras, provides us with a categorytheoretical treatment of this pattern, avoiding the hornet’s nest that is impurity. Named after Calvin Elgot, an American mathematician who worked for many decades in the intersection between software engineering and pure mathematics, Elgot algebras and coalgebras generalize hylomorphisms, catamorphisms, and apomorphisms in a manner both elegant and useful. The paper itself is extremely dense, but Kmett, as per usual, has done the community a great service in translating it to Haskell.
Let’s consider the type signature of a hylomorphism. Rather than just repeat our first type signature, let’s look at hylo
after we expand the Algebra
and Coalgebra
type synonyms.
hylo :: Functor f => (f b > b) > (a > f a) > a > b
This tells us, given a Fcoalgebra over a
and an Falgebra over b
, how to get from an a
to a b
. But what if we could take a shortcut? If, in our coalgebra (the ‘construction’ function), we could shortcircuit the whole hylomorphism, returning a plain b
value, we could provide this refold function with an escape hatch—without having to worry about the semantics of Maybe
or Either
or Except
or whatever failure monad we would use with plain hylo
.
To allow this, our coalgebra, a > f a
, has to be able to return one of two values—an f a
, which continues the unfold, or a b
, shortcircuiting it. Haskell provides us a mechanism to return one of two values, of course: the trusty Either
type. Changing our coalgebra to return an Either
type yields us with the type signature for Elgot
, the Elgot algebra:
elgot :: Functor f => Algebra f b > (a > Either b (f a)) > a > b
We’ll use an auxiliary functions to define Elgot algebras: 
(pronounced ‘fanin’). It is an infix form of the either
helper function: given two functions, one of type b > a
and the other of type c > a
, it creates a function that takes Either
a b
or a c
and returns an a
.
() :: (b > a) > (c > a) > (Either b c > a)
Reading 
as ‘or’ can be a helpful mnemonic: we can see that f  g
returns a function that uses f
or g
.
Defining elgot
follows straightforwardly from the above optimized definition of hylo
. We begin by invoking our coalgebra. If we get a Right
value out of it, we recurse into it, eventually passing this layer of the computation on to our coalgebra—in other words, it behaves like a normal call to hylo
. But if we get a Left
value, we just stop, performing no operation on the value contained therein.
elgot :: Functor f => Algebra f b > (a > Either b (f a)) > a > b
elgot alg coalg = coalg >>> (id  (fmap (elgot alg coalg) >>> alg))
Let’s use an Elgot algebra to bring some sense of safety to our above RPN calculator. Calling error
on invalid input is a bad look: this is Haskell, and we can do better. Let’s start by writing a custom type to represent success and failure.
data Result
= Success Stack
 ParseError String
 TooFewArguments Stack
deriving (Eq, Show)
As with the previous incarnation of this function, we’ll use differencefunction style, but instead of a function over Stack
s, the function will handle Result
s. We’re gonna be mentioning functions of type Result > Result
a few times here, so we’ll make a type alias for it.
type Cont = Result > Result
We’ll start by rewriting parseToken
. Rather than returning a plain Token
and failing at runtime if provided an invalid numeric value, we’ll use readMaybe
to yield a Maybe Int
, returning an Either
that contains an earlytermination function over Result
s or an integer wrapped by a Lit
constructor
safeToken :: String > Either Cont Token
safeToken "+" = Right (Op (+))
safeToken "" = Right (Op ())
safeToken "*" = Right (Op (*))
safeToken "/" = Right (Op div)
safeToken str = case readMaybe str of
Just num > Right (Lit num)
Nothing > Left (const (ParseError str))
Similarly, we rewrite parseToken
to invoke safeToken
. The do
notation provided by Haskell beautifies the nonemptystring case, binding a successful parse into the parsed
result when we encounter a Right
value and implicitly terminating should safeToken
return Left
, the failure case.
safeParse :: String > Either Cont (List Token String)
safeParse "" = return Nil
safeParse str = do
let (x, rest) = span (not . isSpace) str
let newSeed = dropWhile isSpace rest
parsed < safeToken x
return $ Cons parsed newSeed
To tie all this together, we rephrase the definition of safeEval
. We have to make our patternmatching slightly more specific—we have to match on Success
values to get a stack out of them—but we can also remove the call to error
in this function. When handling an arithmetic operation, if there are too few values on the stack to proceed, we call the difference function with a TooFewArguments
value
safeEval :: Algebra (List Token) Cont
safeEval (Cons (Lit i) cont) (Success stack) = cont (Success (i : stack))
safeEval (Cons (Op fn) cont) (Success s) = cont (case s of
(a:b:rest) > Success (fn b a : rest)
_ > TooFewArguments s)
safeEval _ result = result
That’s two uses of error
removed—a victory in the struggle against partial functions and runtime crashes! Furthermore, the error handling becomes tacit in the definition of safeParse
: no case statements or calls to throw
are required, as the donotation over Either
handles the Left
case for us.
Invoking these functions is just as simple as it was when we used hylo
. We replace hylo
with elgot
, and pass an empty Success
value to evaluate the difference function lefttoright over the provided string.
safeRPN :: String > Result
safeRPN s = elgot safeEval safeParse s (Success [])
Other examples of using Elgot algebras are few and far between, but the excellent Vanessa McHale has an example of them on her blog, in which she uses them to calculate the Collatz sequence of a provided integer, yielding performance comparable to an imperative, lowerlevel Rust implementation.
In the defintion of elgot
above, we used 
to handle the Either case: in performing id
(no operation) on a Left
value and recursing on a Right
value, we gained a clarity of definition—but more importantly, we make it easy to reverse the arrows. Every time we reverse the arrows on a fold, we yield the corresponding unfold: but here, reversing the arrows on an Elgot coalgebra, we yield a hylomorphism that can shortcircuit during destruction, rather than construction.
We know how to reverse most of the operations in the above definition: alg
becomes coalg
and vice versa, >>>
becomes <<<
and vice versa, and id
stays the same, being its own dual. The 
may be slightly less obvious, but if we remember that the tuple value ((a, b)
) is dual to Either a b
, we yield the &&&
operator, pronounced ‘fanout’:
(&&&) :: (a > b) > (a > c) > (a > (b, c))
Whereas 
took two functions and used one or either of them to deconstruct an Either
, &&&
takes two functions and uses both of them to construct a tuple: given one of type a > b
and the other of type a > c
, we can apply them both on a given a
to yield a tuple of type (b, c)
. Again, reading the tripleampersand as ‘and’ can be a useful memonic: f &&& g
returns a function that uses both f
‘and’ g
.
Now we know how to reverse every operation in elgot
. Let’s do so:
coelgot alg coalg = alg <<< (id &&& (fmap (coelgot alg coalg) <<< coalg))
Feeding this into GHCi and querying its type yields the following lovely signature:
coelgot :: Functor f => ((a, f b) > b) > (a > f a) > a > b
Our algebra, which previously took an f b
, now takes a tuple—(a, f b)
. That a
is the same a
used to generate the f b
we are examining. The ‘shortcut’ behavior here is slightly more subtle than that present in the definition of elgot
—it depends on Haskell’s callbyneed semantics. If we never observe the second element of the tuple—the f b
—it will never be evaluated, and as such neither will any of the computations used to construct it!
By replacing a > f a
with its natural type synonym, Coalgebra
, we yield a unified definition of coelgot
.
coelgot :: Functor f => ((a, f b) > b) > Coalgebra f a > a > b
coelgot alg coalg = alg <<< (id &&& (fmap (coelgot alg coalg) <<< coalg))
We can think of Elgot algebras as a hylomorphism built out of an RCoalgebra
and an Algebra
. Dually, we can think of Elgot coalgebras as hylomorphisms built out of an RAlgebra
and a Coalgebra
. We can also build a more powerful hylomorphism out of both an RAlgebra
and RCoalgebra
:
rhylo :: Functor f => RAlgebra f b > RCoalgebra f a > a > b
rhylo ralg rcoalg = apo rcoalg >>> para ralg
As far as I can tell, this construction (though it is not particularly groundbreaking) hasn’t been named in the literature before—if you know its name, drop me a line. I refer to it as an “Rhylomorphism”, but I like Rob Rix’s term for it, the “hypomorphism”, a clever amalgam of its component parts. I leave the deforestation stage, analogous to hylo
, as an exercise for the reader.
As always, I would like to thank Manuel Chakravarty for his patience and kindness in checking this series for accurately. Colin Barrett, Ross Angle, and Scott Vokes also provided valuable feedback.
If you Google ‘hylomorphism’, the results will be almost exclusively concerned with Aristotle’s philosophical theory of the same name. Though Aristotle’s concept is not particularly relevant to the study of recursion schemes, we’ll discuss why this name is appropriate for the computation that our hylomorphism performs.↩
Put another way, Haskell makes no syntactic distinction between the types a > (b > c)
and a > b > c
.↩
We could ensure that there are always sufficient values on our stack: if our calculator is initialized with an infinite list for a stack (such as [0, 0..]
, an infinite sequence of zeroes), we could omit the error case.↩
In an effort to publish more than one blog post a year, I’ve decided to write about smaller topics. Today I’m going to talk about the notion of a ‘base functor’, and how the popular recursionschemes library uses base functors to make
]]>In an effort to publish more than one blog post a year, I’ve decided to write about smaller topics. Today I’m going to talk about the notion of a ‘base functor’, and how the popular recursionschemes library uses base functors to make recursion schemes more elegant and ergonomic in practice.
Throughout this series of posts, we’ve seen the pattern of parameterizing our data types in terms of a recursive type variable. In the first installment, we went from this:
data Expr
= Index Expr Expr
 Call Expr [Expr]
 Unary String Expr
 Binary Expr String Expr
 Paren Expr
 Literal Int
deriving (Show, Eq)
to this—the same data type, but of kind^{1} * > *
, with all recursive occurrences of the Expr
type replaced with the type variable a
:
data ExprF a
= Index a a
 Call a [a]
 Unary String a
 Binary a String a
 Paren a
 Literal Int
deriving (Show, Eq, Functor)
We then used the Term
trick, a Ycombinator for the type system, to parameterize ExprF
in terms of itself, yielding a data type equivalent to the original Expr
but that can be mapped over with fmap
and folded with cata
:
newtype Term f = In { out :: f (Term f) }
type Expr = ExprF (Term ExprF)
Similarly, in part 4 we represented the natural numbers with a data type of kind * > *
:
data Nat a
= Zero
 Next a
deriving Functor
And we represented the Plant
type we grow with another such data type:
data Plant a
= Root a
 Stalk a
 Fork a a a
 Bloom
This is a good and fluent way to build data types. However, it has its disadvantages.
Consider the humble linked list, containing values of type a
: [a]
.
infixr 5 :
data [] a = a : [a]
 []
Certainly cata
, the fundamental rightfold operation, should be able to support folding over this structure: after all, it’s of kind * > *
. But if we apply Term to this data type, we run into trouble quite quickly: we lose the ability to store elements in a list. The type variable a
can only hold nested Term a
values: there is no place we can actually store list elements. This is, as you can tell, not particularly useful.
Now, of course, we can do our standard songanddance routine, converting [a]
into a type where its recursive element is replaced by a new type variable to represent recursive occurrences (the [a]
in the (:)
constructor:)
data ListF a b
= Cons a b
 Nil
deriving (Show, Eq, Functor)
This looks a little different from our prior examples—it’s of kind * > * > *
, not * > *
—but the principle is the same. We add a new type variable, here called b
, to represent recursive occurrences of the List
type. And now we can fold over a list:
listSum :: Num a => Algebra (ListF a) a
listSum (Cons a b) = a + b
listSum Nil = 0
But this is clumsy. There’s something fundamentally wrong if we have to write a replacement for the venerable []
type. Recursion schemes are meant to be elegant—manually creating alternate implementations for every recursive data type doesn’t strike me as particularly elegant. But I am, thankfully, not alone in feeling this way—the literature contains many ways to work around this. I’ll focus on the solution provided by the recursionschemes package.
The first thing you see when you open up the recursionschemes
documentation is the following type family declaration:
This understandably intimidates a number of people, especially given its lack of documentation. But this is less forbidding then it appears, and the added mental overhead is worth it—the presence of the Base
type family is one of the things that sets recursionschemes
apart from its competition in terms of easeofuse.
The purpose of the Base
type family is to tie together a standard Haskell data type—such as our original Expr
formulation, or the humble []
list—with its parameterized, “base” representation. Its definition is very concise:
type family Base t :: * > *
While a fullfledged tutorial on type families is beyond the scope of this post (the best such reference is the GHC wiki), we can think of type families as a way to write functions on the typelevel. If we were to declare a type family, and an instance of this family (analogous to an instance of a typeclass):
type family Something t
type instance Something Foo = Bar
then anywhere we encounter the invocation Something Foo
the GHC type system will resolve that to Bar
. While this may seem unnecessary—if you mean Bar
, why not just write Bar
?—it provides us a rich facility with which to associate a type with another.
Look at the definition of Base
again. The kind signature there indicates that, whenever you pass in a concrete type as the variable t
, you will yield a data type parameterized with one additional variable. This corresponds to our experience with ExprF
and List
: Expr
went from kind *
to * > *
, and [a]
went from kind * > *
to * > * > *
.
The Base
type family doesn’t tell us much on our own. The most illustrative path open to us is to look at an instance declared with Base
.
type instance Base [a] = ListF a
This declares a type family instance. Anywhere we mean to read ListF a
, we can write Base [a]
. This provides important organizational meaning: there is only one sensible parameterized implementation for any recursive type, and thus (thanks to Haskell’s support for type families) there is only one implementation of Base a
for any given type a
.
This isn’t particularly exciting on its own. The real fireworks start here, with the definition (simplified here for pedagogical purposes) of the Recursive
typeclass.
class (Functor (Base t)) => Recursive t where
project :: t > Base t t
cata :: (Base t a > a) > t > a
The Recursive typeclass is similar to the Foldable
typeclass^{2}. The analogy holds: if we define a Recursive
instance for our data type t
, whether that’s Expr
or [a]
or anything else, we can fold over this type. However, instead of providing a simple fold, we provide two functions: a project
function that takes a type t
and returns the same type but transformed into its Base
form, and a cata
function that, given an algebra from Base t a
to a
(to wit: Base t a > a
), and an initial t
value over which to fold, yields us a folded a
value.
This is, at first glance, more unwieldy than our formulation of cata
, which only involved a Functor
constraint, and nothing related to Base
functors or a new Recursive
type:
cata :: (Functor f) => Algebra f a > Term f > a
cata f = out >>> fmap (cata f) >>> f
But, critically, this formulation of cata
forces us to work with Term List
rather than the simple [a]
. However, Recursive
allows us to work with ordinary data types: rather than provide a Term t
to cata
, we give an ordinary t
. Recursive
instances use the project
function to transform the provided type into a parameterized one, then pass that transformed data type to the cata
function. As such, we can now use cata
to fold over an ordinary list, without having to wrap it in Term
s and Cons
values.
sumList :: Num a => [a] > a
sumList = cata go where
go Nil = 0
go (Cons a acc) = a + acc
Recursive
has further tricks up its sleeve. Thanks to a MINIMAL
pragma, the Recursive
class only needs an implementation of project
to implement Recursive
fully—we still get a universal cata
function for free. The implementation looks like this, if you’re interested:
class Functor (Base t) => Recursive t where
project :: t > Base t t
cata :: (Base t a > a)  ^ a (Base t)algebra
> t  ^ fixed point
> a  ^ result
cata f = c where c = f . fmap c . project
Note that the cata
function is given a default definition. If you had some magic data type that admitted a faster cata
than the default implementation, you could override it—however, I struggle to think of a type which would admit a custom cata
.
Contained inside the Recursive
class are other useful folds—para
, the paramorphism, which we discussed in part 3, and ones we haven’t covered yet—the generalized paramorphism gpara
and Fokkinga’s prepromorphism prepro
. (We will discuss these in a future installment).
Note that the Base type is constrained in Recursive instances: t
must have a Base
instance, and the Base
instance for t
must be a Functor
. Since cata
is defined in terms of a recursive invocation with fmap
, we need a useful fmap
function over any Base
instance to have a cata
that typechecks.
Thanks to the Recursive
typeclass, we can deal in simple data types—[a]
rather than ListF
, Expr
rather than ExprF
—while retaining the expressive folding power granted by paramterized data types. This is cool as hell. This technique is used in other libraries, such as José Pedro Magalhães’s regular
.
The implementation of Recursive
for [a]
follows. We convert the empty list []
into Nil
, and replace :
with the Cons
constructor.
instance Recursive [a] where
project (x:xs) = Cons x xs
project [] = Nil
Another valuable instance is one for Natural
—as we discussed in the previous installment, we can fold over the natural numbers, bottoming out when we hit zero. We built our own Nat
data type, observing that it was equivalent in definition to Maybe
—recursionschemes
just uses Maybe
for its Recursive
and Base
instance for Natural
.
type instance Base Natural = Maybe
instance Recursive Natural where
project 0 = Nothing
project n = Just (n  1)
As we’ve mentioned before, given a data type t
, the steps for constructing its Base
instance are straightforward: add a new type variable to the definition, and for each data constructor, create a new constructor with all recursive occurrences of t
replaced by the new type variable.
Thanks to the magic of Template Haskell, recursionschemes
can generate this code for us:
import Data.Functor.Foldable.TH
data Expr
= Index Expr Expr
 Call Expr [Expr]
 Unary String Expr
 Binary Expr String Expr
 Paren Expr
 Literal Lit
deriving (Show, Eq)
makeBaseFunctor ''Expr
The makeBaseFunctor
call generates code equivalent to the following:
data ExprF a
= IndexF a a
 CallF a [a]
 UnaryF String a
 BinaryF a String a
 ParenF a
 LiteralF Lit
deriving (Show, Eq, Functor)
type instance Base Expr = ExprF
instance Recursive Expr where
project (Index a b) = IndexF (project a) (project b)
project (Call a b) = CallF (project a) (fmap project b)
 and so on and so forth
This is clearly the result of applying the aforementioned algorithm to our Expr
type. To avoid name collisions, constructor names are suffixed with an ‘F’. (Infix operators are suffixed with a ‘$’).
The inclusion of these Template Haskell splices means that you, the programmer, can pick up the recursionschemes
library with a minimum of fuss and boilerplate. This is, in my experience writing Haskell in production, truly invaluable when dealing with nested data types: you can fold beautifully without setting up dozens of lines of boilerplate.
In part two of this series, we generated an unfold by ‘reversing the arrows’ in cata
. As you might be able to infer from the title of this section, we can do the same for Recursive
, which yields us a Corecursive
typeclass for unfolds:
class Functor (Base t) => Corecursive t where
embed :: Base t t > t
ana :: (a > Base t a) > a > t
We’ve already reversed the arrows and generated ana
from cata
. The only thing left to do is reverse the arrows in project
, yielding embed
—rather than going from a t
to a Base
functor, as project
does, we go from a Base
functor to a t
.
As with cata
, ana
is defined in terms of fmap
and embed
:
class Functor (Base t) => Corecursive t where
embed :: Base t t > t
ana
:: (a > Base t a)  ^ a (Base t)coalgebra
> a  ^ seed
> t  ^ resulting fixed point
ana g = a where a = embed . fmap a . g
Instances for embed
are similarly straightforward:
instance Corecursive [a] where
embed (Cons x xs) = x:xs
embed Nil = []
In practice, you won’t need to write your own Corecursive
instances, as makeBaseFunctor
creates both Recursive
and Corecursive
instances.
Particularly alert readers will notice that the definition for cata
provided by Kmett in recursionschemes
is slightly different from ours. Our definition used partial application of cata
in its definition—cata f
, being partially applied to f
, can be passed to fmap
:
cata :: (Functor f) => Algebra f a > Term f > a
cata f = out >>> fmap (cata f) >>> f
By contrast, Kmett’s cata
uses a whereclause to capture cata f
with a specific name, c
.
cata :: (Base t a > a) > t > a
cata f = c where c = f . fmap c . project
Both formulations of cata
are defined pointfree, but Kmett’s struck me as somewhat unusual— the name c
appears unnecessary, given that you can just pass cata f
to fmap
. It took several years before I inferred the reason behind this—GHC generates more efficient code if you avoid partial applications. Partiallyapplied functions must carry their arguments along with them, forcing their evaluation process to dredge up the applied arguments and call them when invoking the function. whereas bare functions are much simpler to invoke. (For more of the gory details, you can consult the GHC wiki page on the representation of heap objects).
Bearing this implementation detail in mind, this formulation of cata
is quite elegant: by naming cata f
, we can reference it not as a partially applied function, but as a regular function. Passing that function into fmap
generates more efficient code—usually this kind of microoptimization doesn’t matter much, but given that cata
is invoked on every iteration of a fold, the savings add up.
I owe thanks to Edward Kmett, whose recursionschemes
library is magnificent and inspiring, and to Austin Seipp, who checked my statements about GHC code generation for accuracy.
In the next installment, we discuss hylomorphisms, chronomorphisms, and Elgot algebras.
If you’re not familiar with the notion of a ‘kind’, you can think (loosely) about the kind of a data type t
as a measure of how many arguments it takes. Our Expr
type takes no arguments, so its kind is “star”: *
. A data type that takes one argument has kind ‘star to star’, * > *
. A data type that takes two arguments, like Either
, has kind * > * > *
. The highlevel description of a kind is ‘the type of a type’, but you can think about them as merely providing information as to the parameters taken, if any, by a data type. (The :k
directive in GHCi provides information on the kind of any type or typeclass you provide.)↩
As you can see by the name of its containing module, Data.Functor.Foldable
. This class was originally called Foldable
, but the presence of Foldable
in the standard library made the duplication unsupportable, and it was changed to Recursive
.↩
Though we’ve only just begun our dive into Bananas, Lenses, Envelopes, and Barbed Wire, the next natural step in understanding recursion schemes brings us outside its purview. We must turn our attention to a paper written seven years later—Primitive(Co)Recursion and
]]>Though we’ve only just begun our dive into Bananas, Lenses, Envelopes, and Barbed Wire, the next natural step in understanding recursion schemes brings us outside its purview. We must turn our attention to a paper written seven years later—Primitive(Co)Recursion and CourseofValue (Co)Iteration, Categorically, by Tarmo Uustalu and Varmo Vene. Primitive (Co)Recursion explores and formalizes the definition of apomorphisms (introduced first by Meijer et. al, and which we discussed, briefly, in the previous installment) and describes two new recursion schemes, the histomorphism and the futumorphism.
Primitive (Co)Recursion is a wonderful and illuminating paper, but it is dense in its concepts for those unfamiliar with category theory, and uses the semiscrutable bracket syntax introduced by Bananas. But there’s no need for alarm if category theory isn’t your cup of tea: Haskell allows us, once again, to express elegantly the new recursion schemes defined in Primitive (Co)Recursion. Guided by Uustalu and Vene’s work, we’ll derive these two new recursion schemes and explore their ways in which they simplify complicated folds and unfolds. Though these new morphisms are, definitionwise, simple variations on paramorphisms and apomorphisms, in practice they provide surprising power and clarity, as Uustalu and Vene assert:
[We] argue that even these schemes are helpful for a declaratively thinking programmer and program reasoner who loves languages of programming and program reasoning where programs and proofs of properties of programs are easy to write and read.
That sure sounds like us. Let’s get going. This article is literate Haskell; you can find the source code here.
In our first entry, we defined Term
, the fixedpoint of a Haskell Functor
, with an In
constructor that wraps one level of a structure and an out
destructor to perform the corresponding unwrap^{1}.
newtype Term f = In { out :: f (Term f) }
Given an algebra — a folding function that collapses a Functor f
containing a
’s into a single a
—
type Algebra f a = f a > a
we use the catamorphism cata
to apply a leaftoroot^{2} fold over any recursivelydefined data structure. cata
travels to the most deeplynested point in the data structure by fmap
ing itself, recursively, into the next level of the stucture. When fmap cata x
returns an unchanged x
, we cease recursing (because we have hit the mostdeeplynested point); we can then begin constructing the return value by passing each node to the algebra, leaftoroot, until all the recursive invocations have finished.
cata :: (Functor f) => Algebra f a > a > Term f
cata f = out >>> fmap (cata f) >>> f
But the catamorphism has its limits: as it is applied to each level of the structure, it can only examine the current carrier value from which it is building. Given the Falgebra f a > a
, each of the structure’s children—the a
values contained in the f
container—has already been transformed, thus losing information about the original structure. To remedy this, we introduced para
, the paramorphism, and an Ralgebra to carry the original structure with the accumulator:
type RAlgebra f a = f (Term f, a) > a
para :: Functor f => RAlgebra f a > Term f > a
para f = out >>> fmap (id &&& para f) >>> f
Paramorphisms allow us, at each stage of the fold, to view the original structure of the examined node before the fold began. Though this is more powerful than the catamorphism, in many cases it does not go far enough: many useful functions are defined not just in terms of the original argument to the function, but in terms of previous computed values. The classic^{3} example is the Fibonacci function, the general case of which is defined in terms of two previous invocations:
fib :: Int > Int
fib 0 = 0
fib 1 = 1
fib n = fib (n1) + fib (n2)
We could express this function using a catamorphism—though one of the carrier values (fib (n1)
) would be preserved, as the accumulator of our fold, we would need another explicit recursive call to cata
to determine the historical value of fib (n2)
. This is a bummer, both in terms of efficiency—we’re recalculating values we’ve already calculated—and in terms of beauty: a function so fundamental as fib
deserves a better implementation, especially given the expressive power of recursion schemes.
The imperative programmers among us will have a solution to this inefficiency: “iterate!”, they will yell, or perhaps they will clamor “introduce a cache!” in a great and terrible voice. And it’s true: we could compute fib
with a forloop or by memoizing the recursive call. But the former approach entails mutable state—a very big can of worms to open for such a simple problem—and the latter leaves us with two problems. Uustalu and Vene’s histomorphism provides a way out: we will preserve the history of the values our fold computes, so that further recursive calls to compute past values become unnecessary. This style of recursion is called courseofvalue recursion, since we record the values evaluated as our fold function courses through the structure.
Rather than operate on an f a
, a data structure in the process of being folded, we’ll operate on a more sophisticated structure, so that the argument to our fold function contains the history of all applications of the fold itself. Instead of a just a carrier value a
, our f
will contain a carrier value and a recursive, unrollable record of past invocations, to wit:
data Attr f a = Attr
{ attribute :: a
, hole :: f (Attr f a)
}
We’ll call this Attr
, since it’s an ‘attributed’ version of Term
.
An Attr f a
contains an a
—a carrier value, storing the inprogress value of the fold—as well as a fixedpoint value (analogous to Term
) at each level of recursion. Thanks to the fixedpoint hole
within the f
, further Attr
items are preserved, each of which contains the shape of the folded functor f
. And within the f
there lie further Attr
values, each of which contains a carrier value yielded by their application in their attribute
slot. And those Attr
values in turn contain further hole
s, which contain the historical records pertaining to their childrens’ history, and so on and so forth until the bottom of the data structure has been reached. As such, the entire history of the fold is accessible to us: the holes
preserve the shape of the data structure (which was lost during cata
), and the attribute
holds the record of applying the fold to each entity in said data structure.
We have a word for preserving a record of the past, of course—history^{4}. A fold operation that uses Attr
to provide both an accumulator and a record of prior invocations is known as a histomorphism—a shapechanging (morpho) fold with access to its history (histo).
Let’s define the histomorphism. It will, like its cousins cata
and para
, use an algebra for its fold function. But unlike the Falgebra of cata
or the Ralgebra of para
, we’ll be using an algebra that operates on an Attr f a
, yielding an a
out of it. We call this a courseofvalue algebra, abbreviated to a CValgebra, and define a type alias for it, so we end up with a more comprehensible type signature in the histomorphism:
type CVAlgebra f a = f (Attr f a) > a
That is, a CValgebra maps from a container f
containing children of type Attr f a
(which in turn contain f (Attr f a)
children, as far down as is needed in the nested structure), to a final result type a
. The shape of the folded structure and the history of its applications are all contained in its Attr
values: all you have to do is unroll the hole
value to go back one level in history and use attribute
to examine the stored value.
Our histo
function will be similar to cata
and para
at its heart. We start by unpacking the Term
—the initial argument must be a Term
rather than an Attr
, since as we haven’t started the fold yet we have no value to fill in for attribute
. We will then recurse, with fmap
, into the thusrevealed structure until we hit its root. We then use the CValgebra to build the value, starting at the root and continuing upwards to the topmost leaf. These steps are analogous to how we defined cata
and para
, so let’s start defining it:
histo :: Functor f => CVAlgebra f a > Term f > a
histo h = out >>> fmap worker >>> h
But what type should the worker have? Well, we can ask GHC, thanks to one of its most useful features^{5}—type holes. By prepending an underscore to the use of worker
, we can allow the program compilation to continue as far as is possible—however, when the compilation process has finished, GHC will remind us where we used a type hole, and inform us of the type signature it inferred for _worker
. (As a fulltime Haskell programmer, I use this feature nearly every day.)
histo :: Functor f => CVAlgebra f a > Term f > a
histo h = out >>> fmap _worker >>> h
Running this code in GHC yields the following typehole message:
/Users/patrick/src/morphisms/src/Main.hs:14:24: error:
• Found hole: ‘_worker’ with type :: Term f > Attr f a
Okay, that makes sense! We’re operating on Term f
values (lifted into this context by the fmap
within histo
), and we need to yield an Attr f a
, so that the outside Term f
can be transformed into an f (Attr f a)
and then passed into the CValgebra.
An Attr f a
, as defined above, contains two values: a plain a
type, and a recursive f (Attr f a)
hole. Given a Term f
and our ability to invoke both histo
and worker
recursively, we can build the Attr f a
we need. Let’s start by defining the skeleton of worker
: given a Term f
, called t
, it constructs an Attr
, containing two fields.
worker t = Attr _ _
The first field, the a
, is yielded by recursing with histo
on the provided Term
—easy enough. This is just like the catamorphism—indeed, a catamorphism is a histomorphism that ignores the provided history.
worker t = Attr (histo h term) _
The second field’s construction is more clever: we unwrap term
with the out
function, which gives us an f (Term f)
out of a Term f
. Since we don’t know exactly what type f
is yet, we can’t extract the contained Term f
—but we can operate on it, with fmap
, provided by the Functor
constraint. So, to go from an f (Term f)
to an f (Attr f a)
, we need a function of type Term f > Attr f a
… hang on, that’s just worker
itself!
worker t = Attr (histo h term) (fmap worker (out t))
This is the heart of histo
‘s elegance: it’s ’doubly recursive’, in that its worker
function invokes both histo
and worker
itself.
Now we have a histo
function that passes the typechecker:
histo :: Functor f => CVAlgebra f a > Term f > a
histo h = out >>> fmap worker >>> h where
worker t = Attr (histo h t) (fmap worker (out t))
However, this function does not share its subcomputations properly: each iteration of worker
recomputes, rather than reuses, all the nested hole
values within the constructed Attr
. We can fix this by promoting worker
to operate on Attr
values; by recursing with fmap worker
, placing the input and output of the CValgebra in a tuple with &&&
, and then unpacking the tuple into an Attr
, we ensure that all the constructed Attr
values share their subcomputations.
histo :: Functor f => CVAlgebra f a > Term f > a
histo h = worker >>> attribute where
worker = out >>> fmap worker >>> (h &&& id) >>> mkAttr
mkAttr (a, b) = Attr a b
But what does this function mean? We’ve filled in all these type holes, and we have a working histo
function, but why does it work? Why does this preserve the history?
The answer lies in worker
, in the id
function that captures and preserves the Attr
the worker function is operating on. If we omitted that expression, we would have a function equivalent to cata
—one that throws all its intermediate variables away while computing the result of a fold. But our worker function ensures that the result computed at each stage is not lost: as we flow, roottoleaf, upwards through the data structure, we construct a new Attr
value, which in turn contains the previous result, which itself preserves the result before that, and so on. Each step yields an uptodate snapshot of what we have computed in the past.
By not throwing out intermediate results, and pairing these intermediate results with the values used to calculate them, we automatically generate and update a cache for our fold.
Now, I may have used fib
as an example of a courseofvalue recursive function, but I won’t provide an example of using histo
to calculate the nth Fibonacci number (though it’s a good exercise). Let’s solve a toy problem that’s slightly more interesting, one that histomorphisms make clear and pure, and one whose solution can be generalized to all other problems of its ilk.
The changemaking problem is simple: given a monetary amount N
, and a set of denominations (penny, nickel, dime, &c.), how many ways can you make change for N
? While it’s possible to write a naïve recursive solution for this problem, it becomes intolerably slow for large values of N
: each computation for N
entails computing the values for N  1
, and N  2
, and N  3
, and so forth: if we don’t store these intermediate amounts in a cache, we will waste our precious time on this earth. And, though this era may be grim as all hell, slow algorithms are no way to pass the time.
We’ll start by setting up a list of standard denominations. Feel free to adjust this based on the denominational amounts of your country of residence.
type Cent = Int
coins :: [Cent]
coins = [50, 25, 10, 5, 1]
So our fundamental procedure is a function change
, that takes a cent amount and returns a count of how many ways we can make change for said cent amount:
change :: Cent > Int
It is here where we hit our first serious roadblock. I asserted earlier that the changemaking problem, and all the other knapsack problems of its ilk, are soluble with a histomorphism—a cached fold over some sort of data structure. But here we’re dealing with… naturalnumber values. There are no lists, no vectors, no rose trees—nothing mappable (that is to say, nothing with a Functor
instance) and therefore nothing to fold over. What are we supposed to do?
All is not lost: we can fold over the natural numbers, just as we would fold over a list. We just have to define the integers in an unconventional, but simple, way: every natural number is either zero, or 1 + the previous. We’ll call this formulation of the natural numbers Nat
— the zero value will be Zero
^{6}, and the notion of the subsequent number Next
. Put another way, we need to encode Peano numerals in Haskell^{7}.
data Nat a
= Zero
 Next a
deriving Functor
We use Term
to parameterize Nat
in terms of itself—that is to say, given Term
, we can stuff a Nat
into it so as to represent an arbitrarilynested hierarchy of contained Nat
s, and thus represent all the natural numbers:
one, two, three :: Term Nat
one = In (Next (In Zero))
two = In (Next one)
three = In (Next two)
For convenience’s sake, we’ll define functions that convert from standard Int
values to foldable Term Nat
s, and vice versa. Again, these do not look particularly efficient, but please give me the benefit of the doubt.
 Convert from a natural number to its foldable equivalent, and vice versa.
expand :: Int > Term Nat
expand 0 = In Zero
expand n = In (Next (expand (n  1)))
compress :: Nat (Attr Nat a) > Int
compress Zero = 0
compress (Next (Attr _ x)) = 1 + compress x
While this is, at a glance, obviously lessefficient than using integers, it’s not as bad as it seems. We only have three operations: increment, converting from zero, and converting to zero. Restricting our operations to these—rather than writing our own code for addition or subtraction, both of which are lineartime over the Peano numerals—means that operations on our Term Nat
types are almost the same as hardwaretime costs, barring GHCspecific operations. As such, the expressivity we yield with our foldable numbers is well worth the very slight costs.
Given an amount (amt
), we solve the changemaking problem by converting that amount to a Term Nat
with expand
, then invoking histo
on it with a provided CValgebra—let’s call it go
. We’ll define it in a whereclause below.
change :: Cent > Int
change amt = histo go (expand amt) where
Since we’re operating on foldable natural values (Nat
) and ultimately yielding an integral result (the number of ways it is possible to make change for a given Nat
), we know that our CValgebra will have as its carrier functor Nat
and its result type Int
.
 equivalent to Nat (Attr Nat Int) > Int
go :: Nat (Attr Nat Int) > Int
Because histo
applies its algebra from leaftoroot, it starts at the deepest nested position in the Term Nat
—that is to say, Zero
. We know that there’s only one way to make change for zero coins—by giving zero coins back—so we encode our base case by explicitly matching on a Zero and returning 1.
go Zero = 1
Now comes the interesting part—we have to match on Next
. Contained in that Next
value will be an Attr Nat Int
(which we’ll refer to as attr
), containing the value yielded from applying go
to the previous Nat
ural number. Since we’ll need to feed this function into compress
to perform actual numeric operations on it (since we did not write the requisite boilerplate to make Nat
an instance of the Num
typeclass^{8}), we’ll use an @pattern to capture it under the name curr
.
go curr@(Next attr) = let
Because we need to find out what numeric amounts (from coins
) are valid changecomponents for curr
, we have to get an Int
out of curr
. We’ll call this value given
, since it’s our given amount.
given = compress curr
Now we have to look at each value of the coins
list. Any values greater than given
are right out: you can’t use a quarter to make change for a dime, obviously.
validCoins = filter (<= given) coins
Now we subtract the given
amount from each element of validCoins
. This list represents, for each coin in validCoins
, how much change we have remaining after using that coin to make change for given
—if given
were equal to 10, the list would be [9, 5, 0]
.
remaining = map (given ) validCoins
Now we partition this remaining
list into two sublists: the items equal to zero and those that are not. We don’t need to consult the lookup table for the items that are zero, obviously, but we need to do so for the others.
(zeroes, toProcess) = partition (== 0) remaining
Given each number in toProcess
, we have to consider how many ways we could make change out of that number—but, since we know that that we’ve already calculated that result, because it’s by definition less than given
! So all we have to do is look up the cached result in our attr
. (We’ll implement the lookup
function later on—it is two lines of code.) We’ll add all these cached results together with sum
.
results = sum (map (lookup attr) toProcess)
Then all that’s left to do is add zeroCount
and others
together.
in length zeroes + results
Let’s take a look at what we’ve written so far.
change :: Cent > Int
change amt = histo go (expand amt) where
go :: Nat (Attr Nat Int) > Int
go Zero = 1
go curr@(Next attr) = let
given = compress curr
validCoins = filter (<= given) coins
remaining = map (given ) validCoins
(zeroes, toProcess) = partition (== 0) remaining
results = sum (map (lookup attr) toProcess)
in length zeroes + results
Wow. This is pretty incredible. Not only do we have a simple, pure, concise, and performant solution to the changemaking problem, but the caching is implicit: we don’t have to update the cache ourselves, because histo
does it for us. We’ve stripped away the artifacts required to solve this problem efficiently and zeroed in on the essence of the problem. This is remarkable.
I told you I would show you how to look up the cached values, and indeed I will do so now. An Attr Nat a
is essentially a nonempty list: if we could pluck the mostfinal Attr Nat a
after change
has finished executing, we would see the value of change 0
stored inside the first attribute
value, the value of change 1
stored inside the attribute
within the first attribute’s hole
, and the value for change 2
inside that further hole
. So, given an index parameter n
, we return the attribute
if n
is 0, and we recurse inside the hole
if not, with n  1
.
lookup :: Attr Nat a > Int > a
lookup cache 0 = attribute cache
lookup cache n = lookup inner (n  1) where (Next inner) = hole cache
Something crucial to note is that the fixedpoint accumulator—the f (Attr f a)
parameter to our CValgebra—changes shape based on the functor f
contained therein. Given an inductive functor Nat
that defines the natural numbers, Nat (Attr Nat a)
is isomorphic to []
, the ordinary linked list: a Zero
is the empty list, and a Next
that contains a value (stored in Attr
’s attribute
field) and a pointer to the next element of the list (stored in the hole :: Nat (Attr Nat a))
field in the given Attr
). This is why our implementation of lookup
is isomorphic to an implementation of !!
over []
—because they’re the same thing.
But what if we use a different Functor
inside an Attr
? Well, then the shape of the resulting Attr
changes. If we provide the list type—[]
—we yield Attr [] a
, which is isomorphic to a rose tree—in Haskell terms, a Tree a
. If we use Either b
, then Attr (Either b) a
is a nonempty list of computational steps, terminating in some b
value. Attr
is more than an “attributed Term
”—it is an adaptive cache for a fold over any type of data structure. And that is truly wild.
As with para
, the increased power of histo
allows us to express cata
with new vocabulary. Every Falgebra can be converted into a CValgebra—all that’s needed is to ignore the hole
values in the contained Functor f
. We do this by mapping attribute
over the functor before passing it to the Falgebra, throwing away the history contained in hole
.
cata :: Functor f => Algebra f a > Term f > a
cata f = histo (fmap attribute >>> f)
Similarly, we can express para
with histo
, except instead of just fmapping with attribute
we need to do a little syntactic juggling to convert an f (Attr f a)
into an f (Term f, a)
. (Such juggling is why papers tend to use bananabracket notation: implementing this in an actual programming language often requires syntactic noise such as this.)
para :: Functor f => RAlgebra f a > Term f > a
para f = histo (fmap worker >>> f) where
worker (Attr a h) = (In (fmap (worker >>> fst) h), a)
Throughout this series, we can derive unfolds from a corresponding fold by “reversing the arrows”—viz., finding the function dual to the fold in question. And the same holds true for histomorphisms—the dual is very powerful. But, to find the dual of histo
, we must first find the dual of Attr
.
Whereas our Attr
structure held both an a
and a recursive f (Attr f a)
structure, its dual—CoAttr
—holds either an a
value—we’ll call that Automatic
—or a recursive f (CoAttr f a)
value, which we’ll call Manual
. (Put another way, since Attr
was a product type, its dual is a sum type.) The definition follows:
data CoAttr f a
= Automatic a
 Manual (f (CoAttr f a))
And the dual of a CValgebra is a CVcoalgebra:
type CVCoalgebra f a = a > f (CoAttr f a)
So why call these Automatic
and Manual
? It’s simple—returning a Manual
value from our CVcoalgebra means that we specify manually how the unfold should proceed at this level, which allows us to unfold more than one level at a time into the future. By contrast, returning a Automatic
value tells the unfold to continue automatically at this level. This is why we call them futumorphisms—our CVcoalgebra allows us to determine the future of the unfold. (The term ‘futumorphism’ is etymologically dubious, since the ‘futu’ prefix is Latin and the ‘morpho’ suffix is Greek, but there are many other examples of such dubious words: ‘television’, ‘automobile’, and ‘monolingual’, to name but a few.)
Like its predecessor unfolds ana
and apo
, the futumorphism will take a coalgebra, a seed value a
, and produce a term f
:
futu :: Functor f => CVCoalgebra f a > a > Term f
We derived the anamorphism and apomorphism by reversing the arrows in the definitions of cata
and para
. The same technique applies here—>>>
becomes <<<
, and In
becomes out
. And as previously, we use a type hole to derive the needed signature of the helper function.
futu :: Functor f => CVCoalgebra f a > a > Term f
futu f = In <<< fmap _worker <<< f
/Users/patrick/src/morphisms/src/Main.hs:28:32: error:
• Found hole: ‘_worker’ with type :: CoAttr f a > Term f
This also makes sense! The worker function we used in histo
was of type Term f > Attr f a
—by reversing the arrows in this worker and changing Attr
to CoAttr
, we’ve derived the function we need to define futu
. And its definition is straightforward:
futu :: Functor f => CVCoalgebra f a > a > Term f
futu f = In <<< fmap worker <<< f where
worker (Automatic a) = futu f a  continue through this level
worker (Manual g) = In (fmap worker g)  omit folding this level,
 delegating to the worker
 to perform any needed
 unfolds later on.
When we encounter a plain Automatic
value, we continue recursing into it, perpetuating the unfold operation. When we encounter a Manual
value, we run one more iteration on the top layer of the inprogress fold (transforming its children from Coattr f a
values into Term f
values by recursively invoking worker
), then wrap the whole item up with an In
constructor and return a final value. The product of this nested invocation of worker
is then similarly passed to the In
constructor to wrap it up in a fixpoint, then returned as the final output value of futu
.
What differentiates this from apo
—which, if you recall, used an Either
type to determine whether or not to continue the unfold—is that we can specify, in each field of the functor f, whether we want to continue the unfold or not. apo
gave us a binary switch—either stop the unfold with a Left
or keep going with a Right
. futu
, by contrast, lets us build out as many layers at a time as we desire, giving us the freedom to manually specify the shape of the structure or relegate its shape to future invocations of the unfold.
This is an interesting way to encode unfolds! A CVcoalgebra that always returns an Automatic
value will loop infinitely, such as the unfold that generates all natural numbers. This means that we can tell, visually, whether our unfold is infinite or terminating.
“But Patrick,” you might say, “this looks like a cellular automaton.” And you would be right—CVcoalgebras describe tree automata. And in turn, coalgebras describe finitestate automata, and Rcoalgebras describe stream automata. We’ll use this fact to define an example CVcoalgebra, one that grows^{9} random plant life.
Let’s start by defining the various parts of a plant.
data Plant a
= Root a  every plant starts here
 Stalk a  and continues upwards
 Fork a a a  but can trifurcate at any moment
 Bloom  eventually terminating in a flower
deriving (Show, Functor)
Let’s define a few rules for how a plant is generated. (These should, as I mentioned above, remind us of the rules for tree automata.)
1. Plants begin at the ground.
2. Every plant has a maximum height of 10.
3. Plants choose randomly whether to fork, grow, or bloom.
4. Every fork will contain one immediate bloom and two further stems.
Rather than using integers to decide what action to take, which can get obscure very quickly, let’s define another sum type, one that determines the next step in the growth of the plant.
data Action
= Flower  stop growing now
 Upwards  grow up with a Stalk
 Branch  grow up with a Fork
Because we need to keep track of the total height and a random number generator to provide randomness, we’ll unfold using a data type containing an Int
to track the height and a StdGen
generator from System.Random
.
data Seed = Seed
{ height :: Int
, rng :: Random.StdGen
}
We’ll define a function grow
that takes a seed and returns both an randomlychosen action and two new seeds. We’ll generate an action by choosing a random number from 1 to 5: if it’s 1 then we’ll choose to Flower
, if it’s 2 we’ll choose to Branch
, and otherwise we’ll choose to grow Upwards
. (Feel free to change these values around and see the difference in the generated plants.) The Int
determining the height of the plant is incremented every time grow
is called.
grow :: Seed > (Action, Seed, Seed)
grow seed@(Seed h rand) = (choose choice, left { height = h + 1}, right { height = h + 1})
where (choice, _) = Random.randomR (1 :: Int, 5) rand
(leftR, rightR) = Random.split rand
left = Seed h leftR
right = Seed h rightR
choose 1 = Flower
choose 2 = Branch
choose _ = Upwards
And now we’ll define a CVcoalgebra, one that takes a Seed
and returns a Plant
containing a CoAttr
value.
sow :: CVCoalgebra Plant Seed
The definition falls out rather quickly. We’ll start by growing a new seed, then examining the current height of the plant:
sow seed =
let (action, next) = grow seed
in case (height seed) of
Since we’ll start with a height value of 0, we’ll begin by generating a root (rule 1). Because we want to immediately continue onwards with the unfold, we pass a Automatic
into this Root
, giving it the subsequent seed (so that we get a new RNG value).
0 > Root (Automatic next)
Rule 2 means that we must cap the height of the plant at 10. So let’s do that:
10 > Bloom
Otherwise, the height is immaterial. We must consult the action
variable to know what to do next.
_ > case action of
If the action is to Flower
, then we again return a Bloom
.
Flower > Bloom
If it’s to grow Upwards
, then we return a Stalk
, with a contained Automatic
value to continue our fold at the top of that Stalk
:
Upwards > Stalk (Automatic next)
And now we handle the Branch
case. Our rules dictate that one of the branches will stop immediately, and the other two will continue, after a given length of Stalk
. So we return a Fork
with one Manual
and two Automatic
.
Branch > Fork  grow a stalk then continue the fold
(Manual (Stalk (Automatic next)))
 halt immediately
(Manual Bloom)
 again, grow a stalk and continue
(Manual (Stalk (Automatic next)))
Note how, even though we specify the construction of a Stalk
in the first and third slots, we allow the fold to Automatic
afterwards. This is the power of the futumorphism: we can choose the future of our folds, layer by layer. This is not possible with an anamorphism or apomorphism.
Here’s our full sow
function, rewritten slightly to use one case
statement:
sow seed =
let (action, left, right) = grow seed
in case (action, height seed) of
(_, 0) > Root (Automatic left)
(_, 10) > Bloom
(Flower, _) > Bloom
(Upwards, _) > Stalk (Automatic right)
(Branch, _) > Fork (Manual (Stalk (Automatic left)))
(Manual Bloom)
(Manual (Stalk (Automatic right)))
This is pretty remarkable. We’ve encoded a complex set of rules, one that involves both nondeterminism and strict layout requirements, into one CVcoalgebra, and it took just eleven lines of code. No mutable state is involved, no manual accumulation is required—the entire representation of this automaton can be reduced to one pure function.
Now, in our main
function, we can grab an RNG from the global state, and call futu
to generate a Term Plant
.
main :: IO ()
main = do
rnd < newStdGen
let ourPlant :: Term Plant
ourPlant = futu sow (Seed 0 rnd)
Using a rendering function (which I have omitted for brevity’s sake, though you can be assured that it is implemented using cata
rather than explicit recursion), we can draw a picture of the plant we’ve just generated, with little flowers.
⚘
 ⚘ ⚘ ⚘
⚘  
└─┘  
   ⚘
 ⚘   
└─────┘  ⚘ 
 └──────┘
 ⚘ 
└───────────────┘

_
Admittedly, the vaguaries of code page 437 leave us with a somewhat unaesthetic result—but a nicer representation of Plant
, perhaps using gloss or Rasterific, is left as an exercise for the reader.
One final detail: just as we can use an apomorphism to express an anamorphism, we can express anamorphisms and apomorphisms with futumorphisms:
ana :: (Functor f) => Coalgebra f a > a > Term f
ana f = futu (fmap Automatic <<< f)
apo :: Functor f => RCoalgebra f a > a > Term f
apo f = futu (fmap (either termToCoattr Automatic) <<< f)
where termToCoattr = Manual <<< fmap termToCoattr <<< out
Now we know what histomorphisms and futumorphisms are. Histomorphisms are folds that allow us to query any previous result we’ve computed, and futumorphisms are unfolds that allow us to determine the future course of the unfold, multiple levels at a time. But, as is so often the case with recursion schemes, these definitions touch on something deeper and more fundamental.
Here’s the kicker: our above CoAttr
definition is equivalent to the Free
monad, and Attr
(being dual to CoAttr
) is the Cofree
comonad.
We usually represent Free
, aka CoAttr
, as two constructors, one for pure values and one for effectful, impure values:
data Free f a
= Pure a
 Impure (f (Free f a))
And we usually represent the cofree comonad with an infix constructor, since the cofree comonad is at its heart a glorified tuple:
data Cofree f a = a :< (f (Cofree f a))
The various packages in the Haskell ecosystem implement cata
and para
in much the same way, but the same is not true of histo
and futu
. Edward Kmett’s recursionschemes package uses these definitions of Free
and Cofree
(from the free package). fixplate
uses a different definition of Attr
: rather than being a data type in and of itself, it is defined as a Term
over a moregeneral Ann
type. compdata
’s is slightly more complicated, as it leverages other typeclasses compdata
provides to define attributes on nodes, but is at its heart the same thing. Each is equivalent.
The free monad, and its cofree comonad dual, lie at the heart of some of the most fascinating constructions in functional programming. I have neither the space nor the qualifications to provide a meaningful explanation of them, but I can enthusiastically recommend Gabriel Gonzales’s blog post on free monads, Dan Piponi’s post on the cofree comonad, and (of course) Oleg Kiselyov’s groundbreaking work on the free and freer monads. But I think the fact that, as we explore as fundamental a construct as recursion, we encounter another similarly fundamental concept of the free monad, provide an argument for the beauty and unity of the categorytheoretical approach to functional programming that is far more compelling than any I could ever make myself.
I’d like to thank Rob Rix, who was essential to this work’s completion, and Colin Barrett, who has been an invaluable resource on the many occasions when I find myself stuck. I’d also like to thank Manuel Chakaravarty, who has done this entire series a great favor in checking it for accuracy, and Jeanine Adkisson, who found some outrageous bugs in the provided futumorphism. Greg Pfiel, Scott Vokes, and Josh Bohde also provided valuable feedback on drafts of this post. Mark Needham, Ian Griffiths, and Bryan Grounds found important bugs in the first published version of this post; I owe them a debt of gratitude. Next time, we’ll explore one of the most compelling reasons to use recursion schemes—the laws that they follow—and after that, we’ll discuss the constructs derived from combining unfolds with folds: the hylomorphism and the chronomorphism.
In the next installment, we discuss how the popular recursionschemes
library makes it easy to define recursion schemes on custom and existing data types.
Bob Harper, in Practical Foundations for Programming Languages, refers to In
and out
as “rolling” and “unrolling” operations. This is a useful visual metaphor: the progression f (f (Term f)) > f (Term f) > Term f
indeed looks like a flat surface being rolled up, and its opposite Term f > f (Term f) > f (f (Term f))
looks like the process of unrolling.↩
Rob Rix points out that, though catamorphisms are often described as “bottomup”, this term is ambiguous: catamorphisms’ recursion occurs topdown, but the folded value is constructed bottomup. I had never noticed this ambiguity before. (The words of Carroll come to mind: “‘When I use a word,’ Humpty Dumpty said, in rather a scornful tone, ‘it means just what I choose it to mean — neither more nor less.’”)↩
Unfortunately, in this context I think “classic” can be read as “hackneyed and unhelpful”. I dislike using fib()
to teach recursion schemes, as the resulting implementations are both more complicated than a straightforward implementation and in no way indicative of the power that recursion schemes bring to the table. Throughout this series, I’ve done my damnedest to pick interesting, beautiful examples, lest the reader end up with the gravely mistaken takeaway that recursion schemes aren’t useful for any realworld purpose.↩
A word with a rich pedigree—most directly from the Greek ‘ἱστορία’, meaning a narration of what has been learned, which in turn descended from ‘ἱστορέω’, to learn through research, and in turn from ‘ἵστωρ’, meaning the one who knows or the expert— a term commensurate with the first histories being passed from person to person orally. And the Greek root ‘ἱστο’, according to the OED, can be translated as ‘web’: a suitable metaphor for the structural web of values that the Attr
type generates and preserves.↩
A feature taken wholesale, we must note, from dependentlytyped languages like Agda and Idris.↩
Natch.↩
Keeneyed readers will note that this data type is isomorphic to the Maybe
type provided by the Prelude. We could’ve just used that, but I wanted to make the numeric nature of this structure as clear as possible.↩
There is no reason why we couldn’t do this—I just chose to omit it for the sake of brevity.↩
which brings an amusing literalism to the term ‘seed value’↩
As always, if you'd like to follow along with the code, it is preserved here.
In the past two posts, we defined a datatype Term
that represents the fixedpoint 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 typepreserving 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 realworld usecases 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 prettyprinting, we only have access to the currentlyprinted tree (the f Doc
for any fix): any information about the structure of the original Term Expr
is lost, as it has already been prettyprinted.
This would be a problem if you wanted to print, say, zeroargument 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 prettyprinted 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 prettyprinted representation and its original representation as a Term
—an Algebra
that has access to the original, untransformed datum, represented as its fixedpoint 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 Ralgebras.
type RAlgebra f a = f (Term f, a) > a
There is another type of morphism that allows you to traverse a structure with an Ralgebra: 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 pointfree 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 Kcombinator) for just these situations where we want to ignore an argument to a function:
cata' :: Functor f => Algebra f a > Term f > a
cata' f = 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 lesspowerful 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 prettyprinter 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 functioncall's prettyprinted name to determine whether it is id
, then return the argument unchanged—and, as I mentioned above, our prettyprinted Doc
representation shouldn't even support an equality operation, so examining it is a nogo. 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 Ralgebras above (the ternary function), and I'm going to use the Expr
syntax tree defined in previous installments.
fastPretty :: RAlgebra' Expr Doc
 All our cases, aside from the `Call` nodes in which
 we are interested, are the same as in the prettyprinting
 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 s
 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 { func = "id" })
Call {args = [theArg]} = theArg
fastPretty _ (Call f as) = f <> P.parens (P.cat (P.punctuate ", " as))
 The other cases are the same as `prettyPrint` in the last installment.
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 lefttoright function composition with the righttoleft 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 coparamorphism. 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 Ralgebra. 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 Ralgebra using an Either
:
type RCoalgebra f a = 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 Rcoalgebra 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 exceptions.
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 builtin 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 :: 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 :: 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.
In part four, we explore histomorphisms and futumorphisms.
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 secondclass 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 prettyprinter—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 prettyprinting step is happening.↩
On the last episode of this veryinfrequentlyupdated 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 veryinfrequentlyupdated 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 examples (both realworld 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. If you'd like to run the code, an implementation and test suite can be found here.
{# 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 lefthand and righthand 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 arbitrarilynested Expr
– in essence, an Expr (Expr (Expr (Expr ...)))
– but, since Haskell doesn’t support infinite types, we have to resort to a leastfixedpoint 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 arbitrarilynestable 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 lefttoright function composition, we expressed a generalized bottomup 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 bottomup 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 prettyprinted 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 bottomup 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 nexthighest 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 prettyprinters for trees. If the representation you require of a tree type can be expressed in a purely bottomup manner – that is to say, it requires no information about the original structure of the tree being transformed – you can express prettyprinting 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 prettyprinting 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 prettyprinted.
prettyPrint :: Expr Doc > Doc
Our base cases are straightforward:
prettyPrint (Literal i) = P.int i
prettyPrint (Ident s) = P.text s
And our inductivelydefined cases are beautifully clutterfree:
 f(a,b...)
prettyPrint (Call f as) = f <> P.parens (P.cat (P.punctuate ", " as))
 a[b]
prettyPrint (Index it idx) = it <> P.brackets idx
 op x
prettyPrint (Unary op it) = P.text op <> it
 lhs op rhs
prettyPrint (Binary l op r) = l <> P.text op <> r
 (op)
prettyPrint (Paren exp) = P.parens exp
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 lefttoright 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 bottomup and topdown 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 topdown traversal by reversing a bottomup 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 inductivelydefined 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
fixedpoint 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 handwavy treatment of leastfixedpoints 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 realworld benefits: our new generalized traversal can replace a host of typespecific 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 firstclass functions. Clojure, for example, uses them to power its clojure.walk API for generically traversing sexpressions 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 handwritten 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 welltyped 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 stepbystep descriptions of recursion patterns with common Haskell idioms.
If you'd like to follow along with the code, you can find it in this GitHub repository. An HUnit test suite is included to verify the provided examples.
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
properly 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 sixline 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 sharpeyed among you will notice how similar this function is to the builtin 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 builtin 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 arbitrarilynested 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 subexpressionsExpr (Expr Lit)
represents expressions with at most one more layer of subexpressions.Expr (Expr (Expr Lit))
represents twolevel 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 arbitrarilynested 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 arbitrarilynested Expr
s.
Consider the Ycombinator. 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 sharpeyed will have noticed that the expansion of y(f)
is very similar to our NestedExpr
type above. If we have a Ycombinator embedded entirely in the type system, we can describe the repeated application of Expr
to itself, in a manner identical to how the valuelevel Ycombinator operates on functions, and in turn we can describe an Expr a
where a
represents arbitrarilynested Expr
s.
type Y t = t (t (t (t (t ...))))
This general concept^{3} is known as ‘fixedpoint’: 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 Ycombinator that works in the type system too, and that’s is how we will express the selfsimilar nature of an 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 arbitrarilynested 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 fixedpoints 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 fixedpoints of functors. Let’s do something awesome with them.
Consider the notion of the bottomup traversal: specifically, let’s write pseudoEnglish instructions for traversing the fixedpoint of a functor:
To traverse a Term bottomup 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 lefttoright function composition,f >>> g x
is equal to g(f(x))
. Though this style is a bit unconventional—the righttoleft 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 lefttoright 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 typesafe and typegeneric 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 arbitrarilynested 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 bottomup 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 topdown traversal of a Term
, the obvious analogue to our bottomup traversal:
To traverse a Term topdown 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 bottomup 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 lefttoright operator >>>
with <<<
, the righttoleft 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 topdown and bottomup 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 fixedpoints and functors, two concepts central to Haskell and to functional programming in general, is doubly amazing.
Topdown and bottomup 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, moregeneral 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 latenight 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 BirdMeertens formalism, a calculus of program construction based on recursion schemes. (Meijer’s Ph.D. thesis discussed compiler specifications using the BirdMeertens formalism). This calculus was also known as “Squiggol”, after its “squiggly” notation. Though this notation is wellspecified, 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 fixedpoint 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.↩