Recursion Schemes, Part IV: Time is of the Essence
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.
A Brief Recap
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
Running a Course with Histomorphisms
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.
CCCChanges
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
A ShapeShifting 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.
Obsoleting Old Definitions
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)
Controlling the Future with Futumorphisms
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.
Horticulture with Futumorphisms
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
My God, It’s Full of Comonads
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
andout
as “rolling” and “unrolling” operations. This is a useful visual metaphor: the progressionf (f (Term f)) > f (Term f) > Term f
indeed looks like a flat surface being rolled up, and its oppositeTerm 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’↩