Previous installments: 1, 2, 3, 4, 4½, 5.
Now that we’ve covered folds (cata
, para
, and histo
), unfolds (ana
, apo
, and futu
), and refolds (hylo
, hypo
, elgot
, and chrono
), I hope I have shown that recursion schemes are a useful tool to organize programs, beautify code, and clarify human
Previous installments: 1, 2, 3, 4, 4½, 5.
Now that we’ve covered folds (cata
, para
, and histo
), unfolds (ana
, apo
, and futu
), and refolds (hylo
, hypo
, elgot
, and chrono
), I hope I have shown that recursion schemes are a useful tool to organize programs, beautify code, and clarify human intent. The above schemes provide sufficient bells and whistles so as to be an essential part of a functional programmer’s toolbox.
Yet if we allow ourselves a greater degree of generality in the definition and construction of these recursion schemes, we unlock an underlying similarity between all these definitions. This underlying similarity was outlined by Tarmo Uustalu, Varmo Vene^{[1]}, and Alberto Pardo in their 2001 paper Recursion Schemes from Comonads. As is often the case with papers describing recursion schemes, this work is dense and somewhat unapproachable. Initially I deemed Uustalu’s exploration of these similarities elegant but inessential: it was my intention to discuss these results on the merits of their beauty rather than their applicability to realworld situations. However, a close read of Edward Kmett’s recursionschemes
library revealed an implementation of the core ideas behind Recursion Schemes from Comonads, and some experimentation revealed to me how and why this paper is useful.
The essence of Haskell is composition. Functions, folds, lenses, algebras—composition is the melody with which all the disparate elements of Haskell are in tune. Why, then, can I not compose recursion schemes? For example, I have para
, which lets me look at the original values alongside the fold’s values inflight, and histo
, which provides a lookup table for previously calculated compositions, but what if I need both these properties to define a given fold? Or what if I want to create a new hylo
esque combinator out of the composition of a histomorphism and an apomorphism?
Thanks to Uustalu et al.’s ideas, our toolbox of recursion schemes becomes something more: rather than limiting us to the dozen or so predefined recursion schemes, we can build combinators capable of combining and composing existing schemes into new schemes, building a solution tailormade to the needs of the situation. This result is more than a beautiful implementation: it unifies a set of related but disparate tools into a single cohesive abstraction. I hope in this article to outline these ideas, though the density of the paper itself means I won’t be stepping closely through it.
This article uses the Base
functor formulation of recursion schemes, as described in Kmett’s library, rather than the adhoc library we’ve designed in previous installments of this series. If you want an overview of why this formulation is useful, my prior post on the matter may be helpful.
cata :: (Base t a > a) > t > a
para :: (Base t (t, a) > a) > t > a
histo :: (Base t (Cofree (Base t) a) > a) > t > a
These are the type signatures of cata
, para
, and histo
. Each differs from the other in one place: the last parameter to the type Base t
, their Base
algebras. For cata
, the carrier is a plain old a
value, corresponding to previous results (if any) of the stages of the fold. For para
, it’s (t, a)
, because at each stage of a paramorphism the original t
value is visible alongside the inflight a
. And for histo
, the carrier type is Cofree (Base t) a
, representing an adaptive, ‘shapeshifting’ cache structure around the original t
, storing all previouslycomputed a
values.
At first glance, these three values don’t seem to share any essential similarity. But we can change that, by applying the Identity
functor.
newtype Identity a = Identity { runIdentity :: a }
A value of type Identity a
just wraps a single a
. Though it doesn’t appear to be particularly useful, since you can substitute an a
for any Identity
without having to construct or destructure an Identity
value, its use lies in the set of interfaces to which it conforms. In this case, rather than using a bare a
as the carrier type for cata
, we can use Identity
, because the original a
is isomorphic to an Identity a
value.
cata :: (Base t (Identity a) > a) > t > a
para :: (Base t (t, a) > a) > t > a
histo :: (Base t (Cofree (Base t) a) > a) > t > a
Now we have three type signatures, each bearing a different carrier type: Identity
for cata
, the tuple (t,)
for para
, and Cofree (Base t)
for histo
. Each of these types represents a container or context that holds further a
values, which we unify at each step of the fold into a single a
value that is then passed to further iterations of the fold.
There is a deep similarity between these three types, though it may not appear so at first glance: they all implement the Comonad
typeclass.
The theory behind comonads is rich and deep, and I have neither room nor time to give a complete outline thereof. I recommend reading Bartosz Milewski’s excellent and rigorous overview of how to derive and define comonadic structures, as well as Gabriel Gonzales’s application of comonadic abstractions to realworld problems. For our purposes, it suffices to define the Comonad
typeclass and outline its interface.
class Functor w => Comonad w where
extract :: w a > a
duplicate :: w a > w (w a)
This is an interface with two functions:
extract
, which, given some data type w
^{[2]} wrapping an a
value, pulls out and returns that a
. This is dual to Monad
’s return
, which stuffs an a
inside a monadic type.duplicate
, which, given a w a
, wraps it in a further w
container, returning a w (w a)
. This is dual to Monad’s join
.Let’s implement Comonad
for the data types we’ve discussed thus far.
instance Comonad Identity where
extract (Identity a) = a
duplicate i = Identity i
The instance for Identity
is pretty straightforward: in extract
, we patternmatch on the Identity
to reveal its contents, and to duplicate
, we just apply the Identity
constructor again, yielding an Identity (Identity a)
.
instance Comonad ((,) a) where
extract (_, b) = b
duplicate (a, b) = (a, (a, b))
For tuples ((,)
), extract
targets the second element of the tuple. Correspondingly, duplicate
replaces the second element of the provided tuple with a copy of itself, yielding a tuple containing a tuple.
instance Functor f => Comonad (Cofree f) where
extract (a :< _) = a
duplicate (a :< f) = (a :< f) :< fmap duplicate f
Because Cofree
can be seen as a recursive tuple type, the Comonad
instance for Cofree
is spiritually similar. Given some Cofree f a
value, extract
instance yields the a
contained therein, while duplicate w
creates a new Cofree
datum with w
as its annotation, keeping the recursive f
as its selfrecursive type but mapping duplicate
therein to ensure that all recursive elements are properly duplicated.
One of the primary idioms for constructing Haskell programs is monad transformers: the programmer, faced with some sort of program and its requirements, maps each of these requirements to some computational context—the State
transformer for programs that need stateful values, the Reader
transformer for those requring an immutable environment, or the LogicT
transformer for backtrackingamenable logic programming. The programmer then builds their own Monad
by composing each of these elements, for example:
newtype MyProgram = MyProgram { run :: StateT MyState (ReaderT MyEnv (LogicT Identity)) a }
deriving (MonadState MyState, MonadReader MyEnv)
By defining this monad, this programmer has built a miniDSL for describing the capabilities of our program. The MonadState
and MonadReader
interfaces provide her with builtin functionality for accessing the program’s environment and modifying it’s stateful parameter. We call these contexts—this StateT s
, this ReaderT e
, this LogicT
—monad transformers, because each allows us to transform some other monad. Think of it like some layered hard candy: each layer provides a different capability/flavor, down to the “core” monad/chewy center on which all previous layers are built. (This “core” monad is almost always either Identity
or IO
, to represent pure and impure computations respectively.)
Because transformers exist for monads and comonads are dual to monads, we can postulate that that there exist transformers for comonads. And indeed, comonad transformers are a wellestablished construct, though less wellknown than their monadic duals. Let’s take a look at one of the simpler such transformers, the Env
comonad transformer.
data EnvT env w a = EnvT env (w a)
deriving Functor
Given an environment type env
, an inner Comonad
w
, and a wrapped type a
, the EnvT
transformer builds a new comonad with all the capabilities of that w
, but that has the added capability of consulting an environment of type env
. If this looks like the tuple type ,
to you, you’re right: you can see EnvT
as a tuple type specifically constructed to hold comonads^{[3]}. To provide a measure of harmony between EnvT
and (,)
, we can define a ComonadEnv
typeclass:
class Comonad w => ComonadEnv e w  w > e where
ask :: w a > e
This interface provides us with a generalized ask
function capable of extracting an environment (e
) from any comonad supporting the notion of environments.
instance ComonadEnv e (EnvT e w) where
ask (EnvT e _) = e
This instance for EnvT
is pretty trivial: we just return the env
parameter. (We don’t use extract
, since that would target the a
, rather than the env
, of some EnvT env w a
.)
instance ComonadEnv e ((,) e) where
ask = fst
Similarly, we can define ask
over tuples, where ask
retrieves the first element of the tuple. Though this may seem like a lot of typing for little benefit, the ComonadEnv
typeclass provides us with a generalized interface to the environment parameter associated with any environmental Comonad
. Thus, when we build new Comonad
types out of these comonad transformers, we can always use ask
to extract the environment, saving us from having to memorize an extraction function for each comonad. We’ll use this later to provide a fluent interface over the comonads we construct with transformers.
class Comonad w => ComonadCofree f w  w > f where
unwrap :: w a > f (w a)
instance ComonadCofree f (Cofree f) where
unwrap (_ :< r) = r
Similarly, the ComonadCofree
interface provides an abstraction over the Cofree
comonad: the unwrap
function, given a Cofree f a
extracts the selfsimilar recursive entity, of type f (Cofree f a)
. If we build a new comonad with Cofree
at its core, we can implement the ComonadCofree
interface and use the same unwrap
function for both Cofree
and our new comonad. Indeed, let’s do that.
Let’s define a comonad that combines the Env
comonad and the Cofree
comonad: this resulting entity will have both access to an environment and to a contained selfsimilar recursive entity.
newtype Ledger t f a = Ledger { getLedger :: EnvT t (Cofree f) a } deriving Functor
We’ll call it Ledger
, as this data structure is capable of recording past computations (Cofree f
), along with the environment provided (EnvT t
) to each computation, much as an accountant’s ledger can record past transactions and the information associated therewith. The getLedger
record selector allows us to turn a Ledger t f a
back into an equivalent EnvT
over Cofree
; we’ll use this in definitions of Comonad
typeclasses.
instance Functor f => Comonad (Ledger t f) where
extract = getLedger >>> extract  delegate to EnvT's extract
duplicate l@(Ledger w) = Ledger (l <$ w)  add a new Ledger layer to the input
Due to a limitation of GHC, we can’t automatically derive an instance of Comonad
for Ledger
, but it’s not too painful to do so by hand. Similarly, we can write instances for ComonadEnv
and ComonadCofree
. (I’ve annotated these instances with their type signatures, thanks to GHC’s InstanceSigs
extension, for the sake of clarity.)
instance Functor f => ComonadEnv t (Ledger t f) where
ask :: Ledger t f a > t
ask = getLedger >>> ask  delegate to EnvT, again
instance Functor f => ComonadCofree f (Ledger t f) where
unwrap :: Ledger t f a > f (Ledger t f a)
unwrap = getLedger >>> unwrap >>> fmap Ledger  delegate to EnvT+Cofree's unwrap
Now that we have this comonad, we can pose a question: what kind of fold would a Ledger t f
generate? Since the core of this comonad is Cofree
, it would presumably be like histo
—that is, capable of consulting a record of previouslycomputed f
results—with behavior similar to that of para
, providing access to the original, unprocessed t
values from the beginning of each stage of the fold. We could refer to this scheme as a histoparamorphism, or perhaps a parahistomorphism.
Our first instinct might be to sit down and manually derive a definition of this recursion scheme, like we did for cata
, para
, and histo
. But we don’t have to! The contribution of Recursion Schemes from Comonads is that there exists a generalized catamorphism capable of deriving a recursion scheme for any Comonad
, as long as we provide a function called a distributive law, that describes how operations percolate through and transform a given comonad. This means we never have to write our own recursion schemes: we can lean on the generalized catamorphism, gcata
. This provides us a composable, plugandplay interface to recursion schemes. No longer are we limited to these three builtin combinators—instead, we can build our own, out of compositional, reusable parts, without the repetitive and errorprone process of deriving a recursion scheme for every task.
To do this, and to understand how it works, we’ll need to look at how these distributive laws and this generalized catamorphism are implemented.
To understand the nature of distributive laws, it helps to examine the ones provided to us by the recursionschemes
package. Let’s start with the simplest such law, the law for Identity
, out of which the gcata
function (which we will soon define) yields the catamorphism. (Distributive laws in recursionschemes
are generally named distFoo
, where Foo
is replaced by the name of the recursion scheme to which this law gives rise.)
distCata :: Functor f => f (Identity a) > Identity (f a)
distCata f = Identity (fmap runIdentity f)
This law states that we can, given an f
wrapping an Identity
, turn it into an Identity
wrapping an f
. In other words, we’re distributing^{[4]} occurrences of f
from outside an Identity
comonad to inside. We can look at the distributive law for Cofree
, distHisto
, and see that it has a similar shape.
distHisto :: Functor f => f (Cofree f a) > Cofree f (f a)
distHisto = fmap extract f :< fmap unwrap f
Just as distCata
moved an f (Identity a)
inside an Identity
, distHisto
moves an f (Cofree f a)
inside a Cofree
. And a corresponding distributive law for para
exists^{[5]}:
distPara :: Comonad f => f (t, a) > (t, f a)
distPara f = (fst (extract f), fmap snd f)
Please note that these implementations differ from those in the recursionschemes
library, which uses evenmoregeneral combinators.
distLedger :: Comonad f => f (Ledger t f a) > Ledger t f (f a)
Working of the examples provided by the prior distributive laws, we can postulate that a distributive law for Ledger
would look something like the above. And indeed, with a little elbow grease we can write a law ourselves that fits into this pattern:
distLedger f = Ledger (EnvT environ cofree) where
environ = ask (extract f)
cofree = fmap extract f :< fmap distInnards f
distInnards (Ledger (EnvT _ (x :< y))) = distHisto y
There is something immediately offputting about this declaration: it’s complicated. Firstly, it relies on a Comonad
instance, whereas previous distributive laws were able to get away with just a Functor
. And secondly, it requires a good deal of patternmatching to successfully zero in on the Cofree
structure over which we need to distribute. This means that as we adjust the definition of Ledger
, we’ll need to manually fix this patternmatching code, which is no fun at all. But there is hope: recursionschemes
contain combinators that automatically derive distributive laws for us. But to see this in action, we need to stop beating around the proverbial bush and take a look at the definition of the generalized catamorphism.
gcata
In the recursionschemes
package, we find the generalized catamorphism gcata
defined thus:
gcata :: (Recursive t, Comonad w)
=> (forall b. Base t (w b) > w (Base t b))  ^ a distributive law
> (Base t (w a) > a)  ^ a (Base t)walgebra
> t  ^ fixed point
> a
This is… well, it’s a lot to take in. I’ve omitted^{[6]} the implementation, as it is somewhat dense, but we can start understanding gcata
through its type signature. Let’s take a look at the first parameter, described in the documentation as the distributive law:
forall b . Base t (w b) > w (Base t b)
If we recall part 4.5 of this series, we’ll remember that recursionschemes
provides the Base
type family. Given some data type t
, Base t
is the parameterized version of t
, adding an extra type variable and replacing recursive occurrences of t
with this variable. We can mentally substitute f
for this Base t
, which yields something much more like the distributive laws we covered earlier:
forall b . f (w b) > w (f b)
This is congruent with our earlier examples: given some comonad w
and a Base
functor f
, this distributive law describes how a f
containing w
values can be turned into a w
containing f
values. And in the subsequent parameter to gcata
, we can substitute f
for Base t
yet again:
(f (w a) > a)
This looks a lot like our definition of Algebra
, which was f a > a
. Yet instead of a functor wrapping just a
values, this functor wraps w a
values. We’ll call this a w
algebra. Stripped of recursionschemes
’s machinery for Base
(which, though it provides a significant measure of realworld convenience, can clutter up definitions such as these), and by defining type synonyms for distributive laws and w
algebras, we can take a look at the essence of gcata
:
type WDistLaw f w = forall b . f (w b) > w (f b)
type WAlgebra f w a = f (w a) > a
gcata :: (Functor f, Comonad w)
=> WDistLaw f w  ^ a distributive law
> WAlgebra f w a  ^ a walgebra returning 'a'
> Term f
> a
This is pretty remarkable. Simply by specifying a Comonad
and providing a distributive law for it, gcata
becomes capable of doing the job of cata
, para
, and histo
, all stemming from a single definition. All you need to do is provide the required distributive law. We can take a look at the type signatures that occur when we feed gcata
one of the dist
family of distributive laws.
λ> :t gcata distCata
gcata distCata
:: Recursive t => (Base t (Identity a) > a) > Term f > a
That looks identical to the Identity
based cata
that we derived above! Let’s throw a type synonym in here, as we did for the original formulation of cata
, representing the walgebra
type WAlgebra t w a = Base t (w a) > a
cata :: Recursive t => WAlgebra t Identity a > t > a
cata = gcata distCata
Aside from the Identity
comonad, this definition is identical to the standard formulation of cata
. In addition, we can define para
and histo
with gcata
.
para :: (Recursive t, Corecursive t) => WAlgebra t ((,) t) a > t > a
para = gcata distPara
histo :: (Recursive t) => WAlgebra t (Cofree (Base t)) a > t > a
histo = gcata distHisto
So what happens if we plug in our distLedger
function into gcata
?
λ> :t gcata distLedger
gcata distLedger
:: (Recursive t, Comonad (Base t)) => (Base t (Ledger t (Base t) a) > a) > t > a
That’s almost correct—we have a Ledger
based Walgebra as the first parameter—but a look at the type constraints shows that this definition is slightly wrong. Restricting this function to types that provide an instance of Comonad
for their Base
functor is much too restrictive, given that most Base
functors don’t admit a definition of Comonad
. Our error lies in the fact that our distLedger
function used comonadic extract
to extract the environment from a f (Ledger env f a)
. However, if we’re dealing with Base
functors, we can use the Corecursive
typeclass, which provides an embed
that serves, in this case, the purposes of extract
, without any Comonad
constraint. We’ll use an equality constraint \~
(provided by the TypeFamilies
extension) to specify that f
is, in this case, equivalent to Base t
, to keep clutter out of the righthandside of the definition
distLedger' :: (Corecursive t, f ~ Base t) => f (Ledger t f a) > Ledger t f (f a)
distLedger' f = Ledger (EnvT environ cofree) where
environ = embed (fmap ask f)
cofree = fmap extract f :< fmap distInnards f
distInnards (Ledger (EnvT _ (x :< y))) = distHisto y
Now we can build a Ledger
powered recursion scheme, without requring any errant Comonad
constraints in its signature.
histoPara :: (Recursive t, Corecursive t) => WAlgebra t (Ledger t (Base t)) a > t > a
histoPara = gcata distLedger'
Yet we are still left with the problem that haunted us in the previous section: distLedger'
is brittle and difficult to understand. To solve this, recursionschemes
has one last trick up its abstractiondrunk sleeve.
Inside the guts of Data.Functor.Foldable
, there lurks a nastylooking function called distParaT
:
distParaT :: (Corecursive t, Comonad w)
> (forall b. Base t (w b) > w (Base t b))
> Base t (EnvT t w a)
> EnvT t w (Base t a)
As with so much in recursionschemes
, it’s not clear at first what this function does, given its lack of documentation. But if we start adding parentheses in the signature, something jumps out at us:
distParaT :: (Corecursive t, Comonad w)
> (forall b. Base t (w b) > w (Base t b))
> (Base t (EnvT t w a) > EnvT t w (Base t a))
Adding parentheses, and thus making the currying explicit, we see that distParaT
both takes and returns a distributive law. The first parameter is a distributive law describing how a comonad w
distributes over a Base
functor: we’ve seen this before, in the first argument to gcata
. The return type is much more interesting: given some distributive law, distParaT
builds another distributive law, wrapping the comonad w
in an EnvT
and distributing appropriately. In this sense, we can think of distParaT
as a distributivelawtransformer: given some ‘base’ distributive law over w
, distParaT
gives us a distributive law over EnvT env w
. That’s pretty remarkable!
To verify this, we can yield distPara
by passing in distCata
:
λ> :t distParaT distCata
distParaT distCata
:: (Corecursive t) => Base t (EnvT t Identity a) > EnvT t Identity (Base t a)
As we discussed, EnvT
is a comonadic take on the tuple type (,)
. As such, if we mentally substitute (,)
for EnvT
, we yield a definition equivalent to distPara
! (We have to use EnvT
here rather than plain old (,)
because we are dealing in comonad transformers: there exists no TupleT
transformer, since it would be the same as EnvT
).
We’ve established that our Ledger
comonad is the composition of the Env
and Cofree
comonads, the former atop the latter. Since distParaT
transforms distributive laws into EnvT
compatible laws, and we already have a distributive law for Cofree
, distHisto
. What happens if we pass distHisto
to distParaT
?
λ> :t distParaT distHisto
distParaT distHisto
:: Corecursive t
=> Base t (EnvT t (Cofree (Base t)) a)
> EnvT t (Cofree (Base t)) (Base t a)
This yields us something almost identical to Ledger
—remember that Ledger t f a
wraps a EnvT t (Cofree f) a
. Now we can, with some invocations of the Ledger
constructor and getLedger
destructor, write distLedger
without a single patternmatch^{[7]}:
distLedger'' :: Corecursive t => Base t (Ledger t (Base t) a) > Ledger t (Base t) (Base t a)
distLedger'' = fmap getLedger >>> distParaT distHisto >>> Ledger
The upshot of all of this is that, thanks to the generality of gcata
, you can combine arbitrary capabilities, from any type of fold, into a bespoke fold that exactly fits the problem at hand. Furthermore, you never need to write a distributive law by hand: the distributivelawtransformers like distParaT
and its siblings distGHisto
^{[8]} and distZygoT
make it straightforward to derive, given a comonad built of comonad transformers, a welltyped distributive law. Every recursion scheme is, under the hood, wrought of the same material. There is a underlying order and rhythm shared between all recursion schemes, that, in my view, elevates this approach from ‘hey, this is cool’ to something that shows us deep and fundamental aspects of the nature of recursive computations. Just as the integral and differential calculus allowed Newton and Leibniz to unify the treatment of curves, motion, and infinitesimals, Recursion Schemes from Comonads allows us to unify folds, dynamic programming, and mutuallyrecursive computations (zygo
). There is a beauty to this treatment of recursion that is symphonic in its harmony.
gcata
is not the only generalized recursion scheme. There exists its categorical dual, gana
, the generalized anamorphism, an unfold operation derived by reversing the arrows in gcata
.
gana :: (Corecursive t, Monad m)
=> (forall b. m (Base t b) > Base t (m b))  ^ a distributive law
> (a > Base t (m a))  ^ a Basetm coalgebra
> a  ^ a seed
> t
Note that where gcata
entailed a constraint of kind (Recursive t, Comonad w)
, gana
takes the dual of both these typeclasses: Recursive
becomes Corecursive
and Comonad
becomes Monad
. In addition, we reversed the arrows within the distributive law: whereas the distributive laws for folds turned functors wrapping comonads into comonads wrapping functors, the distributive laws for unfolds turn monads wrapping functors into functors wrapping monads.
distAna :: Functor f => Identity (f a) > f (Identity a)
distApo :: Recursive t => Either t (Base t a) > Base t (Either t a)
distFutu :: Functor f => Free f (f a) > f (Free f a)
The distributive law for ana
is almost identical to that for cata
, since Identity
is dual to itself. By contrast, the distributive law for apo
(the apomorphism, dual to the paramorphism) must deal with Either
values, since the dual of (a, b)
is Either a b
. Similarly, distFutu
deals in Free
, dual to distHisto
’s use of Cofree
recursionschemes
also provides transformers capable of building distributive laws for monads, so you need not write them by hand.
Similarly, there exists a ghylo
combinator that generalizes hylo
, the refold. hylo
was already powerful and general, given the set of problems to which it is amenable, but ghylo
takes it even farther: you can build a refold out of futu
and apo
, or ana
and histo
, or any other combination of the comonadic recursion schemes.
As always, I would like to thank Manuel Chakaravarty for checking this series for accuracy. He has done me an extraordinary kindness in lending his time and attention to this series, and it is infinitely better for it. I also need to thank Colin Barrett for his support and insight, and Rob Rix for the motivation and kindness he continually shows me. Ed Kmett, and all the recursionschemes
contributors, also deserve many thanks for creating and maintaining such a superlative and essential library. I would also like to thank everyone who read these monographs, especially those who found errors therein: getting this stuff right is hard, and I appreciate your patience in the face of the bugs that have crept in.
There are many more recursion schemes I am leaving undiscussed: zygomorphisms, mutumorphisms, Fokkinga’s prepromorphisms and postpromorphisms, Mendlerstyle catamorphisms and anamorphisms, Vanessa McHale’s entangled morphisms (dendro, scolio, and chema), and the nighlegendary zygohistomorphic prepromorphism. But at this point, after five years spent thinking and writing about recursion schemes, I’ve decided to put an end to this blog series. I hope, in the future, to have the time to work on a larger, more definitive reference work, covering all the known recursion schemes as well as the topics I had to gloss over. Until then, I’m looking forward to writing about something else; if you’ve read all of what I had to write here, I truly appreciate it. The response to this series has been deeply fulfilling.
Thank you!
You might remember Uustalu and Vene from Primitive(Co)Recursion and CourseofValue (Co)Iteration, Categorically, which introduced the histomorphism and futumorphism (as covered in the third part of this series). ↩︎
Most documentation uses w
to represent types that implement Comonad
, probably because c
is often used in bindings of values, and because w
looks like a flipped—that is to say, arrowreversed—version of m
, which is used for Monad
type variables. ↩︎
In other words, EnvT env w a
is representationally equal to (env, w a)
, and EnvT env Identity a
is isomorphic to (env, a)
. We can also see EnvT
as dual in nature to ReaderT
: it binds a formerlyfree variable on which some further computation depends. ↩︎
You might remember the term ‘distributive law’ from elementary algebra: we say that multiplication distributes over addition, in that 5 * (4 + 3)
is equivalent to (5 * 4) + (5 * 3)
. Given a multiplication operation over an addition, we can distribute that multiplication inside the components of that addition, in essence converting from a product of sums to a sum of products. ↩︎
In the name of didacticism, I fibbed a little on this definition: in recursionschemes
, this law is expressed not with a plain Functor f
, but with a Base t
functor, due to implementation details (distPara
is actually implemented with distZygo
, the distributive law for the zygomorphism, which we won’t cover in this post.) ↩︎
If you’re really curious, it is mostly identical to the definition of cata
, except at each stage of the fold, after recursing into the subterms, we call duplicate
on the Comonad
inside the functor through which we are recursing. The distributive law transforms that functorofcomonads into a comonadoffunctors, which is then destructed with extract
and sent through one last pass of the provided Walgebra to yield a result type. The distributive law describes how the fold is propagated through the given comonad, and the Comonad
typeclass gives us the vocabulary to construct and remove the extra scaffolding upon which the distributive law depends.
gcata k g = g . extract . c where
c = k . fmap (duplicate . fmap g . c) . project
↩︎Given that the result of distParaT distHisto
is isomorphic to Ledger t (Base t) a
, we ought to be able to apply Data.Coerce.coerce
to it and have the Ledger
and getLedger
constructors and eliminators applied for us; GHC, however, can’t yet prove that this is a wellfounded coercion. We have at least the small consolation that GHC will optimize away the overhead of wrapping and unwrapping Ledger
values. ↩︎
It’s unclear to me why this is called distGHisto
rather than distHistoT
; drop me a line should you know. ↩︎
I refer to those genera which have sometimes been called “polymorphic”, in which the species present an inordinate amount of variation; and hardly two naturalists can agree which forms to rank as species and which as varieties.
– Charles Darwin, The Origin of Species
Haskell is my favorite programming language, but
]]>I refer to those genera which have sometimes been called “polymorphic”, in which the species present an inordinate amount of variation; and hardly two naturalists can agree which forms to rank as species and which as varieties.
– Charles Darwin, The Origin of Species
Haskell is my favorite programming language, but it is not simple—a language with a strong static type system and nonstrict semantics is one that must deal in subtlety and nuance. However, typeclasses—one of Haskell’s most fundamental tools for the construction of effective abstractions—admit a surprisinglysimple implementation, one drastically simpler than the corresponding features of ALGOLstyle scripting languages. This piece aims to be a brief, veryhighlevel overview of how typeclasses are resolved, how they operate at runtime, and how the XTypeApplications
extension to GHC provides a more granular approach for such resultion, one that enables sophisticated and subtle APIs in realworld problems.
A computer program is a conversation between a human and a machine. A limited conversation, yes, and one often marred by profanity and frustration, but one informed in structure and style by human language, both the languages with which we communicate with our fellow humans and the inner language with which we organize our thoughts. One of the defining features of human language is the ability for one word to mean many things: one signifier, many referents. We can fix a car, we can fix a breakfast, and we can fix an election—though these activities are substantially different, the speakers of English have collectively decided that there is an underlying similarity between them, and that the word ‘fix’ captures this similarity, giving us one versatile word rather than three^{[1]} situationspecific ones. In other words, spoken language provides polysemy–the ability for a word or phrase to refer to different things based on context. Wordplay, metaphor, simile, metonymy, synecdoche: language, and by extension the whole of human thought, delights in polysemy’s nuance.
In programming, we refer to this phenomenon as polymorphism. Computers, in contrast with humans, do not delight in polymorphism. Resolving the meaning of a polymorphic statement entails choice, and computers are notoriously bad at making correct choices. But effective use of polymorphism is often, if not always, at the heart of wellwritten code, so nearly all programming languages^{[2]} provide means for polymorphism. Because teaching computers to make predictable, sensible choices is a complicated prospect, most programming languages use complicated systems to resolve polymorphism:
Haskell is different. For all its reputation for being a language that is difficult to learn^{[4]}, its system for providing polymorphism is simple, so simple that when I first learned of it I felt vaguely cheated in some way. Let’s take the notion of equality–(==)
, one of the most common polymorphic functions–and explore how Haskell represents that, both to the programmer and within its runtime system. (If you’re already fluent in Haskell and familiar with dictionarypassing style, you might want to skip ahead to the next section, in which I start playing around with explicit type applications.)
Polymorphism is a great and necessary thing, but how should a compiler or interpreter implement it? From an objectoriented perspective, in which code and data are intertwined, the most straightforward solution to provide is to have some sort of lookup table (usually called a ‘vtable’, C++ argot for ‘virtual method table’) present in the inmemory layout of a given object. Due to the fact that Haskell lacks objects but possesses a strong type system, vtables become unnecessary: the target of polymorphic calls is always resolvable at compile time. If, at compile time, your program contains a type variable that cannot be resolved, GHC rejects the program with an error.
Let’s take a look at one of Haskell’s most fundamental typeclasses and the mechanisms with which GHC compiles this typeclass into its intermediate language, which lacks typeclasses.
class Eq a where
(==) :: a > a > Bool
Haskell’s equality operator is implemented atop the Eq
typeclass. Even if you don’t speak Haskell, this should look reasonably familiar if you’ve ever looked at Equatable
in Java or IEquatable in C#.
This interface provides a polymorphic function (==)
, one that compares two values (of the same type) for equality. It is polymorphic in one type variable, a
in the above declaration. We can use this function over any type that implements the Eq
interface, as long as a
can be resolved, at some point, to a concrete type like Int
or String
. We can write a useful function with Eq
.
allEqual :: Eq a => [a] > Bool
allEqual [] = True
allEqual (h:rest) = all (== h) rest
Here we define an allEqual
function that is polymorphic in its argument, taking a list of any values implementing Eq
. The constraint, on the lefthandside of the =>
, introduces a type variable named a
, corresponding to a given type that implements the Eq
class. (We call this a ‘constraint’ because it constrains the set of types that this function will accept.)
Here’s the secret to Haskell’s implementation of polymorphism: during compilation, GHC turns that =>
into an >
. That’s right: a constraint on a function becomes a parameter to that function^{[5]}. allEqual
is a function that takes one argument, but from the runtime’s perspective it takes two. This new argument is called a dictionary, and the underthecovers application of dictionaries to polymorphic functions is called dictionarypassing style^{[6]}.
data EqDict a = EqDict { dictEqual :: a > a > Bool }
Under the dictionarypassing model, this typeclass is represented in a manner similar to this Haskell data type—a data structure, parameterized in terms of an input type, that holds references to concrete implementations of the methods referenced in the typeclass.
When types are correctly resolved, an EqDict Int
dictionary will contain in its dictEqual
field the correct implementation of ==
for Int
values. If, during compilation, a polymorphic type cannot be instantiated or inferred to be a concrete type, typechecking will fail. This is the source of the dreaded Ambiguous type variable
error from GHC: if a given type variable cannot be resolved to a concrete type, we can’t build an EqDict
for it, since we don’t know how to fill in the dictEqual
field.
This has some resemblance to vtables from objectoriented language, but there’s a crucial difference: though a data type may implement Eq
, there is no EqDict
carried around within its inmemory representation. Though an Int
may implement dozens of different interfaces, I can pass them around as data and data alone: polymorphism is provided at callsites, not shoehorned into data structures themselves.
Let’s consider how this would look if Haskell didn’t have typeclasses:
allEqualDictionary :: EqDict a > [a] > Bool
allEqualDictionary dict [] = True
allEqualDictionary dict (h:rest) = all ((dictEqual dict) h) rest
This function is equivalent in functionality to our previous one, but we’d have to build an EqDict
every time we invoked the (==)
function, which is both tedious and inefficient. GHC takes care of this for us.
That’s it. No fancy algorithm, no superclasses or metaclasses or prototypes, no vtables attached to data structures, no runtime type inference. Just a record type for every typeclass. Remarkable.
I mentioned that GHC will reject programs in which it cannot infer a concrete type for every type variable. So what do you do if GHC can’t infer which type to use (or, in other words, which dictionary to pass)? Well, the simplest option is to use an inline type signature.
let tenThousand = 10000 :: Integer
 Ambiguous: it's unclear which 'Num' instance to return from fromIntegral.
