What do you call the opposite of a functional pearl?

09 Mar 2026

I love recursion. As I’ve blogged about before, recursive implementations are usually the most maintainable way to solve inherently-recursive problems. That said, I do most of my programming in node.js and TypeScript, and I also love it when my code doesn’t overflow the stack. These things are sometimes in conflict.

This post is about a technique for manually converting elegant, maintainable recursive code into a gnarled imperative form, trading clarity (and some performance) for stack safety. This technique is not quite precise enough to be automated but it is mostly mechanical, requiring very little creativity or insight into the problem being solved. The resultant implementations are reasonably decipherable.

The key to this approach is something alluded to in my post on continuation-passing style: We can write code which simulates the call stack of the language we’re working in by representing stack frames as first-class values. That post does so in a functional context, unlocking superpowers like simulated resumable exceptions by choosing CPS functions as our representation. In this post we’ll do so in an imperative context, using mutable records to work around the limitations of our language runtime.

Code samples are given in TypeScript, but the general principle described here should translate to any language with basic support for mutability and parametric polymorphism. TypeScript’s type narrowing will be very handy for us, so in languages without type narrowing or pattern matching the specific implementation will need to be adapted.

Warm-up: Linked lists #

Before seeing the main technique, it may be helpful to build some intuition around the problem space. We’ll start off with some basic operations on linked lists and binary trees, and see where the problems start to creep in. This section is going to cover very basic material very pedantically, to try to stress the perspective that will be used in later sections.

First, let’s consider a linked list:

type LinkedList<T> = { 
    tag: "Cons",
    head: T,
    tail: LinkedList<T> } | {
        tag: "Nil"
    };

function cons<T>(head: T, tail: LinkedList<T>): LinkedList<T> {
    return { tag: "Cons", head, tail };
}

function nil<T>(): LinkedList<T> {
    return {
        tag: "Nil"
    }
}

const exampleList = cons(1, cons(2, cons(3, nil())));

A LinkedList is a type with two variants: Cons and Nil. Consuming a list means providing logic to handle each variant. Consider a sumList function:

function sumList(list: LinkedList<number>): number {
    if (list.tag === "Nil") return 0;
    return list.head + sumList(list.tail);
}

This uses a recursive call, so if the list is sufficiently long (around 10k items, on my machine) node.js will experience a stack overflow and throw an exception. This is because every time the function makes a recursive call, the runtime has to “remember” where to return to in the previous invocation so that it can complete the remaining addition operation.

We can remove the possibility for an overflow by converting this function to an iterative form:

function sumListIterative(list: LinkedList<number>): number {
    let sum = 0;
    let pointer = list;
    while (pointer.tag !== "Nil") {
        sum += pointer.head;
        pointer = pointer.tail;
    }
    return sum;
}

In the converted form we take a pointer to items in the list, running it down the list’s length and summing the node contents as we go. This works for two reasons:

1. Addition is associative. (1 + (2 + 3)) gives the same result as ((1 + 2) + 3). In the recursive function we are summing “from the right”, building up a stack of unresolved additions “on the left” which can’t be resolved until the right side is done. In our iterative solution we are summing “from the left”, and so do not need to defer any work.
2. Linked lists are inherently iterative, with each node pointing to exactly one or zero additional nodes. The lack of branching within the data structure makes it trivial to fully explore it.

The conversion hinges on the ability to remove the need to “remember” partial computations, rendering a stateless solution.

Binary trees: deferring work #

Let’s take away the benefits of point 2 above, by switching to a data structure with a branching shape. Consider a binary trees of numbers:

type BinaryTree<T> = {
  contents: T,
  left: BinaryTree<T> | null,
  right: BinaryTree<T> | null
}

function tree<T>(
	rootContents: T, 
	left: BinaryTree<T> | null, 
	right: BinaryTree<T> | null): BinaryTree<T> {
	
    return {
        contents: rootContents,
        left,
        right
    }
}

function leaf<T>(contents: T): BinaryTree<T> {
    return {
        contents,
        left: null,
        right: null
    }
}

