When writing any non-trivial amount of code, we usually factor out the common logic or patterns to improve modularity, facilitate code reuse and avoid repeating ourselves. Recursion schemes is just about that. With recursion schemes you can factor out the recursion patterns in your code, so that you don’t need to write the same types of recursion over and over again. This may sound a little magical to those who aren’t familiar with recursion schemes, but it really isn’t.

This post aims to provide an absolutely elementary introduction to recursion schemes using Scala. There are a few good introductory posts on recursion schemes in Haskell, but I haven’t seen one for Scala, so here we go.

In this post I will use a single example, the factorial function, throughout the post. Calculating factorials is by no means the most striking use case of recursion schemes, but it is suitable for an introductory post. The purpose of this post is not to convince anyone that recursion schemes are useful in the real world - that has already been proven beyond doubt. The purpose is to explain how recursion schemes work to those who are unfamiliar with the concept, in the simplest possible way. To that end, a simple, linear-recursive, toy example like factorial works well in my opinion. The resources in the Further Reading section offer more real-world examples for those interested.

For the same reason, the implementation of recursion schemes in this post is a toy implementation - it is not stack-safe, not as general as it can be, and cannot handle infinite recursions. It just serves the purpose of a basic introduction of how things work. If you are interested in a production-ready Scala implementation of the recursion schemes, you’ll want to look at the Matryoshka project.

# A Recap of Fixpoint Combinator and Fixpoint Type

Recursion schemes are based on fixpoints (also known as fixed points). So before introducing recursion schemes, let’s have a quick recap of how fixpoint combinators and fixpoint types work.

## Fixpoint Combinator

One of my previous posts, The fix Combinator in Scalaz, contains an introduction of the fixpoint combinator. A fixpoint combinator `fix` is a combinator such that for all functions `f`, `fix(f) = f(fix(f))`. In other words, `fix(f)` is a fixpoint of `f` (more precisely, it is the least fixpoint of `f`). This allows you to convert a recursive value into a non-recursive one, by delegating the recursion to `fix`. The way to do it is: suppose you have a recursive value `f`:

``````f = <body containing f>
``````

Define `<body containing f>` as `g(f)`, i.e.,

``````g(f) = <body containing f>
``````

Now we have `f = g(f)`, so `f` is a fixpoint of `g`. And it happens to be the least fixpoint of `g`, hence `f = fix(g)`. Note that `g` is no longer recursive because its body doesn’t contain `g`. This is how you use the fixpoint combinator to factor recursion out of a recursive function, leaving only the “core logic” in the original function.

## Fixpoint Type

The way fixpoint types work is exactly the same as the fixpoint combinator, except that they work at the type level. The following is a simple fixpoint type:

``````final case class Fix[F[_]](unfix: F[Fix[F]])
``````

That is, given a `Fix` of `F`, you can always get an `F` of `Fix[F]`, and vice versa. This can be used to factor recursion out of recursive types, similar as how we factor recursion out of recursive functions as explained above.

Suppose you have a recursive type `F`:

``````sealed trait F
final case class A(a: <type containing F>) extends F
``````

Similar as what we did at the value level, define `F` as `G[F]`:

``````sealed trait G[F]
final case class GA[F](a: <type containing F>) extends G[F]
``````

Then, `Fix[G]` is a type isomorphic to `F`, but without the explicit recursion as `F` does.

Recursion schemes is all about fixpoint types. Next let’s review a few different types of recursion schemes using the factorial example.

# Anamorphism

Anamorphism is one of the basic types of recursion schemes. It generalizes unfold, meaning you can use it to create a recursive structure based on a recursive type.

In a previous post, How Trampoline Works in Scala, I explained how to make the factorial function stack-safe using `TailRec`, which is a recursive type. The approach is basically building a structure on the heap using `TailRec` which mimics the call stack. For the sake of this post, we’ll use a simpler recursive type to represent the stack:

``````sealed trait StackR
final case class DoneR(result: Int = 1) extends StackR
final case class MoreR(stack: StackR, next: Int) extends StackR
``````

where `R` stands for “recursive”. This is a recursive type because one of the fields in `MoreR` is of type `StackR`.

We can use the following function to generate a structure representing the call stack for calculating the factorial of `n`:

``````def unfoldStackR: Int => StackR =
n => if (n > 0) MoreR(unfoldStackR(n - 1), n) else DoneR()

unfoldStackR(5)
// res0: StackR = MoreR(MoreR(MoreR(MoreR(MoreR(DoneR(1),1),2),3),4),5)
``````