print (fromIntegral tenThousand)
 Unambiguous: by narrowing the 'Num' instance to that of 'Word32', we
 know which Num and Show instances to use.
print (fromIntegral tenThousand :: Word32)
If we have some constraint–Eq a
, let’s say–we can, with a type signature, specify an explicit, rather than inferred, type should use. The number 10,000 goes from a polymorphic value to a concrete Integer
. Similarly, the result of fromIntegral
, which yields a value of some type implementing the Integral
typeclass, is established as a Word32
with the explicit signature :: Word32
. (You can’t go the other way: it is not legal to “upcast” a function of Int > Int
to Num a => a > a
).
Ultimately, what we’re doing with this inline type signature is specifying otherwiseunresolvable entries in the given call’s dictionary. Thus, a question: what if, instead of inserting inline type signatures, we had a moregeneral syntax specifically for this purpose, one that allowed us to state exactly which types should be passed to a given function’s dictionary?
Good news: we do. The XTypeApplications
extension to GHC Haskell landed in GHC 8.0, providing syntax for visible type applications, as described in the eponymous and excellent paper by Richard Eisenberg, Stephanie Weirich, and Hamidhasan Ahmed.
allEqual :: Eq a => [a] > Bool
This was the type of our allEqual
function above. When GHC has compiled Haskell down to its intermediate language, we know that this Eq a
parameter will be represented with a dictionary.
 n.b.: This is not legal Haskell syntax