const exampleTree = tree(
    1,
    tree(2, leaf(3), leaf(4)),
    tree(5, leaf(6), leaf(7))
)

We can easily write a recursive sum function:

function sumTree(tree: BinaryTree<number> | null): number {
    if (!tree) return 0;
    const leftSum = sumTree(tree.left);
    const rightSum = sumTree(tree.right);
    return leftSum + rightSum + tree.contents;
}

This function’s execution works something like this:

• The runtime executes sumTree(tree.left). When doing so, it remembers its place in the original sumTree invocation, so it can come back to it and finish it later.
• Once execution returns to the original sumTree invocation, it executes sumTree(tree.right). Again, it remembers its place in the function.
• The runtime computes leftSum + rightSum + tree.contents and returns control to the caller.

To make this function iterative we will have to implement both the addition step and the remembering step. The standard way of implementing this is via a stack or queue:

function sumTreeIterative(tree: BinaryTree<number>): number {
    const stack: Array<BinaryTree<number>> = [tree];
    let total = 0;

    while (stack.length) {
        const node = stack.pop()!;
        total += node.contents;

        if (node.left) {
            stack.push(node.left);
        }

        if (node.right) {
            stack.push(node.right);
        }
    }

    return total;
}

Every time we encounter a single node we find ourselves in the unfortunate situation of having to do two pieces of work: handle its left side and handle its right side. These, in turn, may produce their own work. The stack allows us to solve these problems one step at a time by deferring the branches we do not immediately explore. The stack variable in the iterative solution serves the same purpose as JavaScript’s built-in call stack in the recursive solution.1 We were able to alter the performance characteristics of our code by taking something that the language runtime normally gives us for free, and instead accepting the incidental complexity of managing it manually.

In the next section we’ll take this relocation of responsibility to its logical extreme.

Mutually-recursive trees and forests #

As noted in the section on linked lists, the implementations in the last two sections depends on us recognizing the associativity of addition. This recognition is an example of what I call insight into the nature of a problem. When we understand a problem well we can use our creativity to implement direct and elegant solutions. Creativity has its limits, though: some problems inherently resist understanding while still requiring solutions. In such cases it is desirable to have patterns and heuristics that allow us to muddle through despite our lack of insight.

This section presents a problem which I hope is sufficiently resistant to understanding to prevent most developers from easily coding an iterative implementation from scratch. I will show how we can still produce an iterative solution, despite our lack of insight.

First, the data structure. We will be using a mutually recursive pair of a tree, which holds a value, and a forest, which holds a linked list of trees:

type Tree<T> =
    | {
          tag: "Empty";
      }
    | {
          tag: "Node";
          value: T;
          forest: Forest<T>;
      };

type Forest<T> =
    | {
          tag: "Nil";
      }
    | {
          tag: "Cons";
          head: Tree<T>;
          tail: Forest<T>;
      };

function empty<T>(): Tree<T> {
    return {
        tag: "Empty",
    };
}

function node<T>(value: T, forest: Forest<T>): Tree<T> {
    return {
        tag: "Node",
        value,
        forest,
    };
}

function nil<T>(): Forest<T> {
    return {
        tag: "Nil",
    };
}

function cons<T>(head: Tree<T>, tail: Forest<T>): Forest<T> {
    return {
        tag: "Cons",
        head,
        tail,
    };
}

This data structure comes from the Wikipedia page on mutual recursion, which itself cites course notes from an introduction to Standard ML by Robert Harper. I am not aware of practical reasons to choose this particular representation of trees over the alternatives, other than as an illustration of a language’s ability to support mutually recursive data. I find it unwieldy, which is why I chose to use it for this post.2

We might instantiate one of these like this:

const exampleTree = node(
    1,
    cons(
        node(2, cons(node(3, nil()), nil())),
        cons(
            node(4, cons(
                        empty(), 
                        cons(node(6, nil()), nil()))),
            nil()),
    ),
);

I find this easier to understand with a visualization. Here I’m using purple ovals for calls to node, green rectangles for calls to cons, black ovals for calls to empty and black rectangles for calls to nil:

