Anamorphisms

Building up functors, recursively

8 min readAug 12, 2017

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.

Building things up

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.

Implementation

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 functorF<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.)

An initial example: factorial

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, Nums now.)

More anamorphisms

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[0]);    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.