allEqual :: @EqDict > [a] > Bool
In this pseudoHaskell syntax, we use the @
prefix to mean “a dictionary for”. If we applied allEqual
to a list of Char
values, the dictionary passed in would be represented as @Char
.
The purpose of the XTypeApplications
extension is to let us, using the @
syntax, manually specify the type and dictionary used for a given polymorphic call. (Unlike inline type signatures, explicit type annotations cannot be applied to values: they are always part of function calls.)
λ :set XTypeApplications  or {# LANGUAGE TypeApplications #}
And since explicit type applications are not part of Haskell 2010, we have to toggle their presence with a LANGUAGE
pragma. When we turn this on, we can start with a simple example.
λ :t 100
100 :: Num p => p
An interesting feature of Haskell is that its integer literals are untyped. This means that, in the absence of any other calls that might resolve a given numeric literal to a concrete type such as Int
, Integer
, or Double
, its type is polymorphic: that 100
can stand for any type^{[7]} that implements the Num
interface.
λ :t id @Int32 100
id @Int32 100 :: Int32
But when we use the id
function and a type application, we can constrain the type that id
takes, forcing that literal to be a given type. Given that you can’t apply a type application directly to a literal (type applications only work in function contexts), this hardly seems a benefit over using an explicit type signature, no call to id
required:
λ :t (100 :: Int32)
100 :: Int32
Yet TypeApplications
’s usefulness is more apparent in a more polymorphic context. Let’s define a rather unprincipled function to demonstrate this.
unprincipledAdd :: (Integral a, Integral b)
=> a > a > b
unprincipledAdd a b = fromIntegral (a + b)
unprincipledAdd
takes two values of some Integral
type and adds them together, coercing the result of that addition into some other type implementing Integral
. This is fine to define, but at invocations of unprincipledAdd
we may run into trouble.
print (unprincipledAdd 1 2)
If we write the above call in Haskell code^{[8]}, GHC will reject our program, as it cannot figure out what type to resolve for the numeric literals: they could be Int32
, Integer
, Word16
, Double
—anything that implements the Num
typeclass.
print (unprincipledAdd @Int @Word 1 2)
In contrast, the call with explicit type applications will typecheck successfully. The above call can be expressed with explicit type signatures, too:
print ((unprincipledAdd (1 :: Int) (2 :: Int)) :: Word)
In contrast with our previous example, I’d argue that the explicit type signatures make this version significantly more difficult to read.
Visibile type applications also play nice with inference:
someFunction @Int @_ @(Vector _) a b c
The @_
syntax, like the _
character in a patternmatching context, means something akin to a wildcard: it lets us rely on the type inference engine to infer a particular type variable, while letting us continue on and specify the values for further parameters. Here our invocation means “the first parameter of this function is applied to Int
, the second should be inferred by the type system, and the third is some Vector
containing a type that I want inferred.”
someFunction @Int a b c
If we only need to specify the first N type variables, leaving the subsequent values up to the type inference engine, we need only provide as many variables as we need: GHC will apply the wildcard application to all further type variables.
Visible type applications are essential for idiomatic use of the fusedeffects
library. While a complete explanation of the use of and motivation behind effects systems is out of scope for this particular blog post, it suffices to consider an effectful computation that has access to two stateful variables, of type Foo
and Bar
.
effectful :: (Member (State Foo) sig, Member (State Bar) sig, Carrier m) => m ()
fusedeffects
provides get
and put
functions that manipulate any type provided by the Member State
constraints. Though pleasingly polymorphic, this can lead to situations that stump the type checker:
stringRepr :: (Member (State Foo) sig, Member (State Bar) sig, Carrier m) => m String
stringRepr = do
var < get
pure (show var)
It is not clear from this code whether the get
invocation should return a Foo
or a Bar
—in other words, whether it should use the State Foo
constraint or the State Bar
constraint. A visible type application clears that right up.
{# LANGUAGE TypeApplications #}
stringRepr = do
var < get @Foo
pure (show var)
Thanks to the visible type application (more readable than an explicit signature around the get
invocation or, with XScopedTypeVariables
, around var
), the typechecker is no longer stuck, and we can continue on our merry way.
Conclusion c => c
Most languages have simple evaluation semantics and complicated polymorphism semantics. Haskell is the opposite: its nonstrict evaluation strategy is subtle, but its strategy for resolving polymorphic functions is simple, and places no requirements on the memory layout of Haskell data structures, in contrast with most objectoriented languages.
It’s insights like these that prove the worth and merit of exploring unconventional programming languages. While objectoriented programming has been one of the great success stories in all of software engineering, traditional OOP approaches often entail surprising restrictions. In this way, the despairing air of the Darwin quote that opened this piece is not applicable: given the richness of polymorphism in human language, there are surprisingly simple ways to embed it within a programming language. I’m sure he’d be relieved to know that. Or possibly not. The man was kind of a downer.
I’d like to thank Ayman Nadeem, Peter Berger, Rick Winfrey, and Kenny Foner for reviewing drafts of this post.
The Oxford English Dictionary asserts that the word ‘run’ has the most definitions of any word in the language; the verb alone has 645 meanings. If every such meaning were given its own word, it would take more than four months to learn them all, assuming that the average person can learn ~5 words per day. ↩︎
Even C has _Generic
macros now, which provide a form of compiletime polymorphism. ↩︎
Unless you use @property
, which is much closer to the Smalltalk school of thinking than Simula. ↩︎
(a reputation that is sometimes unfair and sometimes extremely welldeserved) ↩︎
An interesting consequence of this is that you can use =>
in more than one place in a type signature: the signatures Ord a => Ord b => a > b > Bool
and (Ord a, Ord b) => a > b > Bool
are equally valid. ↩︎
Because GHC’s type system is significantly more featureful than the type system specified in the Haskell Report, the details of its typeclass resolution are a bit more complicated—things like type families introduce subtleties to the dictionarypassing approach. You could, however, sit down and implement your own Haskell2010 compiler with dictionarypassing style. ↩︎
such as the excellent Num
instance for functions ↩︎
If you try this upcoming code sample in ghci
, it will execute without error, whereas if you try it in a standard Haskell source file it will fail to typecheck. This is because ghci
uses a set of type defaulting rules to resolve a sensible type for polymorphic literals. This feature is actually present in Haskell itself (section 4.3.4 of the Haskell Report has the gory details), but is tremendously obscure and rarely, if ever, seen in realworld code. ↩︎
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.
]]>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 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 provided continuation.) 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 continuation 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 continuationpassing 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
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: = XFANIN = (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 = ORRRR = as ‘or’ can be a helpful mnemonic: we can see that f ORRRR 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 continuationpassing style, but instead of a function over Stack
values, our continuation will handle Result
values. 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 continuation 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 continuation 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 ORRRR
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 ORRRR
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 ORRRR
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
:
hypo :: Functor f => RAlgebra f b > RCoalgebra f a > a > b
hypo 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 referred 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.
I remain very grateful your readership. The next entry will discuss the fusion laws that folds, unfolds, and refolds all possess, and how we can use these laws to make realworld use of these constructs extremely fast.
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 recursion schemes more elegant and ergonomic
]]>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
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 a a
project (Call a b) = CallF a a
 and so on and so forth
