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 showed 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 VeneYou might remember Uustalu and Vene from Primitive(Co)Recursion and Course-of-Value (Co)Iteration, Categorically, which introduced the histomorphism and futumorphism (as covered in the third part of this series).

, 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 real-world situations. However, a close read of Edward Kmett’s recursion-schemes 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 in-flight, 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 tailor-made 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 ad-hoc 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.

Lurking Similarities

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 in-flight a. And for histo, the carrier type is Cofree (Base t) a, representing an adaptive, ‘shapeshifting’ cache structure around the original t, storing all previously-computed 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.

Comonads for the Impatient

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 Gabriella Gonzales’s application of comonadic abstractions to real-world 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 wMost 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, arrow-reversed—version of m, which is used for Monad type variables.
  
  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 pattern-match 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 self-recursive type but mapping duplicate therein to ensure that all recursive elements are properly duplicated.

Comonads, Transform and Roll Out

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 backtracking-amenable 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 mini-DSL for describing the capabilities of our program. The MonadState and MonadReader interfaces provide her with built-in 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 well-established construct, though less well-known 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 comonadsIn 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 formerly-free variable on which some further computation depends.

. 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 self-similar 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.

A Comonad of One’s Own

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 self-similar 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 previously-computed 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, plug-and-play interface to recursion schemes. No longer are we limited to these three built-in combinators—instead, we can build our own, out of compositional, reusable parts, without the repetitive and error-prone 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.

The Means of Distribution

To understand the nature of distributive laws, it helps to examine the ones provided to us by the recursion-schemes 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 recursion-schemes 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 distributingYou 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.

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 existsIn the name of didacticism, I fibbed a little on this definition: in recursion-schemes, 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.)

:

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 recursion-schemes library, which uses even-more-general 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 off-putting 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 pattern-matching 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 pattern-matching code, which is no fun at all. But there is hope: recursion-schemes 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.

Glorious gcata

In the recursion-schemes 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)-w-algebra
      -> t                                   -- ^ fixed point
      -> a

This is… well, it’s a lot to take in. I’ve omittedIf 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 functor-of-comonads into a comonad-of-functors, which is then destructed with extract and sent through one last pass of the provided W-algebra 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.

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 recursion-schemes 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 recursion-schemes’s machinery for Base (which, though it provides a significant measure of real-world 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 w-algebra 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 w-algebra

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 W-algebra 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 right-hand-side 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, recursion-schemes has one last trick up its abstraction-drunk sleeve.

Zero-Effort Distributive Laws

Inside the guts of Data.Functor.Foldable, there lurks a nasty-looking 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 recursion-schemes, 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 distributive-law-transformer: 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 pattern-matchGiven 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 well-founded coercion. We have at least the small consolation that GHC will optimize away the overhead of wrapping and unwrapping Ledger values.

:

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 distributive-law-transformers like distParaT and its siblings distGHistoIt’s unclear to me why this is called distGHisto rather than distHistoT; drop me a line should you know.

and distZygoT make it straightforward to derive, given a comonad built of comonad transformers, a well-typed 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 mutually-recursive computations (zygo). There is a beauty to this treatment of recursion that is symphonic in its harmony.

Reversing the Arrows, One Last Time

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 Base-t-m 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 recursion-schemes 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.

Au Revoir, 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 recursion-schemes 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, Mendler-style catamorphisms and anamorphisms, Vanessa McHale’s entangled morphisms (dendro-, scolio-, and chema-), and the nigh-legendary 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!