Now we wish to build a similar structure using `Fix` and anamorphism, instead of explicit recursion. To do so, as explained before, we create a new type that adds a type parameter to `StackR`. We’ll call it `Stack`:

``````sealed trait Stack[A]
final case class Done[A](result: Int) extends Stack[A]
final case class More[A](a: A, next: Int) extends Stack[A]
// I don't know why these two "final"s have different colors. It's annoying.
``````

To use recursion schemes, `Stack` must be a functor, so we add a functor instance for `Stack`, together with two smart constructors to improve type inference.

``````import cats.Functor
import cats.implicits._

object Stack {
implicit val stackFunctor: Functor[Stack] = new Functor[Stack] {
override def map[A, B](sa: Stack[A])(f: A => B): Stack[B] =
sa match {
case Done(result) => Done(result)
case More(a, next) => More(f(a), next)
}
}

def done[A](result: Int = 1): Stack[A] = Done(result)
def more[A](a: A, next: Int): Stack[A] = More(a, next)
}
``````

As we can see, the field of case class `Done` does not use type `A`, so mapping over `Done[A]` is a no-op. `Done` is called the base case (or degenerate case, terminating case) for the `Stack` type. This is what terminates the recursion. If a recursive type does not have a base case, then if a value of that type exists, it must be infinitely recursive.

Anamorphism is a type of recursion scheme, which takes a function of type `A => F[A]` (also known as a Coalgebra) where `F` is a functor, and returns a function of type `A => Fix[F]`, that takes an `A` and unfolds it into a recursive structure, `Fix[F]`. The implementation is quite simple if guided by the type signature, in fact it is the only sensible implementation that compiles:

``````// Type A => F[A] is also known as Coalgebra.
def ana[F[_] : Functor, A](f: A => F[A]): A => Fix[F] =
a => Fix(f(a) map ana(f))
``````

That is, we only need to supply a coalgebra, `A => F[A]` which does not need to be recursive, in order to generate the recursive structure. This is what we mean by “factoring recursion out”: your coalgebra only needs to contain the core business logic, and the recursion is taken care of by `ana`.

The coalgebra for factorial would be:

``````val stackCoalgebra: Int => Stack[Int] =
n => if (n > 0) more(n - 1, n) else done()
``````

Feeding `stackCoalgebra` to `ana` should build a structure isomorphic to the one built by `unfoldStackR`:

``````ana(stackCoalgebra).apply(5)
// res1: Fix[Stack] = Fix(More(Fix(More(Fix(More(Fix(More(Fix(More(Fix(Done(1)),1)),2)),3)),4)),5))
``````

The `.apply` above, unfortunately, cannot be ommitted, because `ana` has a context bound on `F`, i.e., `F[_] : Functor`, which is desugared into an implicit parameter list. So if you write `ana(stackCoalgebra)(5)`, Scala will try to match `5` with the implicit parameter, `Functor[F]`, which will give a compilation error.

# Catamorphism

Previously given an integer `n`, we unfold it into a stack structure representing the computation of the factorial of `n`. Now we need to fold it back into an integer, the factorial of `n`. To do so we can use catamorphism, which is a generalized fold.

Let’s first have a look at what it’s like to fold the stack using explicit recursion:

``````// Explicit recursion with StackR
def foldStackR: StackR => Int = {
case DoneR(result) => result
case MoreR(acc, next) => foldStackR(acc) * next
}

// Explicit recursion with Fix[Stack]
def foldFixStack: Fix[Stack] => Int =
_.unfix match {
case Done(result) => result
case More(fix, next) => foldFixStack(fix) * next
}

(unfoldStackR andThen foldStackR)(5)
// res2: Int = 120

(ana(stackCoalgebra) andThen foldFixStack)(5)
// res3: Int = 120
``````

Catamorphism is the dual of anamorphism, and can be implemented by reversing the arrows in `ana`:

``````// Type F[A] => A is also known as Algebra.
def cata[F[_] : Functor, A](f: F[A] => A): Fix[F] => A =
fix => f(fix.unfix map cata(f))
``````

As with `ana`, we only need to provide an algebra, `F[A] => A`, and the recursion is taken care of by `cata`. The algebra for folding the stack would be

``````val stackAlgebra: Stack[Int] => Int = {
case Done(result) => result
case More(acc, next) => acc * next
}

(ana(stackCoalgebra) andThen cata(stackAlgebra))(5)
// res4: Int = 120
``````

# Hylomorphism

Hylomorphism is the composition of anamorphism and catamorphism, and can be implemented simply as

