*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 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 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 Gabriel 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`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 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 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 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 *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 `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 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 `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-match^{[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 distributive-law-transformers like `distParaT`

and its siblings `distGHisto`

^{[8]} 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!

You 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). ↩︎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, arrow-reversed—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 formerly-free 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

`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.) ↩︎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 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.

↩︎`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 well-founded 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. ↩︎