One strike against this data structure is that it can contain gaps: observe the empty() node between the nodes labeled 4 and 6. Another strike is that it is resistant to a straightforward notion of breadth and depth. The nodes are labeled 1-6 (skipping an empty node where one might expect a 5) in some sort of order. Is that order breadth-first, depth-first, or arbitrary? The answer depends on whether you consider the trees in forests to be siblings or whether you consider each node of a forest as a binary fork in a tree.

In the case of this example tree, I’ll define a breadth-first traversal as one which would order these notes as 12436, and a depth-first traversal as one which would order them 12346. I’ll be using the depth-first order for the remainder of this post.

Now that we’ve made our data structure unpleasant, we should next do the same to our recursive function. Here I’m choosing to use a fold function, which will allow nodes in the tree to be consumed in the order in which they are encountered during a depth-first traversal. This places significantly tighter restrictions on our solution than we had before.

Here is the recursive implementation:

function foldTree<S, T>(
    accumulator: S,
    tree: Tree<T>,
    fn: (accumulator: S, value: T) => S,
): S {
    if (tree.tag === "Empty") return accumulator;
    return foldForest(fn(accumulator, tree.value), tree.forest, fn);
}

function foldForest<S, T>(
    accumulator: S,
    forest: Forest<T>,
    fn: (accumulator: S, value: T) => S,
): S {
    if (forest.tag === "Nil") return accumulator;
    const newAcc = foldTree(accumulator, forest.head, fn);
    return foldForest(newAcc, forest.tail, fn);
}

The implementations are minimal, and in my mind are the most “natural” approach to traversing these structures with an accumulator.

We can verify the implementation’s behavior by plugging in a function which simply collects the nodes as they are encountered, simplifying the nested tree structure into a flat array:

function collectRecursive<T>(tree: Tree<T>): Array<T> {
    return foldTree([] as Array<T>, tree, (acc, value) => [
        ...acc,
        value,
    ]);
}

console.dir(collectRecursive(exampleTree));
// outputs: [ 1, 2, 3, 4, 6 ]

We’ve finally arrived at our full problem statement. How can we convert foldTree into an iterative form?

Reifying execution #

The approach taken here is not to try to implement a recursive solution directly. Instead, we will tediously translate the recursive functions into a more explicit form.

Consider what would be involved in the execution of foldTree. It takes three arguments: an accumulator, a tree, and a function. It spawns zero or one recursive child calls. It produces a return value after running.

We will create a data structure for all of these things, representing the stack frame of the function’s execution:

type FoldTreeFrame<S, T> = {
    tag: "FoldTreeFrame";
    accumulator: S;
    tree: Tree<T>;
    fn: (accumulator: S, value: T) => S;
    child: FoldForestFrame<S, T> | null;
    returnValue: null | {
        value: S;
    };
    parent: StackFrame<S, T>;
};

We are also tracking the parent of the stack frame, which is the stack frame that called it. This is for mechanical reasons that will be explained later.

child may be null because foldTree may exit early, without spawning a child. returnValue will be null when the frame is first created, and filled in when the frame is done executing.

We can likewise define a stack frame for foldForest:

type FoldForestFrame<S, T> = {
    tag: "FoldForestFrame";
    accumulator: S;
    forest: Forest<T>;
    fn: (accumulator: S, value: T) => S;
    treeChild: FoldTreeFrame<S, T> | null;
    forestChild: FoldForestFrame<S, T> | null;
    returnValue: null | {
        value: S;
    };
    parent: StackFrame<S, T>;
};

Finally, we need a stack frame for the outermost frame which represents the outside caller of our recursive function:

type ExternalCaller<S, T> = {
    tag: "ExternalCaller";
    topFrame: FoldTreeFrame<S, T> | null;
};

type StackFrame<S, T> =
    | FoldTreeFrame<S, T>
    | FoldForestFrame<S, T>
    | ExternalCaller<S, T>;

We are going to write a function which simulates the recursive functions by creating and modifying StackFrame objects describing the computation as it runs. Consider the tree of function calls which occurs when the recursive functions are invoked; we are representing this exact tree as a data structure which we can traverse and mutate.