``````def hyloSimple[F[_] : Functor, A, B](f: F[B] => B)(g: A => F[A]): A => B =
ana(g) andThen cata(f)
``````

`hyloSimple` first uses `ana` to build a potentially large structure, before using `cata` to tear it down. Alternatively, we can implement hylomorphism directly without using `ana` or `cata`, which “fuses” the anamorphism and the catamorphism, meaning at no time do we have a large `Fix` structure in memory.

``````def hylo[F[_] : Functor, A, B](f: F[B] => B)(g: A => F[A]): A => B =
a => f(g(a) map hylo(f)(g))

hylo(stackAlgebra)(stackCoalgebra).apply(5)
// res5: Int = 120
``````

To see how `hylo` behaves differently than `hyloSimple`, note that `hylo` does not involve `Fix` in its implementation, so it doesn’t create any `Fix`. All it does is to create and map on `More[Int]` and `Done[Int]`, such as `Done(1)`, `More(1, 2)`, `More(2, 3)`, etc.

# Paramorphism

Paramorphism is also a generalization of fold. It is an extension of catamorphism, and offers more power. Here’s the type signature and implementation:

``````def para[F[_] : Functor, A](f: F[(Fix[F], A)] => A): Fix[F] => A =
fix => f(fix.unfix.map(fix => fix -> para(f).apply(fix)))
``````

We can implement `cata` in terms of `para`:

``````def cataViaPara[F[_] : Functor, A](f: F[A] => A): Fix[F] => A =
para(((_: F[(Fix[F], A)]).map(_._2)) andThen f)
``````

Paramorphism is more powerful than catamorphism in the sense that in the algebra `f`, we not only have an `F[A]` to work with, but we also have an `F[Fix[F]]`, which means we have access to the `Fix` structure that yields the `A` when being folded.

For example, if we use `para` to fold our stack corresponding to the calculation of the factorial of 5, then instead of seeing `More(acc=24, next=5)` in one of the steps, we will also have access to the `Fix` structure that generated 24, i.e.,

``````Fix(More(Fix(More(Fix(More(Fix(More(Fix(Done(1)),1)),2)),3)),4))
``````

This is not particularly useful for calculating factorials using our `Stack` type, because `Stack` already stores the accumulated value `acc` in `More`. However, paramorphism does allow us to calculate factorials using the following simpler type, `NatR`, representing natural numbers:

``````sealed trait NatR
case object ZeroR extends NatR
final case class SuccR(prev: NatR) extends NatR
``````

Same as before, we add a type parameter for `NatR` to get rid of the explicit recursion. We call it `Nat`, and implement its functor instance.

``````sealed trait Nat[A]
final case class Zero[A]() extends Nat[A]
final case class Succ[A](a: A) extends Nat[A]

object Nat {
implicit val natFunctor: Functor[Nat] = new Functor[Nat] {
override def map[A, B](na: Nat[A])(f: A => B): Nat[B] =
na match {
case Zero() => Zero()
case Succ(a) => Succ(f(a))
}
}
}
``````

The `Succ` type has one less field compared to `More`, but it can be recovered using the `Fix` structure that we have access to thanks to paramorphism.

``````val natAlgebraPara: Nat[(Fix[Nat], Int)] => Int = {
case Zero() => 1
case Succ((fix, acc)) =>
??? * acc
}
``````

We need to convert a `Fix[Nat]` to an `Int`, representing the next integer to be multiplied, and replace `???` with it. To do so, we can use `cata` by feeding it an algebra from `Nat[Int]` to `Int`:

``````val natAlgebra: Nat[Int] => Int = {
case Zero() => 1
case Succ(n) => n + 1
}

val natAlgebraPara: Nat[(Fix[Nat], Int)] => Int = {
case Zero() => 1
case Succ((fix, acc)) =>
cata(natAlgebra).apply(fix) * acc
}
``````

We can now test it by using `ana` to generate a `Fix[Nat]` and then use `para` to fold it:

``````val natCoalgebra: Int => Nat[Int] =
n => if (n == 0) Zero() else Succ(n - 1)

(ana(natCoalgebra) andThen para(natAlgebraPara))(5)
// res6: Int = 120
``````

# Apomorphism

Apomorphism is the dual of paramorphism, and is an extension of anamorphism.

``````def apo[F[_] : Functor, A](f: A => F[Either[Fix[F], A]]): A => Fix[F] =
a => Fix(f(a) map {
case Left(fix) => fix
case Right(aa) => apo(f).apply(aa)
})
``````