This is 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 part V, we discuss refolds—hylomorphisms 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 three 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 CourseofValue (Co)Iteration, Categorically, by Tarmo
]]>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 applying fmap
, 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
values, 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 someWorkerFunction >>> h
But what type should someWorkerFunction
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.) After adding this type hole, GHC yields the following typehole message:
histo :: Functor f => CVAlgebra f a > Term f > a
histo h = out >>> fmap _worker >>> h
/Users/patrick/src/morphisms/src/Main.hs:14:24: error:
• Found hole: ‘_worker’ with type :: Term f > Attr f a: mystery :: Functor f => (f a > a) > Term 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 :: CVAlgebra Nat 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
remaining = map (given ) validCoins
(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)
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 /futu/morphisms—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
#+RESULTS
/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 Continue
value, we continue recursing into it, perpetuating the unfold operation. When we encounter a Stop
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 a Continue
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.)
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 Continue
into this Root
, giving it the subsequent seed (so that we get a new RNG value).
0 > Root (Continue 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 Continue
value to continue our fold at the top of that Stalk
:
Upwards > Stalk (Continue 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 Stop
and two Continues
.
Branch > Fork  grow a stalk then continue the fold
(Stop (Stalk (Continue next)))
 halt immediately
(Stop Bloom)
 again, grow a stalk and continue
(Stop (Stalk (Continue next)))
Note how, even though we specify the construction of a Stalk
in the first and third slots, we allow the fold to Continue
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 (Continue left)
(_, 10) > Bloom
(Flower, _) > Bloom
(Upwards, _) > Stalk (Continue right)
(Branch, _) > Fork (Manual (Stalk (Continue left)))
(Manual Bloom)
(Manual (Stalk (Continue 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 Continue <<< f)
apo :: Functor f => RCoalgebra f a > a > Term f
apo f = futu (fmap (either termToCoattr Continue) <<< 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, How Si Wei 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.
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’ ↩︎
On the last episode of this exploration of recursion schemes, we defined the catamorphism, our first generalized fold operation over any recursive data structure. Catamorphisms admit a beautiful definition and are useful in hosts of situations. But they have their limits: in this installment, we’ll explore these limits, and
]]>On the last episode of this exploration of recursion schemes, we defined the catamorphism, our first generalized fold operation over any recursive data structure. Catamorphisms admit a beautiful definition and are useful in hosts of situations. But they have their limits: in this installment, we’ll explore these limits, and we’ll discuss how to get around them by introducing a more powerful construct—the paramorphism.
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 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
.
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' = 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) = Pretty.int i
fastPretty _ (Ident s) = Pretty.text s
 uninteresting cases omitted, blah blah blah
 Here's where it gets interesting. We're going to look
 at the first argument to determine whether this is a
 `Call` node with the function name (an `Ident`) named `id`.
 If so, we'll just return the only argument provided.
fastPretty (In (Call { func = "id" }))
(Call {args = [theArg]}) = theArg
 Otherwise, we won't look at the first `Term` argument,
 and just glom the name and the parenthesized and
 commaseparated arguments together.
fastPretty _ (Call f args) = f <> Pretty.parens (mconcat ("," `Pretty.punctuate` args))
 Straightforward ALGOLstyle syntax for the remaining cases
fastPretty _ (Index it idx) = it <> Pretty.brackets idx
fastPretty _ (Unary op it) = Pretty.text op <> it
fastPretty _ (Binary l op r) = l <> Pretty.text op <> r
fastPretty _ (Paren ex) = Pretty.parens ex
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 (shudder) exceptions[fn:4].
So, just as we expressed ana
by reversing the arrows of cata
, we can express apo
by reversing the arrows of para
:
para :: Functor f => RAlgebra' f a > Term f > a
para f = out >>> fmap fanout >>> f where fanout = id &&& para f
apo f :: Functor f => RCoalgebra f a > a > Term f
apo f = In <<< fmap fanin <<< f where fanin = ???
It may not be immediately obvious how to implement fanin
. But, when you reverse the arrows of the fanout
definition above (I have omitted said reversal for brevity’s sake), you’ll discover that you yield a function that takes an Either (Term f) a
and returns a Term f
.
fanin :: Either (Term f) a > Term f
As such, our function will handle this either by applying id
in the case of a Left
value (as getting a Term
means that we can just return the Term
) and recursing with apo
in the case of a plain old a
value, out of which we ultimately yield a Term
, thanks to the ultimate signature of apo
. And Haskell’s 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, 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. ↩︎
It would be a bad idea 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 four 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 four simple recursion schemes, explore how they relate to each other, and I’ll offer up some example sitations (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.
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
values 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
to Int
), 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
? Does it typecheck?
You’re damn right 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 (one for the identifier add
, one for the function call, and two for the . 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 as 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
values containing Doc
values 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:
prettyPrint (Call f as) = f <> P.parens (P.punctuate "," as) f(a,b...)
prettyPrint (Index it idx) = it <> P.brackets idx a[b]
prettyPrint (Unary op it) = (P.text op) <> it op x
prettyPrint (Binary l op r) = l <> (P.text op) <> r lhs op rhs
prettyPrint (Paren exp) = P.parens exp (op)
Applying prettyPrint
to our example call
datum should yield a nice representation:
λ> cata prettyPrint call
add(10,10)
One final detail: we can represent our bottomUp
function in terms of cata
. Indeed, bottomUp f
is just cata f
, with the additional step of stuffing the accumulator value into a Term
with In
before handing it off to f
:
bottomUp f = cata (In >>> f)
This formulation of recursive traversals sure is elegant—but elegance isn’t enough. The real reason to use catamorphisms is that every catamorphism obeys a set of laws.^{[6]} The simplest law is the identity law:
cata In = id
This is pretty straightforward. The In
constructor, which provides the fixedpoint of a functor, is the simplest algebra: given a functor f
wrapping a Term f
, it turns it into a Term f
, leaving the value untouched. And iterating over the contents of a structure without changing them is clearly the identity function.
Catamorphisms can also fuse:
 given alg :: f a > a
 and func :: f a > f
cata (alg >>> fmap func) =>
(cata alg) >>> func
This is an extraordinarily powerful property of catamorphisms: in the above example, it allows you to avoid successive invocations of fmap.
Catamorphisms also compose: given an algebra over a given type
 given alg :: f a > a
 and func :: f a > g a
cata (f >>> In) >>> cata g
==> cata (f >>> g)
That is to say, the result of composing two separate catamorphisms is equivalent to a single catamorphism using the combination of the contained algebras. This is amazing, almost magically so: the composition law allows us to turn two separate calls to cata
into one.
Thanks to Colin Barrett and Rob Rix for reading drafts of this essay, and thanks to Rob for pushing me to publish it.
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. GHC’s support for pattern synonyms can also eliminate applications of In
. ↩︎
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, The Functor
class is broader than just the concept of 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 the purists 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. ↩︎
This is assuming that we’re working in a purely functional language (and that nobody’s calling out to unsafePerformIO
). ↩︎
In 1991, Erik Meijer, Maarten Fokkinga, and Ross Paterson published their nowclassic paper Functional Programming with Bananas, Lenses, Envelopes and Barbed Wire. Though this paper isn’t widely known outside of the functional programming community, its contributions are astonishing: the authors use category theory to express a set of simple,
]]>In 1991, Erik Meijer, Maarten Fokkinga, and Ross Paterson published their nowclassic paper Functional Programming with Bananas, Lenses, Envelopes and Barbed Wire. Though this paper isn’t widely known outside of the functional programming community, its contributions are astonishing: the authors use category theory to express a set of simple, composable combinators, called recursion schemes, that automate the process of traversing and recursing through nested data structures. Though recursion schemes predate Meijer et. al’s work, this paper brings the enormous abstractive power of category theory to bear on the subject of traversing data structures—it’s a magnificent example of how categorytheoretical concepts can bring both rigor and simplicity to daytoday programming tasks.
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 Haskell Programming from First Principles.
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.
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 isn’t good code. It’s clumsy. Four out of this function’s six lines are dedicated to the simple yet tedious task of ensuring that flatten
propery recurses into its argument’s subexpressions—not only is this boring to write, but any future changes (such as added constructors or fields) to Expr
will force us to rewrite it. (I’ll refer to recursion written in this style as explicit recursion, in contrast with the implicit recursion provided by recursion schemes.) In addition, it’s extremely easy to make mistakes in this definition—the syntatic noise that the primitive recursion introduces renders it hard to spot a missing recursive invocation of flatten
, yet even one such omission introduces a critical bug.
We can, however, bring some sanity to this madness by writing a function apply
that, given a function f
operating on Expr
values, 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)
This function decouples the definition of a recursive function from its recursive application. with it, 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' :: Expr > Expr
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 ExprF 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 an expression differs from its predecessor in that we’ve added a type variable a
and replaced all recursive occurrences of the Expr
type with it. (By convention, we append the suffix F
to the type name and constructors of expressions in this formulation; the reason for this will become clear in a moment. 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) > ExprF a > ExprF 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: with GHC’s DeriveFunctor
extension, we can just add Functor
to the list of classes our Expr
declaration derives, alongside Show
and Eq
:
data ExprF a
= IndexF a a
 CallF [a]
 UnaryF String a
 BinaryF a String a
 ParenF a
 LiteralF 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
values, 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
values:
ExprF Lit
represents an expression with no subexpressionsExprF (ExprF Lit)
represents expressions with at most one more layer of subexpressions.ExprF (ExprF (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 = ExprF (ExprF (ExprF (ExprF …)))
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
values.
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 ...)))
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 operators on functions, and in turn we can describe an Expr a
where a
represents an infinite stream of nested Expr
values.
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 f
in this equation, in order to see what it looks like to construct and deconstruct the fixedpoint of an Expr
value. Using GHC’s TypeApplications
extension to set the value f
equal to ExprF
, let’s ask GHCi the type signature of In
over ExprF
values.
:t In @ExprF :: ExprF (Term ExprF) > Term ExprF
In @ExprF :: ExprF (Term ExprF) > Term ExprF
This tells us that in order to end up with a Term ExprF
we have to pass an ExprF
that, if it has children, contains further values of type Term ExprF
. We apply this In
constructor at each level of a nested ExprF
. This allows us arbitrarilynested types, while still permitting the vastlyconvenient Functor
instance and its attendant fmap
.
The type Term ExprF
will show up often, since it is the type equivalent to our old definition of Expr
. Let’s declare a type synonym for this.
type Expr' = Term ExprF
A more idiomatic way to declare Term
is to use a record field rather than declaring an unwrapper function, and to make this declaration a newtype
, which allows GHC to optimize out construction and deconstruction of Term
values with In
and out
.
newtype Term f = In { out :: f (Term f) }
From these definitions, 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
values. 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, the following algorithm for traversing the fixedpoint of a functor:
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
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
values that wrap arbitrarilynested Expr
values:
flattenTerm :: Expr' > Expr'
flattenTerm (In (ParenF e)) = e  remove all Parens
flattenTerm other = other  do nothing otherwise
flatten'' :: Expr' > Expr'
flatten'' = bottomUp flattenTerm
Given a function fn
mapping from Term
to Term
, 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.)
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 ƒ, we:
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 the myriad varieties of recursion schemes—apomorphisms, paramorphisms, and histomorphisms, just to name a few—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 the next installment of this series, we go on to 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 this notation, which 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 Functors.” ↩︎
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 Kestrels, Quirky Birds, and Hopeless Egocentricity. ↩︎
This function is provided by the Haskell prelude with the .
operator. ↩︎