Our lives will be easier if we create some boilerplate functions for constructing our various data types. Aside from the choice of names their implementation is uninteresting.

function callFoldTree<S, T>(
    accumulator: S,
    tree: Tree<T>,
    fn: (accumulator: S, value: T) => S,
    parent: FoldForestFrame<S, T> | ExternalCaller<S, T>,
): FoldTreeFrame<S, T> {
    return {
        tag: "FoldTreeFrame",
        accumulator,
        fn,
        tree,
        child: null,
        returnValue: null,
        parent,
    };
}

function callFoldForest<S, T>(
    accumulator: S,
    forest: Forest<T>,
    fn: (accumulator: S, value: T) => S,
    parent: FoldTreeFrame<S, T> | FoldForestFrame<S, T>,
): FoldForestFrame<S, T> {
    return {
        tag: "FoldForestFrame",
        accumulator,
        forest,
        fn,
        treeChild: null,
        forestChild: null,
        returnValue: null,
        parent,
    };
}

function externalCaller<S, T>(
): ExternalCaller<S, T> {
    return {
        tag: "ExternalCaller",
        topFrame: null,
    };
}

To start, let’s make a shell of our recursive function. This function will initialize itself by creating an ExternalCaller as an outermost parent, and a FoldTreeFrame which points to it. We’ll store the current frame being operated on in a mutable variable, and run our processing in a loop.

function foldIterative<S, T>(
    accumulator: S,
    tree: Tree<T>,
    fn: (accumulator: S, value: T) => S,
): S {
    const caller: ExternalCaller<S, T> = externalCaller();

    const topFrame = callFoldTree(accumulator, tree, fn, caller);
    caller.topFrame = topFrame;

    let frame: StackFrame<S, T> = topFrame;

    while (frame.tag !== "ExternalCaller") {
        if (frame.tag === "FoldTreeFrame") {
            // Implementation for foldTree() goes here
        } else if (frame.tag === "FoldForestFrame") {
            // Implementation for foldForest() goes here
        }
    }

    return frame.topFrame?.returnValue?.value!;
}

The condition to break out of the loop is that our current frame is the outermost caller, at which point we access the returnValue of its child. The individual implementations for foldTree and foldForest will be responsible for changing which stack frame our frame variable points at in each step.

TypeScript’s type narrowing will be our friend throughout this implementation. We need to determine which kind of frame we are working with at any point in time, which makes the tag fields on our types essential.

First, let’s look at the implementation for the foldTree case. As a reminder, here is the function that we are replacing:

function foldTree<S, T>(
    accumulator: S,
    tree: Tree<T>,
    fn: (accumulator: S, value: T) => S,
): S {
    if (tree.tag === "Empty") return accumulator;
    return foldForest(fn(accumulator, tree.value), tree.forest, fn);
}

And here is how we are replacing it:

if (frame.tag === "FoldTreeFrame") {
    if (frame.tree.tag === "Empty") {
        // Block 1
        frame.returnValue = { value: frame.accumulator };
        frame = frame.parent;
    } else {
        if (frame.child?.returnValue) {
            // Block 2
            frame.returnValue = {
                value: frame.child.returnValue.value,
            };
            frame.child = null;
            frame = frame.parent;
        } else {
            // Block 3
            const newAccumulator = fn(
                frame.accumulator,
                frame.tree.value,
            );
            frame.child = callFoldForest(
                newAccumulator,
                frame.tree.forest,
                frame.fn,
                frame,
            );

            frame = frame.child;
        }
    }
}

The code labelled “Block 1” will run when the tree is empty, setting the current stack frame’s result value to the frame’s accumulator argument, and returning control back to this frame’s parent (by changing the active frame to point at the current frame’s parent). This is identical to the behavior of the recursive implementation.

Similarly, the code labelled “Block 3” will run when the tree is not empty, and when this frame’s child invocation is not yet complete. In this case we pass the accumulator and the tree’s contents into fn and then call the fold forest function with the new accumulator. This “call” is done by creating a stack frame for the child invocation and transferring control to it, using frame = frame.child. Again, logically, this matches the second case of the recursive implementation.