Note that in addition to reversing the arrows in `para`, we also change `F[(Fix[F], A)]` to `F[Either[Fix[F], A]]`, since the dual of a pair (product type) is an `Either` (sum type).

Not surprisingly, `ana` can be implemented in terms of `apo`:

``````def anaViaApo[F[_] : Functor, A](f: A => F[A]): A => Fix[F] =
apo(f andThen (_.map(_.asRight[Fix[F]])))
``````

Compared to anamorphism, apomorphism gives you more control on when to stop the recursion. In anamorphism, the recursion is terminated when a node representing the base case (e.g., `Done` or `Zero`) is visited, on which the `map` function is a no-op. In apomorphism, the recursion can be terminated either by visiting a base case, or if `f` returns a `Left` containing a `Fix[F]`.

In our factorial example with `Stack`, using anamorphism, the recursion terminates at `n = 1` where `stackCoalgebra` returns the base case `Done`. Suppose we already have a `Fix` structure corresponding to `n = 3`, i.e., the last three steps of the fold:

``````val lastThreeSteps: Fix[Stack] = Fix(More(Fix(More(Fix(More(Fix(Done(1)),1)),2)),3))
``````

and we want the recursion to terminate on `n = 3`. We can use apomorphism to achieve that, by writing the corresponding coalgebra:

``````val stackCoalgebraApo: Int => Stack[Either[Fix[Stack], Int]] =
n => if (n > 3) more(n - 1, n).map(_.asRight) else lastThreeSteps.unfix.map(_.asLeft)
``````

When calling `apo(stackCoalgebraApo).apply(5)`, the recursion stops at `n = 3`, where `lastThreeSteps` is returned, instead of continuing the recursion.

# Histomorphism

Histomorphism is yet another recursion scheme for fold, and is more powerful than paramorphism. Histomorphism operates on an enhanced version of `Fix`, called `Cofree`, where each node in the structure is annotated by some value.

``````final case class Cofree[F[_], A](head: A, tail: F[Cofree[F, A]])
``````

The implementation of histomorphism requires a helper function `toCofree` to convert a `Fix[F]` to a `Cofree[F, A]`, where each node is annotated by the value generated by folding the corresponding `Fix[F]` structure:

``````def histo[F[_] : Functor, A](f: F[Cofree[F, A]] => A): Fix[F] => A = {
def toCofree: Fix[F] => Cofree[F, A] =
fix => Cofree(head = histo(f).apply(fix), tail = fix.unfix map toCofree)

fix => f(fix.unfix map toCofree)
}
``````

Recall that in catamorphism, at each step of the fold, you only have the value of the current fold, `F[A]`. In paramorphism, you additionally have access to the structure that generated that value, `F[Fix[F]]`. And in histomorphism, additionally, you also have the history of the values generated by the fold so far, or the history of the computation if you will.

In the factorial example, in the step corresponding to `n = 5`, in catamorphism we have `More(acc=24, next=5)`; in paramorphism we also have the structure that generated 24, i.e., `Fix(More(Fix(More(Fix(More(Fix(More(Fix(Done(1)),1)),2)),3)),4))`; in histomorphism we additionally have the history of the generated values, i.e., 1, 1, 2, 6, 24. Each of these values is encoded as the head of a `Cofree` structure, together with the corresponding node, which is in the tail.

This history of generated values is not really useful for the factorial example, since all we need is the current value, 24, and the next number to be multiplied, 5. But it should be easy to imagine that this can be useful in many other cases.

# Dynamorphism

Dynamorphism is the composition of anamorhpism and histomorphism. Similar as hylomorphism, it can be implemented either via `ana` and `histo`:

``````def dynaSimple[F[_] : Functor, A, B](f: F[Cofree[F, B]] => B)(g: A => F[A]): A => B =
ana(g) andThen histo(f)
``````

or directly:

``````def dyna[F[_] : Functor, A, B](f: F[Cofree[F, B]] => B)(g: A => F[A]): A => B = {
val cofree: F[Cofree[F, B]] => Cofree[F, B] =
fc => Cofree(f(fc), fc)
}
``````

The latter implementation avoids building the whole `Fix` structure.

# Futumorphism

The last recursion scheme we are going to cover in this post is futumorphism. It sounds like the dual of histomorphism, and it indeed is. The dual of `Cofree` is, unsurprisingly, the following `Free` type:

``````sealed trait Free[F[_], A]
final case class Continue[F[_], A](a: A) extends Free[F, A]
final case class Combine[F[_], A](fa: F[Free[F, A]]) extends Free[F, A]

