# Anamorphisms

## Building up functors, recursively

This post is part of my series on recursion schemes.

In the last post in this series we looked at catamorphisms, transformations that walk a recursive data structure from the bottom up, collapsing a functor to its contained type at each step. This time, we’ll be looking another type of transformations, anamorphisms. We’ll look at the implementation and functioning of `ana`, (the function which creates anamorphisms,) a few example anamorphisms, and the relationship between anamorphisms and catamorphisms.

As we saw last time, catamorphisms are morphisms (transformations between two things), whose root “cata” (meaning down, back) reflects that they “tear down” a functor at each step. This time, we’re dealing with morphisms that build up a functor at each step. The root of “anamorphism” is “ana”, meaning “upwards”, and can be thought of in the sense of “anabolism” or “anabolic steroids”, terms relating to the building up of biological structures.

Here’s the implementation of `ana`, from `static-land-recursion-schemes`:

`export type Coalgebra<F, A> = A => HKT<F, A>;export function ana<F, A>(functor: Functor<F>,                          transformer: Coalgebra<F, A>,                          seed: A) : Fix<F> {  const transformed = transformer(seed),        childrenMapped = functor.map(          x => ana(transformer, x, functor),          transformed),        rewrapped = new In(childrenMapped);  return rewrapped;}`

The transformation function passed to `ana` is a `Coalgebra`, a function with the signature `A => F<A>`, where `F` is a functor. This is the opposite kind of transformation that we saw used by catamorphisms, which use functions of the signature `F<A> => A`. In category theory, when things are opposites of each other, (in a precise, mathematically-defined way,) they are known as “duals”. It’s conventional to put the prefix “co-” on something to name its dual, so the name “Coalgebra” literally just means “the opposite of an algebra”. (You may remember learning about the “domain” and the “codomain” of functions in middle or high school math classes — these names have the same relationship)

The body of `ana` is relatively straightforward: We have a value of type `A`, apply our coalgebra to it, getting a functor`F<A>`, and then we map over this new functor with `anamorphism`. In cases where the output of the coalgebra is a parameterized value, like an instance of `Plus` in our running example, this mapping digs deeper into the data structure, continuing recursively. In cases where the coalgebra produces a non-parameterized value, like `Num`, this mapping does nothing, and the recursion halts. Finally, we take the output of our mapping, wrap it in an `In` class, and return it.

Compare the functioning of `cata` and `ana`: `cata` takes an algebra `F<A> => A` and a value of type `Fix<F>`, and returns something of type `A`. `ana` takes a coalgebra `A => F<A>` and a value of type `A`, and returns a value of type `Fix<F>`. In its implementation, `cata` extracts a term from `In`, recurses into it, and then transforms it; `ana` transforms a term, recurses into it, and then wraps it in `In`. We can see that `ana` does things opposite of `cata`, and indeed, `ana` and `cata` are duals; it’s not inaccurate to think of anamorphisms as “co-catamorphisms”.

(Side note, for those familiar with currying: I describe `cata` as a function from an algebra and the fixed point of a functor to a value, and `ana` as a function from a coalgebra and a value to the fixed point of a functor. This is accurate, but limiting. Similar to how I showed there are two ways to look at `map` in my post on currying and uncurrying, if we curry `cata` we can see it as a function which “lifts” an algebra from tearing down a functor to tearing down the fixed point of that functor. Similarly, currying `ana` gives us a function that lifts a coalgebra from building up an instance of a functor to building up an instance of that functor’s fixed point.)

Anamorphisms are quite powerful, but they tend to be less intuitive than catamorphisms. For our first example, we’ll go through a basic catamorphism step-by-step, with extra type annotations added, to clarify exactly what’s happening. The key to thinking in terms of anamorphisms is remembering that the “seed type” `A` that our coalgebra operates on doesn’t exist in the final form of the produced structure, (which has type `Fix<F>`) and so can be used as a holder for intermediate values in the computation.

For the first example, let’s add the ability to express a `factorial` in the example arithmetic language that we’ve used for examples so far. (If you need a refresher, the code for the AST we’re working with is here). Rather than adding a new `factorial` class to our AST, we’ll add a function that produces nested multiplications equivalent to a factorial function. In other words, if the user calls `factorial(3)`, we want to produce the same data structure as if the user called `times(num(4), times(num(3), times(num(2), num(1))))`. Here is our first definition of this function:

`type IntermediateFactorial = {  type: 'recursive',  value: number} | {  type: 'terminal',  value: number};function factorial(base: number) : Expr {  return ana(exprFunctor, function(a: IntermediateFactorial) :    ExprF<IntermediateFactorial> {      return a.type === 'terminal' ? new Num(a.value)      :      a.value === 1         ? new Num(1)      :      /* recursive case    */ new Times({                                             type: 'terminal',                                             value: a.value                                           }, {                                             type: 'recursive',                                             value: a.value - 1                                           });    }, { type: 'recursive', value: base });}`

There’s a lot here, so let’s go through this step-by-step. First, we declare a type for the intermediate values that our coalgebra will use. This is the type that we use to keep track of our progress while building a new data structure, and which won’t exist in the anamorphism’s final output. Here we’re keeping track of whether the node we’re currently operating on is “terminal” (at the end of the tree we’re constructing) or “recursive” (a node in the middle which will have children.)