The code labelled “Block 2” does not correspond directly to any code in the recursive function; it is pure incidental complexity. When we find ourselves processing a FoldTreeFrame it may be because we are entering it for the first time after a parent call created it, or it may be because we are re-entering it after a child frame’s execution completed. This means that, before we make a recursive call in block 3, we need to check whether that call has already been completed. If so, we run whatever logic should happen after the recursive call. In this case there is no such logic in foldTree so we only need to deal with the mechanical concerns of returning to our parent frame.

To return, we do three things:

• Set our own return value
• Clean up any recursive calls that this frame has made, by setting them to null
• Update the frame pointer to aim at the current frame’s parent

The clean-up step may seem strange, but it’s a memory-usage optimization. When a language runtime executes a series of function calls it does not need to keep already-exited stack frames around. Branching function calls only form a tree in the time dimension; at any given snapshot in time there exists only a single stack of function calls in memory, tracing the current path through the tree. If we did not set our child frames to null we would end up building the whole tree up in memory and retaining it until the recursive processing is complete. Removing references to them allows the runtime to reclaim their memory at its leisure. If you’ve ever wished that you could deal with manual memory management in JavaScript, now’s your chance!

We’ve covered all of the tricks now, and the translation of foldForest() is more of the same:

if (frame.tag === "FoldForestFrame") {
    if (frame.forest.tag === "Nil") {
        frame.returnValue = { value: frame.accumulator };
        frame = frame.parent;
    } else {
        if (frame.forestChild?.returnValue) {
            frame.returnValue = {
                value: frame.forestChild.returnValue.value,
            };
            frame.treeChild = null;
            frame.forestChild = null;
            frame = frame.parent;
        } else if (frame.treeChild?.returnValue) {
            frame.forestChild = callFoldForest(
                frame.treeChild.returnValue.value,
                frame.forest.tail,
                frame.fn,
                frame,
            );

            frame = frame.forestChild;
        } else {
            frame.treeChild = callFoldTree(
                frame.accumulator,
                frame.forest.head,
                frame.fn,
                frame,
            );

            frame = frame.treeChild;
        }
    }
}

Folding forests requires two recursive calls; we have to check the completion of both of them, and also to clean up both of them when we exit the forest frame.

The full iterative implementation #

That’s it! Putting the pieces together, here’s the final implementation:

function foldTreeIterative<S, T>(
    accumulator: S,
    tree: Tree<T>,
    fn: (accumulator: S, value: T) => S,
): S {
    const caller: ExternalCaller<S, T> = externalCaller();

    const topFrame = callFoldTree(accumulator, tree, fn, caller);
    caller.topFrame = topFrame;

    let frame: StackFrame<S, T> = topFrame;

    while (frame.tag !== "ExternalCaller") {
        if (frame.tag === "FoldTreeFrame") {
            if (frame.tree.tag === "Empty") {
                frame.returnValue = { value: frame.accumulator };
                frame = frame.parent;
            } else {
                if (frame.child?.returnValue) {
                    frame.returnValue = {
                        value: frame.child.returnValue.value,
                    };
                    frame.child = null;
                    frame = frame.parent;
                } else {
                    const newAccumulator = fn(
                        frame.accumulator,
                        frame.tree.value,
                    );
                    frame.child = callFoldForest(
                        newAccumulator,
                        frame.tree.forest,
                        frame.fn,
                        frame,
                    );

                    frame = frame.child;
                }
            }
        } else if (frame.tag === "FoldForestFrame") {
            if (frame.forest.tag === "Nil") {
                frame.returnValue = { value: frame.accumulator };
                frame = frame.parent;
            } else {
                if (frame.forestChild?.returnValue) {
                    frame.returnValue = {
                        value: frame.forestChild.returnValue.value,
                    };
                    frame.treeChild = null;
                    frame.forestChild = null;
                    frame = frame.parent;
                } else if (frame.treeChild?.returnValue) {
                    frame.forestChild = callFoldForest(
                        frame.treeChild.returnValue.value,
                        frame.forest.tail,
                        frame.fn,
                        frame,
                    );

                    frame = frame.forestChild;
                } else {
                    frame.treeChild = callFoldTree(
                        frame.accumulator,
                        frame.forest.head,
                        frame.fn,
                        frame,
                    );

                    frame = frame.treeChild;
                }
            }
        }
    }

    return frame.topFrame?.returnValue?.value!;
}