object Free {
def continue[F[_], A](a: A): Free[F, A] = Continue(a)
def combine[F[_], A](fa: F[Free[F, A]]): Free[F, A] = Combine(fa)
}
``````

Each `Cofree` has a recursive structure tagged with a value of type `A`, while each `Free` has either a recursive structure, or a tag with a value of type `A`.

Given `Free`, here’s the definition and implementation of futumorphism:

``````def futu[F[_] : Functor, A](f: A => F[Free[F, A]]): A => Fix[F] = {
def toFix: Free[F, A] => Fix[F] = {
case Continue(a) => futu(f).apply(a)
case Combine(fa) => Fix(fa map toFix)
}

a => Fix(f(a) map toFix)
}
``````

Futumorphism is another unfold scheme, and is a more powerful one than apomorphism. Recall that in apomorphism, given a value of `A`, you either choose to continue the recursion by returning a `Right`, or choose to stop the recursion by returning a `Left`. In futumorphism, you can also choose to continue the recursion by returning a `Continue` or stop by returning a `Combine`. Additionally, you will be able to unfold multiple steps at a time, which you cannot do with apomorphism.

In anamorphism, to build the stack corresponding to the computation of the factorial of 5, you’ll need 5 recursive steps. In apomorphism, as we’ve seen earlier, you can effectively combine the last three steps together, by terminating the recursion at `n = 3` and returning `lastThreeSteps`. But once the recursion is terminated, it’s terminated. You cannot, for example, combine the first three steps together, and then resume the recursion. On the other hand, you can do that with futumorphism.

The reason you can do that with futumorphism is because a `Free` is either a single `A` wrapped in `Continue` or a recursive structure wrapped in `Combine`. To combine multiple steps together, just have your coalgebra return a `Combine` wrapping a recursive structure corresponding to those steps; to resume the normal recursion, just have it return a `Continue` wrapping a single `A`.

As an example, suppose we have the following recursive structure corresponding to the first three steps in building the stack corresponding to the factorial of 5 (i.e., `n = 5, 4, 3`):

``````val firstThreeSteps: Stack[Free[Stack, Int]] = more(combine(more(continue(3), 4)), 5)
``````

Then we can combine these three steps together, and resume the normal recursion at `n = 2`, using the following coalgebra:

``````val stackCoalgebraFutu: Int => Stack[Free[Stack, Int]] =
n =>
if (n == 5) firstThreeSteps
else if (n > 0) more(n - 1, n) map continue
else done() map continue

futu(stackCoalgebraFutu).apply(5)
// res7: Fix[Stack] = Fix(More(Fix(More(Fix(More(Fix(More(Fix(More(Fix(Done(1)),1)),2)),3)),4)),5))
``````

# Conclusion

Even though the factorial example used in this post is exceedingly simplistic and by no means shows the full power of recursion schemes, it still reveals a few benefits of using recursion schemes over explicit recursion.

Basically, as said before, it allows you to factor your recursion patterns out and only keep the core business logic in your program. This is usually beneficial but not always the case, depending on the problem you are solving, and more importantly your team. If other people in your team have also studied recursion schemes, then your collaboration can become significantly more productive. You simply mention “I’m doing histomorphism” and your teammates will immediately understand what kind of recursion you are doing. On the other hand, if you are the only person in the team that has studied it, and your teammates either do not have the time or do not have the desire to do so, then it could make your code harder to read or maintain by others.

Another benefit of factoring recursion out is that it helps eliminate bugs. In reality you often need to deal with recursive types which are much more complex than `Stack` or `Nat`. If you use explicit recursion, there will be a lot of recursive calls in your program, and if you forget one, your code may still typecheck, but will not have the correct behavior at runtime. Using recursion schemes, there will be no explicit recursion in your program so this class of bug is eliminated.

Last but not the least, it can sometimes significantly shorten your code. When you have a recursive type much more complex than `Stack` or `Nat`, it is possible that you sometimes need to write blocks of boilerplate code solely for the purpose of calling the recursion. If you take recursion out, it becomes no-op, and the whole block can be removed.

On a side note, the recursion scheme implementation in this post is not as general as it can be - for example, all recursion schemes in this post return either `A => Fix[A]` or `Fix[A] => A`, but `Fix` is only one of the possible types you can work with using recursion schemes. There are also lots of subtle details in a production-ready implementation (such as Matryoshka), especially for Scala, that this post does not cover.

The code shown in this post can be found here.