In the coalgebra we pass to `ana`, we handle three cases: when we have a terminal node, when our node has a type of “recursive” and a value of `1`, and when our node has a type of “recursive” with a different value. For terminal nodes, our task is easy: we just put the node’s value into a `Num`. When we have a “recursive” type node, we create a `Times` node, whose left value is a terminal, and whose right value is a “recursive” node, with a value one lower than that of our current node. (Unless our current node’s value is `1`, in which case we’ve reached our base case, and we return a `Num`.)

If we call `factorial(3)`, the execution will run something like this:

• We enter our coalgebra with the argument with a “recursive” type argument, of value `3`
• Our coalgebra produces a `Times` node, whose `left` value is a “terminal” type node, of value `3`, and whose right value is a “recursive” type node, of value `2`.
• `ana` uses `map` to recurse into our returned structure, and passes the `left` value of our returned node to our coalgebra. This node is a “terminal” type, so the coalgebra returns `new Num(3)`. `ana` tries to recurse into this with `map`, but in this case `map` doesn’t do anything, so we’re done here.
• Now `map` recurses into the `right` value of our node, which is a “recursive” type node, of value `2`. This proceeds like before; we produce a `Times` node that has a “terminal” type on one side, and a “recursive” type on the other. `ana` digs into this node with `map`, and the left side gets turned into `new Num(2)`.
• Finally, we get to our last node, which has a “recursive” type and a value of `1`. This hits the base case in our coalgebra, which returns `new Num(1)`. `ana` will try to `map` into this, and since `map` does nothing to values of type `Num`, the computation will terminate.

Finally, `factorial` returns the result, which is an object like this:

`new Times(  new Num(3),  new Times(    new Num(2),    new Num(1)))`

This may seem heavyweight compared to the catamorphisms we saw in my previous post, but this is only because this implementation takes care to be explicit in what it’s doing. We can code an equivalent function that is much more succinct:

`function cleanFactorial(base: number) : Expr {  return ana(exprFunctor,    a => a instanceof Num ? a    :    a === 1          ? new Num(1)    :    /* otherwise    */ new Times(new Num(a), a - 1),   base);}`

When we return a value of `Times` with a `Num` stuffed into it, `ana` will still recurse into this `Times`, and pass this `Num` to our coalgebra. Our coalgebra accounts for this by checking if a value is a `Num` and returning it unchanged if it is. This gives us a more readable way to differentiate nodes that we want to continue expanding (“recursive” nodes before, plain numbers now) from nodes that we don’t (“terminal nodes” before, `Num`s now.)

The `A` in `coalgebra`'s definition `A => F<A>` doesn’t need to be limited to flat values. Let’s see a case where `A` is a recursive value itself:

`function reverse(expr: Expr) : Expr {  return ana(exprFunctor, function(a: Expr) : ExprF<Expr> {    const expr = prj(out(a));    return inj(      expr instanceof Num   ? expr    : expr instanceof Plus  ? new Plus(expr.right, expr.left)    : expr instanceof Times ? new Times(expr.right, expr.left)    : /* expr is a Paren   */ expr);  }, expr);}`

This function takes an expression and swaps the left and right hand sides of each `Plus` and `Times` node in it, producing an equivalent expression. For example, `5 * 4 * 3 * 2 * 1` will turn into `1 * 2 * 3 * 4 * 5`. The “intermediate type” `A` here is `Expr` — we take a whole expression tree, and at each step, we pass part of that `Expr` to each half of the value we construct. In this way, we effectively walk along an Expr from the top down, transforming nodes before we step into them and transform their contents.

(An interesting note here is that this reversal function can also be implemented as a catamorphism, and the `flatten` and `addNecessaryParens` functions from my catamorphism post can also be implemented as anamorphisms. When we looked at the fixed points of functors, we saw that `ExprF<Expr> = Expr`, so it’s reasonable that we can turn an algebra with the signature `ExprF<Expr> => Expr` into a coalgebra with the signature `Expr => ExprF<Expr>` and vice-versa.)

For our final anamorphism, let’s switch gears and use a binary tree of numbers as our recursive type. An implementation of such a data structure can be found here. We’ll write a function which takes an array of numbers, and turns it into a tree with the values from the array as leaves:

`function treeifyArray(arr: Array<number>) : NumberTree {  if (arr.length === 0) throw new Error("argument error");  return ana(numberTreeFunctor, arr => {    if (arr.length === 1) return new Leaf(arr);    const splitIndex = Math.floor(arr.length / 2),          firstHalf = arr.slice(0, splitIndex),          secondHalf = arr.slice(splitIndex);    return new Node(firstHalf, secondHalf);  }, arr);}`

The coalgebra we use here returns a `Leaf` node when its input is an array containing a single element, and a `Node` node when the input is a longer array. Half of the input gets passed to each side of the `Node`, meaning that the output tree will be as balanced as possible. For instance, `treeifyArray([1, 2, 3, 4, 5])` will give a tree of form:

Like catamorphisms, anamorphisms are a useful, flexible class of functions. They seem to appear in projects less often in practice, but they’re a good thing to look out for. In general, if an algorithm is transforming a tree by walking along it from the top down, or is building up a nested structure from a single value or from nothing, there’s a good chance an anamorphism is hiding under the surface.

All code samples from this post are available here.

Thanks to Lizz Katsnelson for editing this post.

JavaScript developer with a focus on typed functional programming. He/him. https://jnkr.tech

## More from Joseph Junker

JavaScript developer with a focus on typed functional programming. He/him. https://jnkr.tech