It’s not going to win any points for beauty, but it works.

…it does work, right?

Property-based testing #

Our initial recursive implementation was made up of 5 lines of logical code and 6 lines of type definitions. All of the data was immutable and the implementation was effectively forced by the shape of the data; under these constraints it would be harder to get it wrong than to get it right. Our iterative implementation is over ten times as long (not even counting type definitions and helper functions), makes wanton use of mutability, and is generally rife with potential edge cases. Questions about how this could possibly be tested and maintained are unavoidable.

Fortunately there’s a relatively easy answer. We don’t need to consider the internal implementation of the iterative solution at all in order to be confident in its correctness. Instead, we first convince ourselves of the correctness of the simpler reference implementation, and then convince ourselves that the two are equivalent.

I won’t cover the process of unit testing the recursive implementation. It is simple enough that, for the purposes of this blog post, I’ll take its correctness as a given. What I’ll focus on here is the step where we convince ourselves that the two implementations are interchangeable.

The two implementations are equivalent if, for all possible inputs, they always produce equal outputs. Unfortunately it is not possible to generate every possible input, so we will have to settle for generating a very large representative sample. This is the domain of property-based testing. To my knowledge fast-check is currently the most mature library for property-based testing in TypeScript and it’s what I’ll use here.

A full explanation of fast-check and property-based testing in general are beyond the scope of this post, and I recommend checking the project’s documentation for more information. In a nutshell, though, we can use it to create generators for random data of a given type. Here’s what the generators look like for the mutually-recursive Tree<T> type, specialized to be Tree<number>:

const arbitraries = fc.letrec((tie) => ({
    empty: fc.constant({ tag: "Empty" }),
    node: fc.record({
        tag: fc.constant("Node"),
        value: fc.nat(),
        forest: tie("forest"),
    }),
    tree: fc.oneof(tie("empty"), {
        arbitrary: tie("node"),
        weight: 5,
    }),
    nil: fc.constant({ tag: "Nil" }),
    cons: fc.record({
        tag: fc.constant("Cons"),
        head: tie("tree"),
        tail: tie("forest"),
    }),
    forest: fc.oneof({ depthSize: "medium" }, tie("nil"), {
        arbitrary: tie("cons"),
        weight: 5,
    }),
}));

letrec allows us to define mutually-recursive data types which refer to each other by name. oneof chooses one of an array of items, but is biased towards the first item in the array. We need to ensure our non-recursive cases are passed in first. weight and depthSize are used here to tune the outputs to have a decent balance between large and small outputs.

When generating recursive data with fast-check it’s generally best to use the statistics function to ensure the arbitraries are producing decent samples3. Here’s what that looks like:

fc.statistics(
    arbitraries.tree as fc.Arbitrary<Tree<number>>,
    (tree) => {
        const nodeCount = foldTree(0, tree, (acc, node) => acc + 1);
        if (nodeCount < 5) return "Under 5 nodes";
        if (nodeCount < 10) return "5 to 10 nodes";
        return "10 nodes or more";
    },
    { numRuns: 5000 },
);

Running this shows that 40% of the generated trees have 5-10 nodes, and 10% have 10+ nodes. This feels like a decent sample to me.

Now that we have generators for the test data, all we need is to assert that our function’s behaviors match. I’ll do so using the uvu test runner:

test("Equivalence", () => {
    fc.assert(
        fc.property(arbitraries.tree as fc.Arbitrary<Tree<number>>, (tree) => {
            function foldingFn(
                acc: Array<number>,
                value: number,
            ): Array<number> {
                return [...acc, value];
            }

            const recursiveResult = foldTree(
                [] as Array<number>,
                tree,
                foldingFn,
            );

            const iterativeResult = foldTreeIterative(
                [] as Array<number>,
                tree,
                foldingFn,
            );

            assert.equal(recursiveResult, iterativeResult);
        }),
        { numRuns: 500 },
    );
});

test.run();

I chose to use a folding function which collects the values into an array, because this makes it trivial to ensure that the traversal orders are identical. The test took only a few minutes to write and (on my machine) under 20 ms to run. Pretty cheap, considering that it’s enough to convince me of the correctness of some very gnarly code.

In the presence of property-based testing I consider the techniques shown in this post to be fully appropriate for production codebases, so long as a recursive reference implementation is maintained and used as a test oracle.

Benchmarks #

To dot i’s and cross t’s, I think it’s important to show the performance impact of the techniques in this post. If you’re willing to go through the pain of applying this process to achieve stack safety there’s a pretty good chance that whatever you’re working on is at least somewhat performance-sensitive.

I am far from an expert at benchmarking node’s performance, but here’s the approach I took.

First, I wrote a script to generate random trees:

function randomNat(): number {
    return Math.floor(Math.random() * 1000);
}

function generateTree(size: number): Tree<number> {
    if (size <= 1) return empty();
    return node(randomNat(), generateForest(size - 1));
}

function generateForest(size: number): Forest<number> {
    if (size <= 1) return nil();
    const treeSizeDecrease = Math.random() < 0.5 ? 0 : -1;
    const forestSizeDecrease = Math.random() < 0.5 ? 0 : -1;
    const treeToForestRatio = Math.random();
    const treeSize = Math.floor(size * treeToForestRatio) + treeSizeDecrease;
    const forestSize =
        Math.floor(size * (1 - treeToForestRatio)) + forestSizeDecrease;

    return cons(generateTree(treeSize), generateForest(forestSize));
}

export function generateData(): Array<Tree<number>> {
    let results: Array<Tree<number>> = [];

    for (let i = 0; i < 10000; i += 10) {
        results.push(generateTree(i));
    }

    return results;
}

The goal here was to generate trees in a range of sizes, from small to large, and with a range of different shapes. generateForest will cause the size of trees to generally decrease over time, and will randomly choose how much of its size gets allocated to the size of its tree child versus its forest child. generateData will produce 1000 trees of increasing size. Running some basic stats on the output confirms that this results in a relatively even distribution of trees from 0 to 2000 nodes.

Performance tests were run using two different workloads: one for summing the contents of each tree, and one for collecting the contents into an array.

function sumIterative(): Array<number> {
    let result = new Array(trees.length);
    for (let i = 0; i < trees.length; i++) {
        result[i] = foldTreeIterative(0, trees[i]!, (acc, x) => acc + x);
    }
    return result;
}

function sumRecursive(): Array<number> {
    let result = new Array(trees.length);
    for (let i = 0; i < trees.length; i++) {
        result[i] = foldTreeRecursive(0, trees[i]!, (acc, x) => acc + x);
    }
    return result;
}

function collectIterative(): Array<Array<number>> {
    let result: Array<Array<number>> = new Array(trees.length);
    for (let i = 0; i < trees.length; i++) {
        result[i] = foldTreeIterative(
            [] as Array<number>,
            trees[i]!,
            (acc, x) => {
                acc.push(x);
                return acc;
            },
        );
    }
    return result;
}

function collectRecursive(): Array<Array<number>> {
    let result: Array<Array<number>> = new Array(trees.length);
    for (let i = 0; i < trees.length; i++) {
        result[i] = foldTreeRecursive(
            [] as Array<number>,
            trees[i]!,
            (acc, x) => {
                acc.push(x);
                return acc;
            },
        );
    }
    return result;
}

I timed how long it took to run each function ten times. The garbage collector was manually invoked before each run, and the run was repeated twice before starting the timer to ensure that the V8 optimizer was warmed up. After 30 runs, these were the results (timings given in milliseconds):

Iterative sum results:
----------------------
minimum:         1267.5
maximum:         1286.5
mean:            1276.4
median:          1276.0
std. deviation:  4.66

Recursive sum results:
----------------------
minimum:         557.3
maximum:         582.2
mean:            566.9
median:          565.0
std. deviation:  6.9

Iteration is 2.25x slower than recursion


Iterative collection results:
-----------------------------
minimum:         1377.3
maximum:         1402.1
mean:            1391.0
median:          1391.8
std. deviation:  5.42

Recursive collection results:
-----------------------------
minimum:         651.4
maximum:         666.1
mean:            657.9
median:          656.2
std. deviation:  4.45

Iteration is 2.12x slower than recursion

A 2.2x slowdown is really not that bad, considering that the core concept here is to use user-level JavaScript code to perform the same job that’s normally done by a highly-optimized engine written in C++.4

The full benchmark code can be found in this post’s example code on GitHub.

Limitations of this approach #

The main limitation here is that these techniques will not apply to polymorphically-recursive functions. Consider this data type, adapted from the Wikipedia page on polymorphic recursion:

type Nested<T> = {
    head: T;
    tail: Nested<Array<T>>;
} | null;

Note that Nested is recursive, defined in terms of itself, but that the recursive invocations of Nested are passed a different type than the original (due to the Array wrapper). A piece of data with the Nested<number> type is a linked list of arrays of numbers, and arrays of arrays of numbers, and arrays of arrays of arrays… with every item in the list containing a deeper level of nesting that the one before it. The type of T changes as the type is unfurled. TypeScript does allow us to write recursive functions which handle this type:

function length<T>(nested: Nested<T>): number {
    if (!nested) return 0;
    return 1 + length(nested.tail);
}

In our iterative implementation, frame is a pointer to a stack frame holding a piece of our data structure. In the case of polymorphic recursion the type of frame would have to change with each invocation of the loop, which TypeScript will not permit.

Verity has made progress on this, with an implementation that uses trampolines and an encoding of existential types. It seems highly likely that an iterative solution exists but that the technique shown here is not sufficiently capable to handle it.

Open questions #

There’s a number of things I’d like to know about this topic.

I stumbled into this way of thinking about recursion on my own while implementing my TypeScript port of Uniplate, but it seems like the kind of thing that would arise naturally in all sorts of imperative settings. I doubt I’m the first, second, or hundredth person to come up with it. I would love references to other people’s approaches here.

I’m intensely curious about other attempts at making polymorphically recursive functions iterable. At the same time, I’m curious as to whether any polymorphically recursive functions can have practical applications in TypeScript at all. (Finger trees might be an option, though I’m not sure whether their performance will make them count as “practical”.) Chris Okasaki’s dissertation “Purely Functional Data Structures” may be a good place to start.

I’m curious about alternative approaches to this problem which might produce code which is easier to maintain and reason about. Verity has also shown me an encoding based off of zippers, which may be another path forward. I feel like starting from a CPS encoding of the recursive functions might also present interesting possibilities.

If you know the answers to any of these questions, please let me know!

Further reading #

Abhinav Sarkar has written a post on a similar topic about mechanically deriving tree iterators based on transformations of recursive functions which starts with a CPS transform.

Acknowledgments #

Thank you to tendstofortytwo, PolyWolf, and Verity for providing me with feedback on earlier drafts of this post.

All code samples in this post are released into the public domain under a Creative Commons 0 license. Code samples and full license text may be found here.

1. Indeed, if you work it out on paper, you’ll see that the changes in the size of the manually-maintained stack in the iterative approach directly correspond to changes in the size of node’s built-in call stack in the recursive approach. ↩

2. For practical applications this mutually recursive tree/forest pair seems like a strictly worse version of a rose tree, which can be defined as type RoseTree<A> = { value: A, children: Array<RoseTree<A>>}. Rose trees are my favorite data structure. In some cases children could be better served by a linked list rather than an array, which brings these two structures closer to one another, but the fact that a rose tree cannot contain gaps and that its definition is not mutually recursive are points in its favor. ↩

3. These calls to statistics are used during development of the arbitraries; I would not execute the statistics as part of runs of the test suite. ↩

4. Given that these metrics are for processing ten thousand trees which each have an average of one thousand nodes, this means that even in the slowest case my small laptop was processing over seven million nodes per second. Computers are inconceivably fast. ↩